我有一个用于迷宫问题的迷宫矩阵。
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): # 首先，让我们查找起始位置，有更好的方法但这可以工作 (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] # 并获取目标位置（用于启发式） (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] # 获取总成本 # 为了代码更易读，状态是（坐标元组，前一个，路径成本，启发式成本） fringe = [((i_s, j_s), list(), 0, heuristic(i_s, j_s))] visited = {} # 空集合 # 可能限制以防止搜索时间过长 while True: # 获取第一个状态（成本最低） state = fringe.pop(0) # 目标检查 (i, j) = state[0] if lab[i][j] == 3: path = [state[0]] + state[1] path.reverse() return path # 设置成本（路径足够，因为启发式不会改变） visited[(i, j)] = state[2] # 探索邻居 neighbor = list() if i > 0 and lab[i-1][j] > 0: #上方 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]))) # 重新排序列表（这里应该使用优先级队列以避免每次都重新排序） fringe.sort(key=comp)