汕头seo关键词排名,网站背景图片优化,wordpress 手机写文,南平建设局网站移动机器人运动规划 --- 基于图搜索的Dijkstra算法 Dijkstra 算法Dijkstra 算法 伪代码流程Dijkstra 算法步骤示例Dijkstra算法的优劣分析 Dijkstra 算法
Dijkstra 算法与BFS算法的区别就是 : 从容器中弹出接下来要访问的节点的规则不同
BFS 弹出: 层级最浅的原则#xff0c… 移动机器人运动规划 --- 基于图搜索的Dijkstra算法 Dijkstra 算法Dijkstra 算法 伪代码流程Dijkstra 算法步骤示例Dijkstra算法的优劣分析 Dijkstra 算法
Dijkstra 算法与BFS算法的区别就是 : 从容器中弹出接下来要访问的节点的规则不同
BFS 弹出: 层级最浅的原则队列里最下方的元素
Dijkstra 弹出: 代价最小的节点g(n)
g(n) :表示的是从开始节点到当前n节点的代价累加 Dijkstra在扩展的时候同时考虑从n节点扩展所有可扩展节点的代价g()如果某个节点m的代价g(m)比g(n)要小则更新当前代价为g(m) Dijkstra的最优性保证图运行的过程中任何一个被扩展或者访问的节点保证存储的代价g()值是从起点节点开始到当前节点的最小值
Dijkstra 算法 伪代码流程
维护一个优先级队列存储所有被扩展的节点且节点按g()值的大小自动按从小到大排列。
-优先级队列首先为空以起始节点Xs进行初始化-起始节点g(Xs)0并且初始化其它节点的代价为无穷大-循环1、如果队列是空的返回false跳出循环2、弹出优先级队列中代价最小的节点n3、标记节点n为被扩展节点4、如果节点n为目标节点返回true,跳出循环5、找到n节点周围可以扩展的所以节点没被扩展过m6、进行判断 如果g(m)为无穷大说明其它节点也没发现过m,7、则计算 真正的g(m)g(n)Cnm然后将m节点加入到优先级队列中8、进行判断 如果g(m)不为无穷大有值了(说明其它节点发现过mm已经在优先级队列中)9、再次进行判断 如果之前发现m时计算的g(m)比g(n)Cnm大的话10、更新g(m)g(n)Cnm。11、重复循环至步骤1-结束循环Dijkstra 算法步骤示例 以这个图将Dijkstra 算法运行的步骤进行一个示例
1、首先初始化队列将起始节点放入优先级队列中 2、弹出起始节点 3、扩展弹出节点周围的节点 起始节点S可以扩展到子节点d\e\p并且计算各节点的g值 4、将扩展的节点加入到优先级队列中并且进行排序 g§最小放到队列最前面也就是图中的最下面然后是d,最后是e。 5、弹出最小的g值节点 也就是p节点 然后循环至步骤3直至结束
Dijkstra算法的优劣分析
优点完备的如果问题有解一定能找到解最优的找到的解一定是最优的缺点没有目标终点方向的只是比广度搜索多了一个代价值判断如果每个边的代价都是1的话那么就变成了广度搜索。
针对该缺点与之对应的就是启发式搜索例如贪心算法根据到目标的进行一个启发式搜索。
如果Dijkstra的最优性与启发式搜索结合使搜索具有方向性时也就是 A*算法了。
