A-star(A*)在Python中对迷宫矩阵的搜索算法 [重复]。

Question

这个问题在这里已经有了答案:

一种星形算法。距离启发法 (1个答案)

封闭 上月.

我有一个迷宫问题的迷宫矩阵。

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*搜索 算法使用 曼哈顿距离 作为距离估计和 当前路径的长度 作为路径成本。

有什么好的建议吗？

更新：我想用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*的想法是探索边缘地带中成本值最小的状态（定义为启发式成本和进阶成本（由你之前必须经过的所有状态计算）之和）。你可以在上找到这个算法的通用实现。A*搜索算法的维基百科页面. 在你的情况下，一个国家可能包括：

1. ．i, j 网格中的位置
2. 上一状态 None (第一种状态)
3. 这个状态的总成本（启发式+路径成本）。

要探索一个集合，你只需要检查小区的直接邻居（只包括值为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)