在 python 中的矩阵上使用统一成本搜索

Question

美好的一天，我有一个 11x11 矩阵（如下所示），其中 0 代表开放空间，1 代表墙壁。水平和垂直运动的权重为 1，对角线运动的权重为 sqrt(2) 矩阵如下所示：

 `board = [[0,0,0,0,0,0,0,0,0,0,0,0],
           [0,0,0,0,0,1,1,1,0,1,1,0],
           [0,1,0,0,0,0,1,1,0,1,1,0],
           [0,1,1,0,0,0,0,0,0,1,1,0],
           [0,1,1,1,0,0,0,0,0,1,1,0],
           [0,1,1,1,1,0,0,0,0,1,1,0],
           [0,1,1,1,1,1,1,1,1,1,1,0],
           [1,1,1,1,1,1,1,1,1,1,1,0],
           [0,0,0,0,0,0,0,0,0,0,1,0],
           [0,0,0,0,0,0,0,0,0,0,1,0],
           [0,0,1,1,1,1,1,1,1,1,1,0],
           [0,0,0,0,0,0,0,0,0,0,0,0]]`

我的目标是在 python 中编写统一成本搜索代码，以找到从起点（例如 [1,1]）到终点（例如 [5,1] 的最具成本效益的路径]).我遇到的大多数代码都适用于图形而不是矩阵。我需要有关使用矩阵解决此问题的帮助。

我是 python 的新手，非常感谢所有帮助和建议。我正在使用 python 3.

Answer 1

由于似乎没有人知道这个问题的简单答案，所以我 post 我的（希望是正确的）答案。使用的方法不是很有效，并且基于像算法一样的洪水填充。

首先我们定义一个包含所有可能方向的列表。这些由 lambda 函数表示，其中 return 新索引（x 和 y）、当前权重和当前路径：

from math import sqrt

dirs = [
    lambda x, y, z, p: (x, y - 1, z + 1, p + [(x, y)]),  # up
    lambda x, y, z, p: (x, y + 1, z + 1, p + [(x, y)]),  # down
    lambda x, y, z, p: (x - 1, y, z + 1, p + [(x, y)]),  # left
    lambda x, y, z, p: (x + 1, y, z + 1, p + [(x, y)]),  # right
    lambda x, y, z, p: (x - 1, y - 1, z + sqrt(2), p + [(x, y)]),  # up left
    lambda x, y, z, p: (x + 1, y - 1, z + sqrt(2), p + [(x, y)]),  # up right
    lambda x, y, z, p: (x - 1, y + 1, z + sqrt(2), p + [(x, y)]),  # down left
    lambda x, y, z, p: (x + 1, y + 1, z + sqrt(2), p + [(x, y)])  # down right
]

然后我们创建一些函数。第一个检查方向计算的索引是否是矩阵的有效索引，并且没有墙。

def valid(grid, x, y):
    return 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 0

adjacent 函数为 frontier 处的每个单元格生成每个方向（想象它像一个波浪），flood 函数将波浪向前移动一步并替换旧的踩墙 (1).

def adjacent(grid, frontier):
    for (x, y, z, p) in frontier:
        for d in dirs:
            nx, ny, nz, np = d(x, y, z, p)
            if valid(grid, nx, ny):
                yield (nx, ny, nz, np)

def flood(grid, lst):
    res = list(adjacent(grid, frontier))
    for (x, y, z, p) in frontier:
        grid[x][y] = 1
    return res

在下面的函数中，我们将定义的函数和return称为最短路径权重和最短路径的元组。

def shortest(grid, start, end):
    start, end = tuple(start), tuple(end)
    frontier = [(start[0], start[1], 0, [])]
    res = []
    while frontier and grid[end[0]][end[1]] == 0:
        frontier = flood(grid, frontier)
        for (x, y, z, p) in frontier:
            if (x, y) == end:
                res.append((z, p + [(x, y)]))
    if not res:
        return ()
    return sorted(res)[0]

