python 中迷宫矩阵的 A 星 (A*) 搜索算法

Question

我有一个迷宫矩阵来解决迷宫问题。

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* 搜索 算法后 return 从点 2 到点 3 的路径曼哈顿距离作为距离估计，当前路径的长度作为路径成本。

有指点吗？或者tip/clue我应该如何操作这个？

更新：我想 return 通过用 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]]

Answer 1

经典搜索算法使用一组称为边缘的状态和一组访问状态来工作：

边缘是所有尚未探索希望找到目标状态的集合
访问集是所有已经访问过的状态，避免再次访问它们

A*的思想是在边缘探索成本值最小的状态（定义为启发式成本和进展成本之和（由之前必须经过的所有状态计算得出） )).您可以在 the wikipedia page for A* search algorithm 上找到该算法的通用实现。在您的情况下，状态可能包括：

网格中的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 中迷宫矩阵的 A 星 (A*) 搜索算法

A-star (A*) search algorithm on labyrinth matrix in python

python

search

maze

artificial-intelligence

a-star