首页 > 编程语言 >机器人路径规划:基于迪杰斯特拉算法(Dijkstra)的机器人路径规划(提供Python代码)

机器人路径规划:基于迪杰斯特拉算法(Dijkstra)的机器人路径规划(提供Python代码)

时间:2024-03-20 18:30:11浏览次数:29  
标签:index 路径 dist Python self 机器人 算法 节点

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。它可以找到从一个起始节点到其他所有节点的最短路径。

一、算法介绍


Dijkstra算法采用贪心策略,通过逐步扩展已知最短路径集合来逐步确定最短路径。它使用一个距离数组来记录从起始节点到其他节点的当前最短距离,并通过不断更新距离数组来逐步确定最短路径。

二、算法描述


1. 创建一个距离数组dist[],用于记录起始节点到其他节点的当前最短距离。初始化dist[],将起始节点的距离设为0,其他节点的距离设为无穷大。
2. 创建一个集合visited[],用于记录已经确定最短路径的节点。
3. 重复以下步骤,直到visited[]包含所有节点:
   a. 从未访问的节点中选择一个距离最小的节点u,将其加入visited[]。
   b. 对于节点u的所有邻居节点v,更新其距离数组dist[]:
      - 如果通过节点u可以获得更短的路径,则更新dist[v]为新的最短距离。
4. 最终,dist[]数组中记录了起始节点到其他所有节点的最短距离。

三、算法流程


1. 初始化dist[]数组和visited[]集合。
2. 将起始节点的距离设为0。
3. 重复以下步骤,直到visited[]包含所有节点:
   a. 从未访问的节点中选择一个距离最小的节点u。
   b. 将节点u加入visited[]。
   c. 对于节点u的所有邻居节点v,更新其距离数组dist[]:
      - 如果通过节点u可以获得更短的路径,则更新dist[v]为新的最短距离。
4. 返回dist[]数组作为最短路径结果。

四、部分代码

import matplotlib.pyplot as plt
import math

show_animation = True


class Dijkstra:

    def __init__(self, ox, oy, resolution, robot_radius):
        """
        Initialize map for a star planning

        ox: x position list of Obstacles [m]
        oy: y position list of Obstacles [m]
        resolution: grid resolution [m]
        rr: robot radius[m]
        """

        self.min_x = None
        self.min_y = None
        self.max_x = None
        self.max_y = None
        self.x_width = None
        self.y_width = None
        self.obstacle_map = None

        self.resolution = resolution
        self.robot_radius = robot_radius
        self.calc_obstacle_map(ox, oy)
        self.motion = self.get_motion_model()

    class Node:
        def __init__(self, x, y, cost, parent_index):
            self.x = x  # index of grid
            self.y = y  # index of grid
            self.cost = cost
            self.parent_index = parent_index  # index of previous Node

        def __str__(self):
            return str(self.x) + "," + str(self.y) + "," + str(
                self.cost) + "," + str(self.parent_index)

五、部分结果

六、完整Python代码

见下方联系方式

标签:index,路径,dist,Python,self,机器人,算法,节点
From: https://blog.csdn.net/2401_82411023/article/details/136885190

相关文章

  • python基础 1
    #coding:utf-8##号表示单行注释,被注释的代码不会被运行ctrl+/进行注释#python中的输出语句#print("hellodcs38")#print是python当中默认的打印方式name='helloworld'#定义了一个变量name,将=号右边的"helloworld"字符串赋值给到name这个变量##在pyth......
  • python coding with ChatGPT 打卡第23天| 回溯算法:理论基础
    文章目录视频讲解回溯法的效率解决的问题如何理解回溯法回溯框架视频讲解回溯算法理论篇回溯是递归的副产品,只要有递归就会有回溯。回溯法的效率回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案,如果想让回溯法高效一些,可以加一些剪枝的操作,但也改不了回溯法......
  • 自学Python需要多久才能学会?
    这个问题很难给到一个具体的数字,Python的自学取决于Python的基础知识掌握程度,学习的意愿以及学习的能力。下面我们分布来看。有编程基础的人自学python需要多久?Python的语法时自学的关键,而python的语法和其他编程语言也是有很多相似之处的,比如条件判断和循环、字符串和集......
  • 【Python实用教程】使用Python快速查找电脑里的文件
    电脑随着使用时间的增加,我们在电脑中储存的文件变得越来越多。当这个时候你想要查找一个文件,但是又忘记了文件的位置在哪,想通过排序查找这个文件,又由于文件夹里面文件太多,根本找不到。如果使用电脑自带的搜索,时间又很长。那么在面对海量的存储文件,其实我们可以通过其实我......
  • 【Python使用】python高级进阶知识md总结第5篇:获取进程编号,1. 获取进程编号的目的【
    python高级进阶全知识知识笔记总结完整教程(附代码资料)主要内容讲述:操作系统,虚拟机软件,Ubuntu操作系统,Linux内核及发行版,查看目录命令,切换目录命令,绝对路径和相对路径,创建、删除文件及目录命令,复制、移动文件及目录命令,终端命令格式的组成,查看命令帮助。HTTP请求报文,HTTP响应报文......
  • 路径目录
    一、目录与路径绝对路径与相对路径绝对路径:由根目录/起始的文件名或目录名称。例:/home/etc相对路径:相对于目前路径的写法。例:./home/etc如果是在写程序(shellscripts)来管理系统的条件下,务必使用绝对路径的写法。如果使用相对路径在程序当中,则可能由于你执行的工作环境......
  • Python实战-飞机大战
    plane_sprites:importrandomimportpygameSCREEN_RECT=pygame.Rect(0,0,480,700)游戏基类:classGameSprite(pygame.sprite.Sprite):def__init__(self,img_name,speed=1):super().__init__()self.image=pygame.image.load(img_name)self......
  • Java调用python服务接口https遇到证书问题的具体解决
    是这样的,大概前一段时间做过一个业务,一直没有记录下来就是我们的算法部,封装好了一系列的算法,然后是python写的。而我们需要用Java去调用他们的方法。如何处理这个问题呢就是我在python里面写了一个rest-api,暴露出几个接口,供Java这边调。但是不知道为什么算法部当时那边弄了个......
  • 湖南克鲁斯机器人齿轮箱维修,高效可靠!
    一、克鲁斯机器人齿轮箱的常见故障类型齿轮磨损:长时间的高负荷运转会导致齿轮磨损,进而影响传动效率和精度。轴承故障:轴承损坏或润滑不良可能导致齿轮箱运转不平稳,产生噪音和振动。密封失效:克鲁斯机器人齿轮箱密封件老化或损坏可能导致润滑油泄漏,影响齿轮和轴承的润滑效果。......
  • 【python】Python实现梯度下降算法
    (文末包含完整代码)导入需要的包importnumpyasnpimportmatplotlib.pyplotasplt定义函数defget_y(x):y=x**2+x*2+1returny计算梯度defget_gradient(x):getgradient=2*x+2returngetgradient采用梯度下降计算函数最小值时自......