A*（A-Star）算法也是一种在图中求解最短路径问题的算法。
由狄克斯特拉算法发展而来，狄克斯特拉算法会从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径。
也就是说，一些离终点较远的顶点的最短路径也会被计算出来，但是这部分其实是无用的。
与迪克斯特拉算法不同的是，A*就会预先估算一个值，并利用这个值省去一些无用的计算。
A*.jpg
图示顶点从A-Z，备注：A2,A3,A4也是顶点，只是字母不够用了，用数字区分。
设S为起点，G为终点，尝试用狄克斯特拉算法来求该图中最短路径。
在图中每个方框属于一个顶点，假设每个相邻两个顶点的距离（权重）都为1。
以这个设定为前提，用狄克斯特拉算法来求最短路径：
用狄克斯特拉算法求最短路径的结果如下图所示：
dks.jpg
从M搜索到A的最小权重路径权重是8，最短路径的顶点顺序是：
M - L - K - J - H - Z - C - B - A
狄克斯特拉算法只根据起点到候补顶点的距离来决定下一个顶点。因此无法发现M-N -O 方向和H - I - G方向的两条路径离终点越来越远，同样会继续搜索。
而A*算法不仅会考虑从起点到候补顶点的距离，还会考虑从点钱所在顶点到终点的估算距离。这个估算距离可以自由设定。这里用顶点到终点的直线距离四设五入后的值。
接下来就用A*算法来求解：
现将起点M设置为已经搜索过的状态，分别计算起点周围每个顶点的权重。
顶点N到终点的估算距离 = √（16 + 25）= 6.4 四舍五入 = 6
顶点N的权重 = 从起点M到顶点N的顶点距离 加上 顶点N到终点的距离估算距离 = 1 + 6 = 7
顶点Q到终点的估算距离 = √ （9 + 16）= 5
顶点Q的权重 = 从起点M到顶点Q的距离 加上顶点Q到终点的估算距离 = 1 + 5 = 6
顶点L到终点的估算距离= √ （ 16 + 9 ） = 5
顶点L的权重 = 从起点M到顶点L的距离 加上 顶点L到终点的估算距离 = 1 + 5 = 6
接下来选择权重最小的顶点来继续搜索，选择Q或者L都可以，这里选择Q，
选择Q来搜索时候，这里会求解R的权重
顶点R的权重 = 从起点M到顶点R的距离 加上 顶点R 到终点的估算距离= 2 + 4 = 6
接下来可以选择顶点R或者顶点L继续搜索，这里选择顶点R,
选择顶点R搜索时候，这里会求解S的权重，
顶点S的权重 = 从起点M到顶点S的距离 加上 顶点S到终点的估算距离 = 3 + 4 = 7
接下来选择权重最小的顶点L来进行搜索，求解K的权重
顶点K的权重 = 2 + 4 = 6
接下来选择权重最小的顶点K来进行搜索，求解J的权重
顶点J的权重= 3 + 4 = 7
接下来可以选的起点是N，S, J，权重都为7，这里随机选择N来搜索，求解顶点O的权重
顶点O的权重 = 2 + 7 = 9
接下来可选择的起点是S和J，权重都为7，这里随机选择S来搜索，求解T的权重
顶点T的权重 = 4 + 4 = 8
接下来选择J来搜索，求解H的权重
顶点H的权重 = 4 + 4 = 8
接下来可选择的顶点是T 和 H ，这里随机选择T
...
....
搜索完毕结果如下图：
end.jpg
求得最终的M - A的最短路径权重为8，顺序为M - L - K - J - H - Z - C - B - A 。
在A*算法中显然少搜索了两个远离终点方向的路线M-N-O 和J - H - I。效率比狄克斯特拉算法高。
但是如果这个顶点到终点的估算距离无法大概估算，那么就不能用A*算法。
网友评论