====================如果你没接触过编程，可以忽略此部分===================
我们来看一看具体过程
A*算法之所以带*，是因为这个星代表着估价函数，A星算法可以看作是一种带有估价函数的广度优先算法。
估价函数如此重要，让我们来详细认识一下他：
上图每个格子中都有三个数字，他们是左上角的f,左下角的g 右下角的h，n代表这个格子结点。
f(n) = g(n) + h(n)
f(n)是节点n的总估价值
g(n)就是在地图中从初始点到该节点走过来的花费
h(n)就是从该节点到终点的估算代价。
其中g(n)是已知的。我们需要提供的是h(n)估价函数
常用估价函数有：
设当前点的坐标为(x,y)，结束点的坐标为(xB,yB)
1）Manhattan distance（曼哈顿距离）：
曼哈顿距离是标准的启发式函数，即：两点在南北方向上的距离加上在东西方向上的距离。之所以被称为曼哈顿，是因为它看起来像计算城市中从一个街道走到另外一个街道的步数，由于城市中是不可能沿对角线斜着穿过建筑物的，所以该方法很适合估算街道多的城镇地图。
公式：
h(n) = abs(x-xB) + abs(y-yB )；
2）对角线距离：
对角线距离比较适合寻路中允许对角运动的，该公式很适合野外，树林，障碍物较少而且零散的地图。
公式：
h(n)=max(abs(x-xB)，abs(y-yB))
3）Euclid distance (欧几里德距离)：
如果寻路中单位可以沿着任意角度移动，那么可以使用直线距离。也就是我们俗话说的迷宫的道路可以斜着走。
公式：
h(n) = sqrt((x-xB)^2 + (y-yB)^2); （南北的平方+东西的平方）开方
该函数比较适合地图障碍物不均，有的地方多，有的地方少，有横平树直的街道，也有可斜走的野外地图。
我们现在已经知道估价函数是什么东西了，上图中运用的是曼哈顿距离估价函数，方便计算，曼哈顿只需将当前格与目标点的上下步数和南北步数相加即是估价值，这个h(n)值写在格子右下角，这个格已经走过的步数g(n)写在左下角，一步等于10分，斜着走一步等于14分,最后把f(n) = g(n)+h(n)两者的合写在左上角做为该格子的总估价值f(n)，总估价值越低的格子，越有可能是到达终点的最短路径的必经之路。
我们来看A星算法的具体行动步骤：
我们要准备两张列表，开放，封闭列表（open表,close表），上图中绿色为开放列表，蓝色为封闭列表，蓝色中的金色是最终从蓝色列表中选择的最短路径。
准备好两个表之后：
1)将起点周围结点用估价函数f(n)计算预估值并放入Open表中，并将指针标志指向父节点也就是起点。起点本身放入close表中；
2)从Open表中取估价值最小的节点n , 判断如果是终点则结束寻路，否则继续下一条；
3)循环(n节点周围所有结点x)
{
如果( x结点在open表中)
{
如果(新G值 < x在open表中的旧G值)
{
1.更新open表中的x结点的父结点指针指向 n结点,并采用新G值计算x结点的f值
}
}
否则又如果 (x结点在close表)
{
如果(新G值 < x在close表中的旧G值)
{
1.更新close表中的x结点的父结点指针指向 n结点,并采用新G值计算x结点的f值;
2.把X结点取出放入open表;
}
}
否则
{
1.求X结点的估价值;
2.将X结点放入OPEN表中;
}
}
4）把n结点从open表取出，放入close表中;
5）按照估价值将open表中的所有节点排序，使f值最低的节点排在最前面;
6) 返回重新执行步骤2)，直到找到终点，或者open表为空说明在当前地图跟本没有路可以到达终点;
|
楼主
