1.启发式搜索：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

　　启发算法有： 蚁群算法，遗传算法、模拟退火算法等。

2.估价算法：从当前节点移动到目标节点的预估损耗。

　　预估算法有：曼哈顿（manhattan）等。

3.算法特点：理论上时间是最优的，但空间增长是指数型的。

4.java实现：上下左右移动

package cn.liushaofeng.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
* A Star Algorithm
* @author liushaofeng
* @date 2015-8-24 下午11:05:48
* @version 1.0.0
*/
public class AstarAlgorithm
{
private List openList = null;
private List closeList = null;
private int[][] map;

 /\*\*  
  \* default constructor  
  \* @param map data map  
  \*/  
 public AstarAlgorithm(int\[\]\[\] map)  
 {  
     this.map = map;  
     this.openList = new ArrayList<Node>();  
     this.closeList = new ArrayList<Node>();  
 }

 /\*\*  
  \* find path  
  \* @param srcNode source node  
  \* @param desNode destination node  
  \* @return node path  
  \*/  
 public Node findPath(Node srcNode, Node desNode)  
 {  
     init(srcNode);  
     do  
     {  
         if (openList.isEmpty())  
         {  
             break;  
         }

         Node node = openList.get(0);  
         List<Node> aroundPoint = getAroundPoint(srcNode, node, desNode);  
         openList.addAll(aroundPoint);  
         closeList.add(node);  
         openList.remove(node);

     } while (!findDes(desNode));

     return findNodePath(desNode);  
 }

 private Node findNodePath(Node desNode)  
 {  
     for (Node node : openList)  
     {  
         if (node.getX() == desNode.getX() && node.getY() == desNode.getY())  
         {  
             return node;  
         }  
     }  
     return null;  
 }

 private boolean findDes(Node desNode)  
 {  
     for (Node node : openList)  
     {  
         if (node.getX() == desNode.getX() && node.getY() == desNode.getY())  
         {  
             return true;  
         }  
     }  
     return false;  
 }

 private void init(Node srcNode)  
 {  
     openList.add(srcNode);  
 }

 // top bottom left and right, four points  
 private List<Node> getAroundPoint(Node srcNode, Node nextNode, Node desNode)  
 {  
     int x = srcNode.getX();  
     int y = srcNode.getY();

     int\[\] xData = new int\[2\];  
     int\[\] yData = new int\[2\];  
     if (x - 1 >= 0)  
     {  
         xData\[0\] = x - 1;  
     }  
     if (x + 1 < map.length)  
     {  
         xData\[1\] = x + 1;  
     }

     if (y - 1 >= 0)  
     {  
         yData\[0\] = y - 1;  
     }  
     if (y + 1 < map\[0\].length)  
     {  
         yData\[1\] = y + 1;  
     }

     List<Node> tmpList = new ArrayList<Node>();

     for (int i : xData)  
     {  
         Node node = new Node(i, y, srcNode);  
         if (!isObstacle(node) && !inClosetList(node))  
         {  
             calcWeight(srcNode, node, desNode);  
             tmpList.add(node);  
         }  
     }

     for (int i : yData)  
     {  
         Node node = new Node(x, i, srcNode);  
         if (!isObstacle(node) && !inClosetList(node))  
         {  
             calcWeight(srcNode, node, desNode);  
             tmpList.add(node);  
         }  
     }

     return tmpList;  
 }

 private void calcWeight(Node parentNode, Node node, Node desNode)  
 {  
     node.setG(parentNode.getG() + 10);  
     int h = Math.abs(node.getX() - desNode.getX()) + Math.abs(node.getY() - desNode.getY());  
     node.setWeight(node.getG() + h \* 10);  
 }

 private boolean inClosetList(Node nextNode)  
 {  
     for (Node node : closeList)  
     {  
         if (node.getX() == nextNode.getX() && node.getY() == nextNode.getY())  
         {  
             return true;  
         }  
     }  
     return false;  
 }

 private boolean isObstacle(Node nextNode)  
 {  
     return map\[nextNode.getX()\]\[nextNode.getY()\] == 1;  
 }

 public static void main(String\[\] args)  
 {  
     int\[\]\[\] map =  
     {  
     { 0, 0, 0, 0, 0, 0, 0 },  
     { 0, 0, 0, 0, 0, 0, 0 },  
     { 0, 0, 0, 1, 0, 0, 0 },  
     { 0, 0, 0, 1, 0, 0, 0 },  
     { 0, 0, 0, 1, 0, 0, 0 },  
     { 0, 0, 0, 0, 0, 0, 0 },  
     { 0, 0, 0, 0, 0, 0, 0 } };

     AstarAlgorithm astar = new AstarAlgorithm(map);  
     Node pathNode = astar.findPath(new Node(3, 1, null), new Node(3, 5, null));  
     System.out.println(pathNode == null ? "Can not find path!" : pathNode.toString());  
 }  

}

查看代码

数据模型

package cn.liushaofeng.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
* Node
* @author liushaofeng
* @date 2015-8-24 下午09:48:53
* @version 1.0.0
*/
public class Node
{
private Node parentNode;
private int x;
private int y;

 private int weight;  
 private int g;

 /\*\*  
  \* default constructor  
  \* @param x x point  
  \* @param y y point  
  \* @param parentNode parent node  
  \*/  
 public Node(int x, int y, Node parentNode)  
 {  
     this.x = x;  
     this.y = y;  
     this.parentNode = parentNode;  
 }

 public int getG()  
 {  
     return g;  
 }

 public void setG(int g)  
 {  
     this.g = g;  
 }

 public Node getParentNode()  
 {  
     return parentNode;  
 }

 public void setParentNode(Node parentNode)  
 {  
     this.parentNode = parentNode;  
 }

 public int getX()  
 {  
     return x;  
 }

 public void setX(int x)  
 {  
     this.x = x;  
 }

 public int getY()  
 {  
     return y;  
 }

 public void setY(int y)  
 {  
     this.y = y;  
 }

 public int getWeight()  
 {  
     return weight;  
 }

 public void setWeight(int weight)  
 {  
     this.weight = weight;  
 }

 @Override  
 public String toString()  
 {  
     return getPath();  
 }

 private String getPath()  
 {  
     List<Node> dataList = new ArrayList<Node>();  
     Node node = this;  
     while (node != null)  
     {  
         dataList.add(node);  
         node = node.getParentNode();  
     }

     StringBuffer sb = new StringBuffer();  
     for (int i = dataList.size() - 1; i >= 0; i--)  
     {  
         if (i == 0)  
         {  
             sb.append("(" + dataList.get(i).getX() + "," + dataList.get(i).getY() + ")");  
         } else  
         {  
             sb.append("(" + dataList.get(i).getX() + "," + dataList.get(i).getY() + ")->");  
         }  
     }  
     return sb.toString();  
 }  

}

查看代码

代码待调试。