基础路径规划算法如Dijkstra、A*、D*有哪些特点与区别？

本文共计7388个文字，预计阅读时间需要30分钟。

在一张固定地图上选择一条路径，当存在多条可选路径时，需要选择成本最小的那条路径。我们称这类问题为最短路径选择问题。解决这类问题最经典的算法是Dijkstra算法。

引言

在一张固定地图上选择一条路径，当存在多条可选的路径之时，需要选择代价最小的那条路径。我们称这类问题为最短路径的选择问题。解决这个问题最经典的算法为Dijikstra算法，其通过贪心选择的步骤从源点出发逐步逼近目标点，从而得到起始点与目标点的最短路径。A*算法是在Dijikstra算法上做了改进，使其能够在 开阔空间(也就是四通八达或具有少量障碍物的方格路，可以近似看成各边权重均相等的完全图) 上具有比Dijikstra算法有更好的搜索效率。 但Dijikstra算法和A*算法无法很好的适用动态路网的情况，D*算法却能够很好的适应。Dijikstra算法和A*算法在动态路网中进行重新规划所花费的代价比D*算法高，且效率比D*的低。

ps: 动态路网是指在沿着最优路径前进时，突然出现既定路径中断(地图上的路径变更等)需要进行重新规划的情况。

Dijikstra算法

Dijikstra算法是单向最短路径的查找算法，其要求对应的图必须无负权。其适用有向图和无向图的情况(一般会将无向图的每条边看成两条反向的有向边)。Dijikstra算法是一个贪心算法，每一步都是基于贪心选择策略来进行。

算法描述： 对于具有V个顶点和U条边的图 E=(U,V),算法会将图的顶点V分为两部分，一部分是已遍历过且已找到从源点source到目标点的最短路径的节点集合S。一部分是未遍历过的节点集合K。每次遍历过程都会从未找到最短路径的节点集合K中取出距离源点路径最短的节点n。