0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

Dijkstra算法和A*算法

3D视觉工坊 来源:3D视觉工坊 2023-07-07 10:56 次阅读

在本文中,我们将主要介绍Dijkstra算法和A*算法,从成本计算的角度出发,并逐步展开讨论。

我们将从广度优先搜索开始,然后引入Dijkstra算法,与贪心算法进行比较,最终得出A*算法。

成本计算

在路径规划中,成本计算的一个主要因素是距离。距离可以作为一种衡量路径长短的度量指标,通常使用欧几里得距离、曼哈顿距离或其他合适的距离度量方法来计算。

本文主要介绍欧几里得距离与曼哈顿距离。

568fa43a-1c52-11ee-962d-dac502259ad0.png

广度优先搜索

广度优先搜索(Breadth First Search,BFS )是一种图遍历算法,按照广度方向逐层遍历所有可达节点。

BFS的基本思想是通过维护一个队列,逐层访问节点。

具体步骤如下:

1、将起始节点放入队列中,并标记为已访问。

2、当队列非空时,执行以下步骤:

从队列中取出一个节点,记为当前节点,并标记为已访问。

如果该节点是目标节点,则返回结果。

将当前节点的所有未访问过的邻居节点放入队列中。

3、如果队列为空,则表示已经遍历完所有可达节点,算法结束。

算法框图

56a7ab70-1c52-11ee-962d-dac502259ad0.png

实现效果如下:

56bb7f38-1c52-11ee-962d-dac502259ad0.png

广度优先搜索是一种基本的图搜索算法,它按照图的广度方向逐层遍历所有可达节点。然而,BFS并不考虑边的权重,它只关注节点的层级关系。

因此,对于成本计算来说,BFS并不适用。这里为了实现到目标点的搜索,采用了曼哈顿距离计算初始点的行进成本。

代码

def searching(self):
  """
    Breadth-first Searching.
     path, visited order
    """


  self.PARENT[self.s_start] = self.s_start # 开始节点的父节点
  self.g[self.s_start] = 0 # 开始节点的成本
  self.g[self.s_goal] = math.inf # 目标节点的成本
  # 统一成本搜索,起点的成本是0
  heapq.heappush(self.OPEN,
          (0, self.s_start))


  while self.OPEN:
    _, s = heapq.heappop(self.OPEN) # 弹出最小的元素,优先级较高
    self.CLOSED.append(s) # 将节点加入被访问元素队列,已访问


    if s == self.s_goal: # 到达目标点,即停止
      break


      for s_n in self.get_neighbor(s): # 得到s的邻居节点
        new_cost = self.g[s] + self.cost(s, s_n) 
        # 计算当前邻居节点s_n的成本=g(s)节点s的成本+s到s_n之间的成本


        if s_n not in self.g: # 当前节点没有访问过
          self.g[s_n] = math.inf # 起点到节点s_n的成本为无穷


          if new_cost < self.g[s_n]:  # conditions for updating Cost
                        self.g[s_n] = new_cost
                        self.PARENT[s_n] = s


                        # bfs, add new node to the end of the openset
                        # 将新的节点添加到队列的末尾
                        prior = self.OPEN[-1][0] + 1 if len(self.OPEN) > 0 else 0
            heapq.heappush(self.OPEN, (prior, s_n))
            self.f[s_n] = prior


            return self.extract_path(self.PARENT), self.CLOSED, self.f

Dijkstra算法

迪杰斯特拉算法(Dijkstra)算法是一种单源最短路径算法,用于在加权图中找到从起点到所有其他节点的最短路径。

它基于贪心策略,每次选择当前距离起点最近的节点,并通过该节点更新与它相邻的节点的距离。具体步骤如下:

1、初始化:初始化变量和数据结构,创建一个包含所有节点的集合,并为每个节点设置一个距离值。将起始节点的父节点设置为自身,将起始节点的距离值设置为0,其他节点的距离值设置为无穷大(表示尚未找到最短路径)。将起始节点以成本0的优先级推入优先队列OPEN中。

2、主循环:当OPEN非空时:

弹出优先级最小(成本最低)的节点(_, s),其中_为忽略的值,s为当前节点。

将当前节点s添加到CLOSED列表中,表示已访问。

检查当前节点是否为目标节点。如果是,则跳出循环。

对于当前节点的所有邻居节点,计算通过当前节点到达邻居节点的距离,并与邻居节点的当前距离值进行比较。

如果计算得到的距离值小于邻居节点的当前距离值,则更新邻居节点的距离值为新的更小值并将邻居节点s_n以新的成本作为优先级推入优先队列OPEN中循环结束后,可以通过从目标节点回溯到起始节点,在PARENT字典中提取最短路径。

3、循环结束后,可以通过从目标节点回溯到起始节点,在PARENT字典中提取最短路径。

