python - python中迷宫矩阵的A星(A *)搜索算法
问题描述
我有一个迷宫问题的迷宫矩阵。
Labyrinth =
[[0, 0, 0, 0, 0, 0, 1, 0],
[0, 1, 0, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 0, 1, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 1, 1, 3, 0],
[0, 0, 1, 1, 1, 0, 0, 0],
[0, 1, 2, 0, 1, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0, 0]]
这里,
- 0 表示一个封闭的单元格,它是一堵墙
1 表示一个空单元格
2 和 3 分别代表起点和终点。
我需要一个函数,它可以在使用曼哈顿距离作为距离估计和当前路径的长度作为路径成本执行A* 搜索算法后返回从点 2 到 3 的路径。
任何指针?或提示/提示我应该如何操作这个?
更新:我想通过用 X 等其他字符标记路径来从头到尾返回路径。作为参考,这个:
Labyrinth =
[[0, 0, 0, 0, 0, 0, 1, 0],
[0, 1, 0, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 0, 1, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, X, X, 3, 0],
[0, 0, X, X, X, 0, 0, 0],
[0, 1, 2, 0, 1, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0, 0]]
解决方案
经典搜索算法使用一组称为边缘的状态和一组访问状态:
- 边缘是所有尚未探索希望找到目标状态的集合
- 访问集是所有已经访问过的状态,以避免再次访问它们
A* 的想法是探索边缘中具有最小成本值的状态(定义为启发式成本和进展成本的总和(由您之前必须经过的所有状态计算))。您可以在 A* 搜索算法的维基百科页面上找到该算法的通用实现。在您的情况下,状态可能包括:
i, j
网格中的位置- 前一个状态(假设
None
为第一个状态) - 此状态的总成本(启发式 + 路径成本)。
要探索一个集合,您只需要检查单元格的直接邻居(仅包括值为 1 的那个)。值得注意的是,在访问集中,您应该只包括位置 (i,j) 和成本(因为如果您找到更短的路径,您可能会重新进入此状态,即使在您的问题中不太可能)。
这是一个适用于您的案例的示例(但可能很容易概括):
def astar(lab):
# first, let's look for the beginning position, there is better but it works
(i_s, j_s) = [[(i, j) for j, cell in enumerate(row) if cell == 2] for i, row in enumerate(lab) if 2 in row][0][0]
# and take the goal position (used in the heuristic)
(i_e, j_e) = [[(i, j) for j, cell in enumerate(row) if cell == 3] for i, row in enumerate(lab) if 3 in row][0][0]
width = len(lab[0])
height = len(lab)
heuristic = lambda i, j: abs(i_e - i) + abs(j_e - j)
comp = lambda state: state[2] + state[3] # get the total cost
# small variation for easier code, state is (coord_tuple, previous, path_cost, heuristic_cost)
fringe = [((i_s, j_s), list(), 0, heuristic(i_s, j_s))]
visited = {} # empty set
# maybe limit to prevent too long search
while True:
# get first state (least cost)
state = fringe.pop(0)
# goal check
(i, j) = state[0]
if lab[i][j] == 3:
path = [state[0]] + state[1]
path.reverse()
return path
# set the cost (path is enough since the heuristic won't change)
visited[(i, j)] = state[2]
# explore neighbor
neighbor = list()
if i > 0 and lab[i-1][j] > 0: #top
neighbor.append((i-1, j))
if i < height and lab[i+1][j] > 0:
neighbor.append((i+1, j))
if j > 0 and lab[i][j-1] > 0:
neighbor.append((i, j-1))
if j < width and lab[i][j+1] > 0:
neighbor.append((i, j+1))
for n in neighbor:
next_cost = state[2] + 1
if n in visited and visited[n] >= next_cost:
continue
fringe.append((n, [state[0]] + state[1], next_cost, heuristic(n[0], n[1])))
# resort the list (SHOULD use a priority queue here to avoid re-sorting all the time)
fringe.sort(key=comp)
推荐阅读
- python - 关闭一个 qthread
- c# - 从父表单关闭打开的表单
- android - 使用谷歌分析 Flutter 日志事件
- javascript - 位置:'底部' - 选项卡不允许滑动
- python - Python脚本将八进制转换为字符串,例如八进制(755)到(rwxr-xr-x)。坚持添加破折号分隔符
- node.js - 使用 batchupdate() 通过 nodejs 使用 API 更改 Google 文档中所有内容的行高
- swift - SwiftUI 中的 Tabbar 中间按钮实用功能
- unit-testing - 模拟改造挂起功能无限响应
- prolog - 定义一个规则发生_before(X,Y),它使用系统谓词定义事件 X 在事件 Y 之前发生的关系
- linux - Ansible:即使在调试显示它的内容之后,注册的变量也是未定义的