做网站 网络映射,建站推广什么意思,wordpress文章无法使用,网络营销课程培训图的搜索#xff08;二#xff09;#xff1a;贝尔曼-福特算法、狄克斯特拉算法和A*算法
贝尔曼-福特算法
贝尔曼-福特#xff08;Bellman-Ford#xff09;算法是一种在图中求解最短路径问题的算法。最短路径问题就是在加权图指定了起点和终点的前提下#xff0c;寻找从…图的搜索二贝尔曼-福特算法、狄克斯特拉算法和A*算法
贝尔曼-福特算法
贝尔曼-福特Bellman-Ford算法是一种在图中求解最短路径问题的算法。最短路径问题就是在加权图指定了起点和终点的前提下寻找从起点到终点的路径中权重总和最小的那条路径。 设置A为起点G为终点。 首先设置各个顶点的初始权重 :起点为 0,其他顶点为无穷大(∞)。这个权重表示的是从 A 到该顶点的最短路径的暂定距离。随着计算往下进行,这个值会变得越来越小,最终收敛到正确的数值。 选中候补顶点分别计算这条边从一端到另一端的权重计算方法为“顶点原本的权重边的权重” 计算权重如果计算结果小于顶点的值就更新这个值。
如图计算A到B的权重顶点 B 的权重是无穷大比 9 大所以把它更新为 9。更新时需要记录计算的是从哪个顶点到该顶点的路径。
再次计算B到A的权重B 的权重为 9从 B 到 A 的权重便为 9918。与顶点 A 现在的值 0 进行比较因为现在的值更小所以不更新。
A到C的路径计算同理。接下来计算B到C的路径。 在进行B-C计算时发现A-C-B的路径比A-B的路径更短于是更新如下 接着对所有的边进行更新操作 更新完所有的边后,第 1 轮更新就结束了。接着,重复对所有边的更新操作,直到权重不能被更新为止。 第二轮更新后顶点 B 的权重从 8 变成了 7顶点 E 的权重从 9 变成了 8。接着进行第三轮更新。发现第三轮更新后所有顶点的权重不再更新操作结束。算法的搜索流程也就此结束我们找到了从起点到其余各个顶点的最短路径。 根据搜索结果可知从起点 A 到终点 G 的最短路径是 A-C-D-F-G权重为 14。
将图的顶点数设为 n、边数设为 m。该算法经过 n 轮更新操作后就会停止而在每轮更新操作中都需要对各个边进行 1 次确认因此 1 轮更新所花费的时间就是 O(m)整体的时间复杂度就是 O(nm)。
有向图与以上步骤相同只需按照边所指向的方向来计算即可。
计算最短路径时,边的权重代表的通常都是时间、距离或者路费等,因此基本都是非负数。不过,即便权重为负,贝尔曼 - 福特算法也可以正常运行。
如果闭环中有负数权重就不存在最短路径。
狄克斯特拉算法
狄克斯特拉( Dijkstra)算法也是求解最短路径问题的算法,使用它可以求得从起点到终点的路径中权重总和最小的那条路径。 仍然设A为起点G为终点。 与贝尔曼-福特算法相同将起点设置为0其他顶点设置为无穷大。设置从A出发寻找可以从目前所在的顶点直达且尚未被搜索过的顶点,此处为顶点 B 和顶点 C,将它们设为下一步的候补顶点。 计算后结果如上图。计算方法是“目前所在顶点的权重目前所在顶点到候补顶点的权重”。与贝尔曼-福特算法类似。 **从候补顶点中选出权重最小的顶点。**此处 B 的权重最小,那么路径 A-B 就是从起点 A 到顶点 B 的最短路径。确定了最短路径移动到顶点B。 将可以从顶点B直达的顶点设为新的候补顶点于是顶点 D 和顶点 E 也成为了候补。目前有三个候补顶点 C、D、E。 同理。在计算B到各顶点值后比较各点值大小。其中B-C点的权重为85所以不更新。确认了最短路径移动到顶点D。计算D-E的权重为75发现并不需要更新它。现在有两个候补顶点C和E权重均为5选择哪一个向下计算都可以。以下先选择C。 算出F点的权重后回到E进行计算。 此时算出G点的权重为14。再次回到F对F-G的权重进行计算得2014。故G的最小权重为14。 最终得到的这颗橙色的树就 是最短路径树,它表示了起点到达各个顶点的最短路径。
比起需要对所有的边都重复计算权重和更新权重的贝尔曼 - 福特算法狄克斯特拉算法多了一步选择顶点的操作这使得它在求最短路径上更为高效。
将图的顶点数设为 n、边数设为 m那么如果事先不进行任何处理该算法的时 间复杂度就是 O( n²)。不过如果对数据结构进行优化那么时间复杂度就会变为 O(m nlogn)。
有负数权重时不能使用狄克斯特拉算法
不存在负数权重时,更适合使用效率较高的狄克斯特拉算法,而存 在负数权重时,即便较为耗时,也应该使用可以得到正确答案的贝尔曼 - 福特算法。
A*算法
A*(A-Star)算法也是一种在图中求解最短路径问题的算法,由狄克斯特拉算法发展而来。
狄克斯特拉算法会从离起点近的顶点开始按顺序求出起点到各个顶点的最短路径。也就是说一些离终点较远的顶点的最短路径也会被计算出来但这部分其实是无用的。与之不同A* 就会预先估算一个值并利用这个值来省去一些无用的计算。 先使用狄克斯特拉算法来求解以上迷宫的最短路径。
将迷宫看作是一个图其中每个方块都是一个顶点各顶点间的距离权重都为 1。 用狄克斯特拉算法求最短路径的结果会如上图所示方块中的数字表示从起点到该顶点的距离权重蓝色和橙色的方块表示搜索过的区域橙色方块同时还表示从 S 到 G 的最短路径。
狄克斯特拉算法只根据起点到候补顶点的距离来决定下一个顶点。因此它无法发现蓝色箭头所指的这两条路径其实离终点越来越远同 样会继续搜索。 而A* 算法不仅会考虑从起点到候补顶点的距离, 还会考虑从当前所在顶点到终点的估算距离。 这个估算距离可以自由设定,此处我们用的是将顶点到终点的直线距离四舍五入后的值。
由人工预先设定的估算距离被称为**“距离估算值”。如果事先根据已知信息设定合适的距离估算值,再将它作为启发信息辅助计算,搜索就会变得更加高效。这样的算法也成为启发式算法**。 从起点开始搜索。分别计算起点周围每个顶点的权重。计算方法是“从起点到该顶点的距离”方块左下加上 “距离估算值”方块右下。 选择一个权重最小的顶点用橙色表示并继续向后搜索。 按照顺序继续向下搜索。 搜索完毕如上图。可以看出基本不回去计算离终点太远的区域。
如果我们能得到一些启发信息即各个顶点到终点的大致距离这个距离不需是准确的值我们就能使用 A* 算法。当然有时这类信息是完全无法估算的这时就不能使用 A* 算法。
距离估算值越接近当前顶点到终点的实际值A* 算法的搜索效率也就越高反过来如果距离估算值与实际值相差较大那么该算法的效率可能会比狄克斯特拉算法的还要低。如果差距再大一些甚至可能无法得到正确答案。
不过,当距离估算值小于实际距离时,是一定可以得到正确答案的(只是如果没有设定合适的距离估算值,效率会变差)。
A* 算法在游戏编程中经常被用于计算敌人追赶玩家时的行动路线等但由于该算法的计算量较大所以可能会使游戏整体的运行速度变慢。因此在实际编程时需要考虑结合其他算法或者根据具体的应用场景做出相应调整。
参考资料我的第一本算法书 (石田保辉 宮崎修一)