算法框图

56cae518-1c52-11ee-962d-dac502259ad0.png

实现效果如下:

56f3d3f6-1c52-11ee-962d-dac502259ad0.png

Dijkstra算法能够正确地找到起始节点到其他所有节点的最短路径。它基于贪婪策略,每次选择当前最短路径的节点,通过逐步更新节点的距离值,最终找到最短路径。

代码

  def searching(self):
    """
    Breadth-first Searching.
     path, visited order
    """


    self.PARENT[self.s_start] = self.s_start # 开始节点的父节点
    self.g[self.s_start] = 0 # 开始节点的成本
    self.g[self.s_goal] = math.inf # 目标节点的成本


    # 统一成本搜索,起点的成本是0
    heapq.heappush(self.OPEN,
            (0, self.s_start))


    while self.OPEN: # open_list
      _, s = heapq.heappop(self.OPEN) # 弹出最小的元素,优先级较高
      self.CLOSED.append(s) # 将节点加入被访问元素队列


      if s == self.s_goal: # 到达目标点,即停止
        break


      for s_n in self.get_neighbor(s): # 得到s的邻居节点
        new_cost = self.g[s] + self.cost(s, s_n) # 计算当时邻居节点s_n的成本=g(s)节点s的成本+s到s_n之间的成本


        if s_n not in self.g:  # 当前节点没有访问过
          self.g[s_n] = math.inf # 起点到节点s_n的成本为无穷


        if new_cost < self.g[s_n]:  # 预估节点s_n成本

贪婪算法

贪婪算法(Greedy Algorithm)是一种常见的算法设计策略,其基本思想是在每一步选择当前最优解,而不考虑整体的最优解。贪婪算法通常以局部最优解为目标,通过不断做出局部最优选择来达到整体最优解。

贪婪算法在路径规划问题中,根据当前位置到目标位置的成本作为启发式评估准则,选择最近的节点作为下一步移动的目标。具体步骤如下:

1、初始化:设置起始节点,将起始节点的父节点设置为起始节点本身,并将起始节点和目标节点的成本初始化为无穷大,将起始节点加入开放列表,其优先级根据启发式函数值确定。

2、主循环:当OPEN非空时:

从OPEN列表中弹出具有最高优先级的节点,将其加入已访问列表(CLOSED)中。

检查当前节点是否为目标节点。如果是,则跳出循环。

获取当前节点的邻居节点,从邻居节点中选择距离目标节点最近的节点,将选择的节点加入OPEN列表,并将该节点作为当前节点。

3、循环结束后,通过从目标节点回溯到起始节点,在PARENT字典中提取最短路径。

算法框图

5701cf88-1c52-11ee-962d-dac502259ad0.png

实现效果如下:

5722d656-1c52-11ee-962d-dac502259ad0.png

贪婪最佳优先搜索算法的局限性在于它过度依赖启发式函数(heuristic function),该函数用于估计节点到目标节点的距离。

由于启发式函数的估计可能不准确或不全面,算法可能会在搜索过程中陷入局部最优解,导致得到的路径并不是最短的。

代码

 def searching(self):
    self.PARENT[self.s_start] = self.s_start # 开始节点的父节点
    self.h[self.s_start] = math.inf # 开始节点的成本
    self.h[self.s_goal] = math.inf # 目标节点的成本
    # heappush 函数能够按照 h 值的大小来维护堆的顺序,这意味着self.OPEN堆中的节点将按照 h 值的升序排列,h 值较小的节点将具有较高的优先级。
    heapq.heappush(self.OPEN,
            (self.heuristic(self.s_start), self.s_start))


    while self.OPEN: # 当不为空时,即存在未探索区域
      _, s = heapq.heappop(self.OPEN) # 弹出最小的元素,优先级较高
      self.CLOSED.append(s) # 将节点加入被访问元素队列


      if s == self.s_goal: # stop condition,到达目标点,即停止
        break
      for s_n in self.get_neighbor(s): # 得到s的邻居节点
        new_cost = self.heuristic(s_n) + self.cost(s, s_n) # 计算当时邻居节点s_n的成本=g(s)节点s的成本+s到s_n之间的成本


        if s_n not in self.h: # 下一个节点没有遍历过
          self.h[s_n] = math.inf # 起点到节点s_n的成本为无穷


        if new_cost < self.h[s_n]:  # 预估节点s_n成本

A*算法

Dijkstra算法没有考虑到目标节点的位置,因此可能会浪费时间在探索那些与目标节点相距较远的方向上。贪婪最佳优先搜索算法会优先选择离目标节点更近的节点进行扩展。

这样做的好处是它能够更快地找到到达目标节点的路径,但无法保证找到的路径是最短路径,因为它只考虑了节点到目标节点的距离,没有综合考虑到起点到目标节点的实际距离。

