1491204654
A-star算法描述：
A算法，启发式算法，A（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。
公式表示为： f(n)=g(n)+h(n),
其中 f(n) 是从初始状态经由状态n到目标状态的代价估计，
g(n) 是在状态空间中从初始状态到状态n的实际代价，
h(n) 是从状态n到目标状态的最佳路径的估计代价。
（对于路径搜索问题，状态就是图中的节点，代价就是距离）
这几篇博客对A启发式算法介绍的很详细 堪称最好的A*算法 启发式搜索技术A
之前就有了解过A算法解决八数码问题，也用过BFS广度优先搜索走迷宫，说说我对A算法的理解吧，A算法类似BFS，但是A算法的重点在于设计权重判断函数，选择最佳的走法，而且是有目标性的走，不像BFS是盲目的走法，例如在 9 * 9方格中，可以上下左右跟斜线行走，当然9 * 9的方格是正方形，所以横着走跟竖着走权重设为1，那么斜着走就是根号2，大概的比例是 1 : 1.414 ，约等于 10 ：14，那么 我们就可以选择这个权重来进行估值，每次选择权重最小的一个方向走。
Java代码实现
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class A {
class Node {
int x, y;
int g, h, f;
Node parentNode;
public Node() {
}
public int compareTo(Node node) {
return this.f - node.f;
}
public Node(int x, int y, Node parentNode) {
super();
this.x = x;
this.y = y;
this.parentNode = parentNode;
}
}
static List<Node> openList = new ArrayList<Node>();
static List<Node> closeList = new ArrayList<Node>();
static int COST_ROW, COST_COL, COST_X;
// 1为可通行，0为障碍物，不可通行
static int[][] map = new int[][] {
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 0, 0, 0, 0, 1, 0, 0, 1 },
{ 1, 1, 1, 1, 0, 0, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 0, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 0, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
public static void main(String[] args) {
int row = map.length;
int col = map[0].length;
// 权重
COST_ROW = 10;
COST_COL = 10;
COST_X = 14;
boolean flag = astar(map, new A().new Node(4, 2, null), new A().new Node(4, col - 2, null), row, col);
if(flag)
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print(map[i][j] + " ");
}
System.out.print("\n");
}
else
System.out.println("Not Found");
}
static boolean astar(int[][] map, Node startNode, Node endNode, int row,
int col) {
Node curNode = startNode;
// 将开始节点添加到搜索list
openList.add(startNode);
while (!openList.isEmpty() && !openList.contains(endNode)) {
// 找到当前权值最小的节点
curNode = findMinWeight(openList);
// 找到最短路径
if (curNode.x == endNode.x && curNode.y == endNode.y
|| openList.contains(endNode)) {
while (!(curNode.x == startNode.x && curNode.y == startNode.y)) {
map[curNode.x][curNode.y] = 2;
if (curNode.parentNode != null) {
curNode = curNode.parentNode;
}
}
map[startNode.x][startNode.y] = 2;
return true;
}
// 上下左右
if (curNode.y - 1 >= 0)
check(curNode.x, curNode.y - 1, curNode, endNode, COST_COL);
if (curNode.y + 1 < col)
check(curNode.x, curNode.y + 1, curNode, endNode, COST_COL);
if (curNode.x - 1 >= 0)
check(curNode.x - 1, curNode.y, curNode, endNode, COST_ROW);
if (curNode.x + 1 < row)
check(curNode.x + 1, curNode.y, curNode, endNode, COST_ROW);
// 斜
if (curNode.x - 1 >= 0 && curNode.y - 1 >= 0)
check(curNode.x - 1, curNode.y - 1, curNode, endNode, COST_X);
if (curNode.x - 1 >= 0 && curNode.y + 1 < col)
check(curNode.x - 1, curNode.y + 1, curNode, endNode, COST_X);
if (curNode.x + 1 < row && curNode.y - 1 >= 0)
check(curNode.x + 1, curNode.y - 1, curNode, endNode, COST_X);
if (curNode.x + 1 < row && curNode.y + 1 < col)
check(curNode.x + 1, curNode.y + 1, curNode, endNode, COST_X);
openList.remove(curNode);
closeList.add(curNode);
}
return false;
}
static boolean check(int x, int y, Node curNode, Node endNode, int cost) {
Node node = new A().new Node(x, y, curNode);
if (map[x][y] == 0) {
closeList.add(node);
return false;
}
if (isHave(closeList, x, y) != -1)
return false;
// 查找开启列表中是否存在
int index = -1;
if ((index = isHave(openList, x, y)) != -1) {// 存在
// G值是否更小，是则更新
if ((curNode.g + cost) < openList.get(index).g) {
countG(node, cost);
countF(node);
openList.set(index, node);
}
} else {
// 不存在，添加到开启列表中
node.parentNode = curNode;
count(node, endNode, cost);
openList.add(node);
}
return true;
}
static void count(Node curNode, Node endNode, int cost) {
countG(curNode, cost);
countH(curNode, endNode);
countF(curNode);
}
/**
* 计算G消耗
* @param curNode
* @param endNode
* @param cost
*/
static void countG(Node curNode, int cost) {
if (curNode.parentNode == null)
curNode.g = cost;
else
curNode.g = curNode.parentNode.g + cost;
}
/**
* 计算H估值
* @param curNode
* @param endNode
*/
static void countH(Node curNode, Node endNode){
curNode.h = (Math.abs(curNode.x - endNode.x)
+ Math.abs(curNode.y - endNode.y)) * COST_COL;
}
/**
* 计算F权值
* @param curNode
*/
static void countF(Node curNode) {
curNode.f = curNode.g + curNode.h;
}
/**
* 是否存在某个节点
*
* @param list
* @param x
* @param y
* @return
*/
static int isHave(List<Node> list, int x, int y) {
int length = list.size();
for (int i = 0; i < length; i++) {
Node node = list.get(i);
if (node.x == x && node.y == y)
return i;
}
return -1;
}
/**
* 找最小权值的节点
*
* @param list
* @return
*/
static Node findMinWeight(List<Node> list) {
Iterator<Node> iterable = list.iterator();
Node now = iterable.next();
while (iterable.hasNext()) {
Node next = iterable.next();
if (next.compareTo(now) < 0)
now = next;
}
return now;
}}
运行结果
1 2 2 2 2 2 1 1 1 1
2 0 0 0 0 0 2 0 0 1
1 2 1 1 0 0 0 2 1 1
1 1 2 1 0 0 1 1 2 1
1 1 2 1 0 0 0 1 2 1
1 1 1 1 0 0 0 1 1 1
1 1 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1
值为2的一条线路为最短路径