• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

(二)【机器人路径规划】Dijkstra算法

人工智能 二进制人工智能 1230次浏览 0个评论

Dijkstra算法

Dijkstra算法是从一个节点到区域各节点的最短路径算法,解决的是最短路径问题。
特点:以起点为中心,向外层层扩展,直到扩展到终点为止。

(二)【机器人路径规划】Dijkstra算法


我们引入两个集合closelist、openlist和两个集合

  • 闭集closelist:记录已求出最短路径的节点。
  • 开集openlist:记录还未求出最短路径的节点。
  • 集合1:记录源节点到各节点的距离
  • 集合2:记录节点对应的父节点

算法操作步骤:

1 首先,将源节点加入集合closelist,其他节点加入到openlist中,计算A到其他节点的距离,源节点无法直接到达的距离记为 ∞ \infty ∞.。
2 从openlist中选出“距离最短的顶点N”,并将顶点N加入到closelist中;同时,从openlist中移除顶点N。
3 重新计算openlist中各个节点到起点A的距离。(重新计算openlist中节点的距离,是由于上一步中确定了N是求出最短路径的顶点,从而可以利用N来更新其他顶点的距离。例如:A到B再到C的距离可能小于A到C的距离,这时应该更改A到C的距离,C的父节点也会改变。)
4 重复上面两个步骤,直到遍历所有的节点。

例子:找A到G的最短路径

(二)【机器人路径规划】Dijkstra算法

1 首先,将源节点A放入闭集合中,并将未求出的节点放入开集合,具体如下:

(二)【机器人路径规划】Dijkstra算法

2 在开集合中选择距离最小的点,显然可以得到此点为B,并将B从开集合删除加入到闭集合中。

(二)【机器人路径规划】Dijkstra算法

3 利用节点B,重新计算所有节点到A的距离(假设此例子中AC<AB+BC,且AC<AB+BF,则C在集合1的距离不变,其父节点也不变,把C从开集中移除加入到闭集,接下去以C遍历其相邻点。)

(二)【机器人路径规划】Dijkstra算法

以此类推直到所有节点都被寻找完,并且闭集合中出现了终点。

(二)【机器人路径规划】Dijkstra算法

最短路径:G==>F==>E==>C==>B==>A


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明(二)【机器人路径规划】Dijkstra算法
喜欢 (0)

您必须 登录 才能发表评论!

加载中……