前言:
目前我们对“algorithm运算法则”大体比较看重,小伙伴们都想要了解一些“algorithm运算法则”的相关内容。那么小编在网络上收集了一些有关“algorithm运算法则””的相关文章,希望咱们能喜欢,你们一起来学习一下吧!在本文中,我们将主要介绍Dijkstra算法和A*算法,从成本计算的角度出发,并逐步展开讨论。我们将从广度优先搜索开始,然后引入Dijkstra算法,与贪心算法进行比较,最终得出A*算法。
成本计算
在路径规划中,成本计算的一个主要因素是距离。距离可以作为一种衡量路径长短的度量指标,通常使用欧几里得距离、曼哈顿距离或其他合适的距离度量方法来计算。本文主要介绍欧几里得距离与曼哈顿距离。
广度优先搜索
广度优先搜索(Breadth First Search,BFS )是一种图遍历算法,按照广度方向逐层遍历所有可达节点。
BFS的基本思想是通过维护一个队列,逐层访问节点。具体步骤如下:
1.将起始节点放入队列中,并标记为已访问。
2.当队列非空时,执行以下步骤:
从队列中取出一个节点,记为当前节点,并标记为已访问。如果该节点是目标节点,则返回结果。将当前节点的所有未访问过的邻居节点放入队列中。
3.如果队列为空,则表示已经遍历完所有可达节点,算法结束。
算法框图
实现效果如下:
广度优先搜索是一种基本的图搜索算法,它按照图的广度方向逐层遍历所有可达节点。然而,BFS并不考虑边的权重,它只关注节点的层级关系。因此,对于成本计算来说,BFS并不适用。这里为了实现到目标点的搜索,采用了曼哈顿距离计算初始点的行进成本。
代码
def searching(self): """ Breadth-first Searching. :return: 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中
3.循环结束后,可以通过从目标节点回溯到起始节点,在PARENT字典中提取最短路径。
算法框图
点击【自动驾驶】路径规划算法Dijkstra与A* - 古月居可查看全文
标签: #algorithm运算法则