A*算法是一种综合了Dijkstra算法和贪婪最佳优先搜索的启发式搜索算法。A*算法同时使用了节点到起点的实际距离(表示为g值)和节点到目标节点的估计距离(表示为h值)。

它通过综合考虑这两个值来评估节点的优先级,并选择优先级最高的节点进行扩展。

A算法通过选择合适的启发式函数来平衡搜索的速度和路径的优劣。当启发式函数满足一定条件时,A算法能够保证找到最短路径。

Dijkstra与贪婪搜索算法对比

在路径规划中,贪婪算法关注的是当前节点到目标节点的距离(启发式函数值),它倾向于选择离目标节点最近的节点作为下一步。

Dijkstra算法关注的是从起点到各个节点的距离,通过不断更新节点的最短距离来逐步扩展路径。

5734a6f6-1c52-11ee-962d-dac502259ad0.png

A*算法的成本函数是由两部分组成:g(n)和h(n)。

g(n)表示从起点到达节点n的实际距离(也称为已知最短路径的代价),表示为g(n)。——Dijkstra

h(n)表示从节点n到目标节点的预估距离(也称为启发式函数),表示为h(n)。——贪婪搜索

A算法使用这两个值来评估节点的优先级。具体地,A算法为每个节点计算一个估计总代价f(n),计算公式为:

576b94a4-1c52-11ee-962d-dac502259ad0.png

其中,f(n)表示从起点经过节点n到达目标节点的预估总代价。

5775d82e-1c52-11ee-962d-dac502259ad0.png

具体步骤如下:

1、初始化:设置起始节点,将起始节点的父节点设置为起始节点本身,将起始节点的成本设置为0,将目标节点的成本设置为无穷大,将起始节点加入到OPEN列表中,使用节点的f值作为优先级。

2、主循环:当OPEN非空时:

从OPEN列表中弹出具有最高优先级的节点,将其加入已访问列表(CLOSED)中。

检查当前节点是否为目标节点。如果是,则跳出循环。

获取当前节点的邻居节点。

对于每个邻居节点,执行以下步骤:

计算从起始节点经过当前节点到达邻居节点的实际距离,即g值。

如果邻居节点不在g字典中,将其g值初始化为无穷大。

如果计算得到的g值小于邻居节点的当前g值,更新邻居节点的g值为新的更小值,并将当前节点设为邻居节点的父节点。

计算邻居节点的启发式函数值,即h值。

将邻居节点加入OPEN列表,并根据f值(f = g + h)确定其优先级。

3、循环结束后,通过从目标节点回溯到起始节点,在PARENT字典中提取最短路径。

算法框图

5796f036-1c52-11ee-962d-dac502259ad0.png

实现效果如下:

57da1b68-1c52-11ee-962d-dac502259ad0.gif

A*算法的效率和质量受启发式函数的选择影响较大。合理选择启发式函数能够提供更好的搜索引导,但不同问题可能需要设计不同的启发式函数。

代码

def searching(self):
    """
    A_star Searching.
     path, visited order
    """


    self.PARENT[self.s_start] = self.s_start # 开始节点的父节点
    self.g[self.s_start] = 0 # 开始节点的成本
    self.g[self.s_goal] = math.inf # 目标节点的成本


    # heappush 函数能够按照 f 值的大小来维护堆的顺序,这意味着self.OPEN堆中的节点将按照 f 值的升序排列,f 值较小的节点将具有较高的优先级。
    heapq.heappush(self.OPEN,
            (self.f_value(self.s_start), self.s_start))


    while self.OPEN: # 当不为空时,即存在未探索区域
      _, s = heapq.heappop(self.OPEN) # 弹出最小的元素,优先级较高
      self.CLOSED.append(s) # 将节点加入被访问元素队列


      if s == self.s_goal: # stop condition,到达目标点,即停止
        break
      for s_n in self.get_neighbor(s): # 得到s的邻居节点
        new_cost = self.g[s] + self.cost(s, s_n) # 计算当时邻居节点s_n的成本=g(s)节点s的成本+s到s_n之间的成本


        if s_n not in self.g:
          self.g[s_n] = math.inf # 起点到节点s_n的成本为无穷


        if new_cost < self.g[s_n]:  # 预估节点s_n成本

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 算法
    +关注

    关注

    23

    文章

    4608

    浏览量

    92844
  • Dijkstra
    +关注

    关注

    0

    文章

    13

    浏览量

    8441

原文标题:自动驾驶 | 路径规划算法Dijkstra与A*

