路径规划算法1.2图搜索算法——经典Dijkstra和A*搜索算法前言广度优先搜索Dijkstra算法权图Dijkstra算法统一cost search地图搜索算法贪婪最优搜索和启发函数A*算法
前言
路径规划算法1.1给出了初始的图检索算法，可视化(VG )。 这次记录了基于图检索的2种经典寻径算法Dijkstra和A*。 这两种算法深深地影响了后续的grid-based算法。
这里使用Red Blob Games的主页进行叙述。
宽度优先搜索这里又提到了宽度优先搜索方法，这个概念是从图论中引出的。 BFS意味着对图(树)上的每个节点展开，每个方向上的展开优先级一致，被扫描的每个节点都可以获得其连接信息。
以上是遍历全部图的过程：
将起点列入先进先出列表q。 取出q中的节点(第一个是起点)。 访问该节点的所有相邻节点并将其放入q中(已排队的节点将不再可访问)，然后节点展开完成。 取出下一个节点，重复上述过程直到节点消失。 在节点展开过程中，记录每个节点和要访问的节点将形成节点之间的路径。
对于寻径算法，不需要展开所有节点，而是可以在找到目标节点时提前退出。
(图源Red Blob Games )
戴克斯特拉法戴克斯特拉法戴克斯特拉法戴克斯特拉法是宽度优先搜索算法(BFS(Breadth-Firstsearch，BFS ) )，但该戴克斯特拉法为搜索提供了从起点到节点的cost的指南
对于以上的权利图，以a为起点的算法流程如下：
创建用于记录到达节点的两个队列u、用于记录未到达节点的q以及用于记录起点到其他每个点的最短距离的数组array。 对U={A}、Q={B，c，d，e，F}、array={ 5，10，15，inf，inf}进行初始化()在起点不能到达某个节点的情况下，距离为inf ) q中最接近a
在阵列中AB的距离最小，从q中取出b放入U={A，B}，BE，在阵列中用A-B-E的距离=13inf更新阵列={ 5，10，15，13，inf}
交流距离最小，从q中取出c放入U={A，b，C}，光盘相连，阵列中A-C-D的距离为1415，更新阵列={ 5，10，14，13，inf}
AE距离最小，从q中取出e放入U={A，b，c，E}，ED，EF。 在array中A-B-E-D的距离=14=14，A-B-E-F的距离=22inf，array={ 5，10，
AD距离最小，从q中取出d放入U={A，b，c，e，D}，DF。 在阵列中，用A-B-E-D-F的距离=2022更新阵列={ 5，10，14，13，20 }
节点搜索已完成。 最后的U={A，b，c，e，d，F}，array={ 5，10，14，13，20 }。 中节点顺序表示两点之间的最短路径，阿拉蕾表示a和节点之间的最短距离。
统一成本搜索在地图的寻路地图中寻路时，常用应用Dijkstra思想的Uniform Cost Search算法，优先搜索最短距离节点，通过更新最小距离来寻找最优路径。 不同之处在于，Dijkstra获取到地图中每个节点的最短路径，而统一成本搜索仅获取到目标点的最短路径。
如下图所示，绿色网格的cost是明亮网格的5倍，折线表示具有相同cost的节点。 左图是BFS和Dijkstra算法(实际上是UCS算法)的对比。
(图源Red Blob Games )
*算法贪婪最优搜索启发函数Dijkstra算法在节点搜索时优先选择最小cost节点，贪婪最优搜索Greedy Best First Search使用启发式函数作为搜索标准值：
hurIstIc(s，
g o a l ) = ∥ s − g o a l ∥ heuristic(s, goal)=|s-goal| heuristic(s,goal)=∥s−goal∥其中s表示搜索到的节点，goal表示目标点，|| ||表示范数。
贪婪最有搜索通过启发函数来优先搜索那些距离目标更近的节点，因此相比Dijkstra的速度要快的多：
但是如果起点与目标间存在障碍物，则有可能找不到最优路径：
（图源 Red Blob Games）
前面的贪婪最优搜索没有找到最佳路径的原因，就是由于搜索仅依赖于启发函数（离目标越近越好），而忽略了到达节点的cost。
因此，A*算法融合了Dijkstra和启发函数，在寻路时，搜索那些当前cost与期望的cost最小的节点，其搜索权值函数为：
f ( s ) = c o s t ( s t a r t , s ) + h e u r i s t i c ( s , g o a l ) f(s)=cost(start, s)+heuristic(s, goal) f(s)=cost(start,s)+heuristic(s,goal)
其结果如下图，可以看出Dijkstra、GBF和A*的区别，其中紫色线为cost，粉色线为heuristic.
（图源 Red Blob Games）