本文主要是介绍图搜索的经典启发式算法A星(A*、A Star)算法详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 1. 引言
- 2. 广度优先搜索
- 3. Dijkstra 算法
- 4. 启发式优先搜索(Heuristic)
- 4.1 贪心最佳优先搜索
- 4.2 A*搜索
1. 引言
在许多场景中,我们常会遇到一类问题,即“找到一个位置到另一个位置的距离最短(用时最少)的路径”,解决这类问题可以将实际问题映射到一张网络图上,并通过图搜索算法进行求解,这里所说的图搜索算法指的是一系列基于图的算法,而本文将介绍的 A* 算法是其中最为流行的启发式搜索算法,由于 A* 算法结合了其他的基础图搜索的特点,因此本文将从最简单的图搜索算法“广度优先搜索”开始介绍,逐步扩展至 A* 算法。
刚才提到,图搜索算法都需要基于一张图,即将实际的复杂的地图映射成具有固定节点( N o d e s Nodes Nodes)和边( E d g e s Edges Edges)的图( G r a p h Graph Graph),有些边是有方向限制的,为弧 A r c s Arcs Arcs。具体的映射方式很多,即同样一张地图,可以映射成具有 10 10 10 个节点的路线图,也可以映射成 100 100 100 个节点的网格图,在求解过程中,节点数越多的图的求解时间越长,尽管它在一定程度上更能近似于实际情况且更易处理。
2. 广度优先搜索
广度优先搜索(Breadth First Search, BFS)原本是一种在树形数据结构中搜索满足给定属性的节点的算法,后在 1961 年由 CY Lee 等人开发成一种路径搜索算法。
在图搜索中,有一个称为待探索边界 f r o n t i e r frontier frontier 的概念,即图搜索算法基于起点,不断地推进待探索边界,直到该边界触碰到目标点时结束,而由于该算法的特点是在所有方向上平等地探索,因此这个推进待探索边界的过程也被称为“洪水填充 ( f l o o d f i l l ) (flood\ fill) (flood fill)”,该算法由于简单易实现的特性,在许多寻路和图分析场景都有应用,具体如下图所示。
这里的 f r o n t i e r frontier frontier 在代码实现中,是一个待探索的节点队列。队列的初始元素为起始点,基于起始点向前一步探索(下一步可以走到哪些节点),将这些相邻节点扩展到 f r o n t i e r frontier frontier 队列当中,以此类推。每扩展一个节点,记录下该节点的父节点,方便在探索到目标节点后,返回出最优路线。该算法在路径搜索问题上的逻辑如下(伪代码):
frontier = Queue() # 生成一个队列
frontier.put(start) # 以起点作为开始
came_from = dict() # path A->B 存储为 came_from[B] == A
came_from[start] = None # 存储每个节点的上一个位置while not frontier.empty(): # 只要边界队列不为空就循环下去current = frontier.get() # 从边界中取出一个点if current = goal: # 算法终止机制,判断当前节点是否为目标点break # 路径长度限制、遍历的点数、寻到的目标点数......都可以是终止约束for next in graph.neighbors(current): # 基于这个点向相邻的点进行扩展if next not in came_from: # 只要这个扩展的点不曾遍历到,就添加到边界中和已遍历节点集合中frontier.put(next)came_from[next] = current# 获得最有路线
current = goal
path = []
while current != start: path.append(current) # 从目标点回溯到起点current = came_from[current]
path.append(start)
path.reverse() # optional 获得最优路线
3. Dijkstra 算法
前文的广度优先搜索算法,在待探索边界上,以同样的权重按顺序地推进待探索边界,即认为每个边的权重是一致的,但在实际的许多场景中,连接节点的边的权重往往并不相同,显然,在相同的探索深度下,累计代价最小的节点有更大的概率探索到总代价 g ( n ) g(n) g(n) 小的路线,因此基于广度优先搜索的思路,将待探索边界从普通队列变更为优先队列,评估优先顺序时考虑当前节点到起始点的距离(成本)。
常常用 g ( n ) g(n) g(n) 表示从起始节点到 n n n 节点的路径成本。
由于 Dijkstra 算法带有权重地进行探索,改变了 f r o n t i e r frontier frontier 的推进方向,因此有可能出现多次(不同路线)探索同一个节点的情况,对于已经探索过的节点,如果新路线的累积代价更小,则更新该节点的信息。基于 Dijkstra 算法的伪代码如下:
frontier = PriorityQueue() # 生成优先队列
frontier.put(start, 0) # 优先遍历队列中优先度更好(小)的节点
came_from = dict()
cost_so_far = dict() # 存储节点和起点之间的距离
came_from[start] = None
cost_so_far[start] = 0while not frontier.empty():current = frontier.get()if current == goal:breakfor next in graph.neighbors(current):new_cost = cost_so_far[current] + graph.cost(current, next)if next not in cost_so_far or new_cost < cost_so_far[next]:# 判断新的总移动成本,cost_so_far[next] = new_costpriority = new_costfrontier.put(next, priority)came_from[next] = current
与广度优先搜索算法一样,Dijkstra 算法能保证最终找到最优的路径,而 Dijkstra 算法相比广度优先搜索节省了大量的计算时间。
4. 启发式优先搜索(Heuristic)
前面提到的广度优先搜索和 D i j k s t r a Dijkstra Dijkstra 算法适合于找单个起点到多个节点的路径;而如果是找单个起点到具体某一个节点的路径,则由于我们的目标很明确,我们希望从目标节点中获取启发信息,例如在探索节点时,优先探索距离目标点更近的节点。当然,这里的“距离近”并不一定是真实距离,它为待探索边界的优先顺序提供了一定的启发信息。
例如:这里用当前点与目标点之间的曼哈顿距离作为启发信息:
def heuristic(a, b):# Manhattan distance on a square gridreturn abs(a.x - b.x) + abs(a.y - b.y) # 这里用的简答的曼哈顿距离
4.1 贪心最佳优先搜索
在启发式搜索方法中,最简单易实现的是贪心最佳优先搜索(Greedy Best First Search, GBFS),即优先探索距离目标最“近”的节点,在一些情况下,该算法的效率极高,但对于较为复杂(待障碍物等)的图搜索问题,该算法往往不能保证找到最优的路径。
算法逻辑其实就是在广度优先搜索 B F S BFS BFS 算法上,增加启发信息 h e u r i s t i c heuristic heuristic,具体的伪代码如下:
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
came_from[start] = Nonewhile not frontier.empty():current = frontier.get()if current == goal:breakfor next in graph.neighbors(current):if next not in came_from:priority = heuristic(goal, next)frontier.put(next, priority)came_from[next] = current
对于节点到目标点的估计距离,常常用符号 h ( n ) h(n) h(n) 进行表示。
4.2 A*搜索
前面提到的三种图搜索算法都各有优势,而 A* 算法简单而言,就是既学 Dijkstra 算法参考已产生的累积代价,又学了贪心最佳优先搜索参考了与目标节点的启发信息。前者能保证找到最优路线,而后者能提高算法的求解效率。
对于图中的每条边 ( x , y ) (x,y) (x,y),用 d ( x , y ) d(x,y) d(x,y) 表示边的长度,用 h ( x ) h(x) h(x) 表示节点 x x x 到目标点的估计距离,如果恒满足 h ( x ) ≤ d ( x , y ) + h ( y ) h(x)\leq d(x,y)+h(y) h(x)≤d(x,y)+h(y),则可得 f ( x ) = h ( x ) + g ( x ) ≤ g ( x ) + d ( x , y ) + h ( y ) = f ( y ) f(x)=h(x)+g(x)\leq g(x)+d(x,y)+h(y)=f(y) f(x)=h(x)+g(x)≤g(x)+d(x,y)+h(y)=f(y),此时 h h h 满足三角不等式,可以称之具备一致性,通过一致性的 h h h 函数,能使 A* 算法一定找到最优路径。
具体 A* 算法的计算逻辑伪代码如下:
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0 # 与起点的距离while not frontier.empty():current = frontier.get()if current == goal:breakfor next in graph.neighbors(current):new_cost = cost_so_far[current] + graph.cost(current, next)if next not in cost_so_far or new_cost < cost_so_far[next]:cost_so_far[next] = new_costpriority = new_cost + heuristic(goal, next) # 与目标点的估计距离frontier.put(next, priority)came_from[next] = current
A* 算法综合考虑 g ( n ) g(n) g(n) 和 h ( n ) h(n) h(n),如果 A* 算法中当前点到目标点的估计距离相对于与起点的实际距离很小,与起点的距离主导边界队列的搜索顺序,则 A* 算法表现出 D i j k s t r a Dijkstra Dijkstra 算法的性能;反之,则表现出类似 G B F S GBFS GBFS 的搜索性能。
总体而言, B F S BFS BFS 无差别地探索所有的路径,但是复杂度太高,但适用于目标节点未知(寻宝)的情况; D i j k s t r a Dijkstra Dijkstra 算法能保证找到最短路径,但因为没有用到目标点的信息,在探索方向上会花费大量时间; G B F S GBFS GBFS 仅向着目标点优化,算法的效率很高,但是不能保证找到最优路径;而 A ∗ A^* A∗ 算法既考虑了和起点的距离,也考虑了和目标点的距离(两者求和),在预估函数满足一定条件下,能保证找到最优解,效率比 D i j k s t r a Dijkstra Dijkstra 算法高一些,比 G B F S GBFS GBFS 算法低一些。
这篇关于图搜索的经典启发式算法A星(A*、A Star)算法详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!