我对它进行了 (0, 0) 到 (8, 8) 的测试，输出似乎是合理的。如果两个水平/垂直步骤的成本低于相等对角线步骤的成本，它可能会失败。

编辑：(0, 0) 到 (8, 8) 的结果，P 作为路径：

[[P,P,P,P,P,P,P,P,P,P,P,0],
 [0,0,0,0,0,1,1,1,0,1,1,P],
 [0,1,0,0,0,0,1,1,0,1,1,P],
 [0,1,1,0,0,0,0,0,0,1,1,P],
 [0,1,1,1,0,0,0,0,0,1,1,P],
 [0,1,1,1,1,0,0,0,0,1,1,P],
 [0,1,1,1,1,1,1,1,1,1,1,P],
 [1,1,1,1,1,1,1,1,1,1,1,P],
 [0,0,0,P,P,P,P,P,P,P,1,P],
 [0,0,P,0,0,0,0,0,0,0,1,P],
 [0,P,1,1,1,1,1,1,1,1,1,P],
 [0,0,P,P,P,P,P,P,P,P,P,0]]

体重：39.071067811865476

编辑 2：添加复制粘贴版本。

from math import sqrt

board = [[0,0,0,0,0,0,0,0,0,0,0,0],
         [0,0,0,0,0,1,1,1,0,1,1,0],
         [0,1,0,0,0,0,1,1,0,1,1,0],
         [0,1,1,0,0,0,0,0,0,1,1,0],
         [0,1,1,1,0,0,0,0,0,1,1,0],
         [0,1,1,1,1,0,0,0,0,1,1,0],
         [0,1,1,1,1,1,1,1,1,1,1,0],
         [1,1,1,1,1,1,1,1,1,1,1,0],
         [0,0,0,0,0,0,0,0,0,0,1,0],
         [0,0,0,0,0,0,0,0,0,0,1,0],
         [0,0,1,1,1,1,1,1,1,1,1,0],
         [0,0,0,0,0,0,0,0,0,0,0,0]]

dirs = [
    lambda x, y, z, p: (x, y - 1, z + 1, p + [(x, y)]),  # up
    lambda x, y, z, p: (x, y + 1, z + 1, p + [(x, y)]),  # down
    lambda x, y, z, p: (x - 1, y, z + 1, p + [(x, y)]),  # left
    lambda x, y, z, p: (x + 1, y, z + 1, p + [(x, y)]),  # right
    lambda x, y, z, p: (x - 1, y - 1, z + sqrt(2), p + [(x, y)]),  # up left
    lambda x, y, z, p: (x + 1, y - 1, z + sqrt(2), p + [(x, y)]),  # up right
    lambda x, y, z, p: (x - 1, y + 1, z + sqrt(2), p + [(x, y)]),  # down left
    lambda x, y, z, p: (x + 1, y + 1, z + sqrt(2), p + [(x, y)])  # down right
]

def valid(grid, x, y):
    return 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 0

def adjacent(grid, frontier):
    for (x, y, z, p) in frontier:
        for d in dirs:
            nx, ny, nz, np = d(x, y, z, p)
            if valid(grid, nx, ny):
                yield (nx, ny, nz, np)

def flood(grid, frontier):
    res = list(adjacent(grid, frontier))
    for (x, y, z, p) in frontier:
        grid[x][y] = 1
    return res

def shortest(grid, start, end):
    start, end = tuple(start), tuple(end)
    frontier = [(start[0], start[1], 0, [])]
    res = []
    while frontier and grid[end[0]][end[1]] == 0:
        frontier = flood(grid, frontier)
        for (x, y, z, p) in frontier:
            if (x, y) == end:
                res.append((z, p + [(x, y)]))
    if not res:
        return ()
    return sorted(res)[0]

print(shortest(board, (0, 0), (8, 8)))

在 python 中的矩阵上使用统一成本搜索

Using uniform cost search on a matrix in python

python

distance

matrix