文章出处:【微信号:3D视觉工坊,微信公众号:3D视觉工坊】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    自动驾驶路径规划威廉希尔官方网站 之A-Star算法

    Astar算法Dijkstra算法的效果差不多,但Astar算法访问的节点数明显比Dijkstra算法
    发表于 03-23 12:26 3483次阅读

    经典算法大全(51个C语言算法+单片机常用算法+机器学十大算法

    系列,则更是最后写了6篇文章,成为了国内最为经典的红黑树教程。十三个经典算法集锦  一、A*搜索算法  一(续)、A*,Dijkstra,B
    发表于 10-23 14:31

    使用dijkstra算法的准备工作

    使用dijkstra算法dijkstra算法是特别经典的路径分析算法,文章中的算法也确实很容易
    发表于 05-23 08:13

    基于OpenHarmony的智能助老服务系统

    原理有了一定的认识和理解。其次介绍 了 Dijkstra 算法A*算法的发展,然后分析了两者的原理和实现过程,指出了两者在 特定场景下的缺点,并对两者做了对比。然后研究了描述地图的
    发表于 09-22 22:23

    基于Dijkstra的PKI交叉认证路径搜索算法

    针对网状型公钥基础设施(PKI)信任模型认证路径的不确定性,提出一种基于Dijkstra 算法的PKI 交叉认证路径搜索算法。该算法根据PKI 系统中配置的认证路径搜索服务器,结合信任
    发表于 03-20 15:59 20次下载

    路由算法详解

    路由算法详解1. 引言 2. 路由器基础知识 3. LS算法 4. 示例:Dijkstra算法 5. DV算法 6. 分级路由
    发表于 08-06 09:36 5497次阅读
    路由<b class='flag-5'>算法</b>详解

    改进的Dijkstra算法在灾害决策系统中的应用_赵慧娟

    改进的Dijkstra算法在灾害决策系统中的应用_赵慧娟
    发表于 03-19 11:30 0次下载

    基于有向非负极图数据DIJKSTRA算法

    传统的Dijkstra算法只是针对起点和终点求解最短路径,而不能解决从起点出发,经过必经节点集,到达终点的无重复节点且无回路的最短路径问题。为此,在有向非负权图中,提出了Dijkstra算法
    发表于 11-03 15:22 8次下载
    基于有向非负极图数据<b class='flag-5'>DIJKSTRA</b><b class='flag-5'>算法</b>

    基于Dijkstra最短路径的抽样算法

    针对社交网络中随机抽样算法抽样结果不能很好地代表原始网络的问题,设计了一种基于Dijkstra最短路径的抽样算法。首先,利用Dijkstra算法
    发表于 12-17 11:40 1次下载
    基于<b class='flag-5'>Dijkstra</b>最短路径的抽样<b class='flag-5'>算法</b>

    基于改进Dijkstra的端端密钥协商最优路径选择算法

    针对量子密钥分发(QKD)网络端端密钥协商路径选择问题,设计了一种基于改进Dijkstra算法的端端密钥协商最优路径选择算法。首先,基于有效路径策略,剔除网络中的失效链路;然后,基于最短路径策略
    发表于 12-27 16:58 0次下载
    基于改进<b class='flag-5'>Dijkstra</b>的端端密钥协商最优路径选择<b class='flag-5'>算法</b>

    基于Dijkstra算法的配电网孤岛划分

    针对传统孤岛划分方法存在的没有合理利用电网拓扑结构、算法搜索性能差等问题,提出了一种基于Dijkstra算法的配电网孤岛划分方法。首先,采用Dijkstra
    发表于 03-05 11:02 1次下载

    使用英特尔编译器优化Dijkstra最短路径图算法

    我们使用英特尔®Cilk™Plus阵列表示法和OpenMP *并行程序的优化,在Linux *上优化了Dijkstra最短路径图算法的版本。
    的头像 发表于 11-13 06:13 2508次阅读

    基于STM32的A*(A星)寻路算法实现

    STM32 + LED点阵屏 实现A算法寻路A算法最初发表于1968年。它可以被认为是Dijkstra
    发表于 12-27 19:15 14次下载
    基于STM32的<b class='flag-5'>A</b>*(<b class='flag-5'>A</b>星)寻路<b class='flag-5'>算法</b>实现

    全文详解A*算法及其变种

    相比于 BFS,Dijkstra 算法新增了cost_so_far用于记录从当前点current到起点的路径所需要的代价,并将搜索规则改为优先搜索cost最小的点.如下图所示,,Dijkstra
    发表于 09-14 09:25 1956次阅读
    全文详解<b class='flag-5'>A</b>*<b class='flag-5'>算法</b>及其变种

    中国铁路网的Dijkstra算法实现案例

    该项目分别在DE1-SOC开发板的FPGA和HPS上实现了Dijkstra算法,能在中国铁路网中找到两站之间的最短距离和路线。
    的头像 发表于 04-09 11:10 587次阅读
    中国铁路网的<b class='flag-5'>Dijkstra</b><b class='flag-5'>算法</b>实现案例