赞
踩
A*算法
A*(A-Star)算法也是一种在图中求解最短路径问题的算法,由狄克斯特拉算法发展而来。狄克斯特拉算法会从离起点近的顶点开始,按顺序求出起点到各个顶点的最短路径。也就是说,一些离终点较远的顶点的最短路径也会被计算出来,但这部分其实是无用的。与之不同,A*就会预先估算一个值,并利用这个值来省去一些无用的计算。
01
首先,试着用狄克斯特拉算法来求该迷宫中的最短路径吧。
02
将迷宫看作是一个图,其中每个方块都是一个顶点,各顶点间的距离(权重)都为1。
03
以这个设定为前提,用狄克斯特拉算法来求最短路径。
04
用狄克斯特拉算法求最短路径的结果会如上图所示,方块中的数字表示从起点到该顶点的距离(权重),蓝色和橙色的方块表示搜索过的区域,橙色方块同时还表示从S到G的最短路径。
05
狄克斯特拉算法只根据起点到候补顶点的距离来决定下一个顶点。因此,它无法发现蓝色箭头所指的这两条路径其实离终点越来越远,同样会继续搜索。
06
而A*算法不仅会考虑从起点到候补顶点的距离,还会考虑从当前所在顶点到终点的估算距离。这个估算距离可以自由设定,此处我们用的是将顶点到终点的直线距离四舍五入后的值。
07
接下来,就试着用A*算法来求解吧。首先把起点设为搜索完毕状态。搜索完的点都用蓝色表示。
08
分别计算起点周围每个顶点的权重。计算方法是“从起点到该顶点的距离”(方块左下)加上“距离估算值”(方块右下)。
提示
如步骤06中方块右下角的数字所示,由人工预先设定的估算距离被称为“距离估算值”。如果事先根据已知信息设定合适的距离估算值,再将它作为启发信息辅助计算,搜索就会变得更加高效[插图]。这里我们只知道终点所在位置,不知道该如何通往终点,所以使用了直线距离。
09
选择一个权重最小的顶点,用橙色表示。
10
将选择的顶点设为搜索完毕状态。
11
计算搜索完毕的顶点到下一个顶点的权重。
12
选择距离最短的一个顶点。
13
将选好的顶点设为搜索完毕状态。之后重复上述操作,直到到达终点为止。
14
搜索中……
15
搜索完毕。效率比狄克斯特拉算法的高了很多。
解说
如果我们能得到一些启发信息,即各个顶点到终点的大致距离(这个距离不需是准确的值)我们就能使用A*算法。当然,有时这类信息是完全无法估算的,这时就不能使用A*算法。
距离估算值越接近当前顶点到终点的实际值,A*算法的搜索效率也就越高;反过来,如果距离估算值与实际值相差较大,那么该算法的效率可能会比狄克斯特拉算法的还要低。如果差距再大一些,甚至可能无法得到正确答案。
不过,当距离估算值小于实际距离时,是一定可以得到正确答案的(只是如果没有设定合适的距离估算值,效率会变差)。
应用示例
A*算法在游戏编程中经常被用于计算敌人追赶玩家时的行动路线等,但由于该算法的计算量较大,所以可能会使游戏整体的运行速度变慢。因此在实际编程时,需要考虑结合其他算法,或者根据具体的应用场景做出相应调整。
演示:
- import heapq
-
- def heuristic(node, goal):
- # 计算启发式函数(估计从当前节点到目标节点的代价)
- return abs(node[0] - goal[0]) + abs(node[1] - goal[1])
-
- def astar(graph, start, goal):
- open_list = [] # 用于存储待探索的节点
- closed_list = set() # 用于存储已经探索过的节点
- heapq.heappush(open_list, (0, start, None)) # 将起点加入open_list中
-
- while open_list:
- cost, node, parent = heapq.heappop(open_list) # 从open_list中取出开销最小的节点
-
- if node == goal: # 如果当前节点为目标节点,则找到路径
- path = []
- while parent: # 根据父节点不断追溯路径
- path.append(node)
- node, parent = parent
- path.append(start)
- return path[::-1]
-
- closed_list.add(node) # 将当前节点加入已探索列表
-
- for neighbor in graph.get(node, []): # 遍历当前节点的邻居节点
- if neighbor not in closed_list: # 如果邻居节点不在已探索列表中
- neighbor_cost = cost + graph[node][neighbor] # 计算到达邻居节点的开销
- heapq.heappush(open_list, (neighbor_cost + heuristic(neighbor, goal), neighbor, (node, parent))) # 将邻居节点加入open_list
-
- return None # 如果未找到路径,则返回None
-
- # 测试
- graph = {
- (0, 0): {(0, 1): 1, (1, 0): 1},
- (0, 1): {(0, 0): 1, (1, 1): 1},
- (1, 0): {(0, 0): 1, (1, 1): 1},
- (1, 1): {(0, 1): 1, (1, 0): 1}
- }
-
- start = (0, 0)
- goal = (1, 1)
-
- path = astar(graph, start, goal)
- print(path)
结果:
[(0, 0), (0, 1), (1, 1)]
当然,也可以用更复杂的:
———————————————————————————————————————————
文章来源:书籍《我的第一本算法书》
书籍链接:
我的第一本算法书 (豆瓣) (douban.com)
作者:宫崎修一 石田保辉
出版社:人民邮电出版社
ISBN:9787115495242
本篇文章仅用于学习和研究目的,不会用于任何商业用途。引用书籍《我的第一本算法书》的内容旨在分享知识和启发思考,尊重原著作者宫崎修一和石田保辉的知识产权。如有侵权或者版权纠纷,请及时联系作者。
———————————————————————————————————————————
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。