在Python中获取二维数组中一个单元格的最短路径

Question

我有一个二维数组 arr，其中每个单元格都有一个值为 1、2 或 3。例如，arr[0][0] = 3, arr[2][1] = 2, and arr[0][4] = 1。

我想知道从给定的某个单元格（例如 arr[5][5]）到离它最近的值为 2 的单元格的最短路径，路径中不应包含任何值为 1 的单元格。我该如何做？

下面是一个 BFS 的脚本，但我该怎样让它接受一个二维数组作为图形以及一个起始点作为数组中的某个单元格位置，并从这个单元格前往最近的值为 2 的单元格，避免包含值为 1 的单元格，使其看起来像 bfs(2darray, starting location, 2)？

def bfs(graph, start, end):
    # Maintain a queue of paths
    queue = []

    # Push the first path into the queue
    queue.append([start])
    while queue:

        # Get the first path from the queue
        path = queue.pop(0)

        # Get the last node from the path
        node = path[-1]

        # Path found
        if node == end:
            return path

        # Enumerate all adjacent nodes, construct a new path and push it into the queue
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print bfs(graph, '1', '11')

- Tak

---

单元格中的值是否会影响到到达该单元格的路径的“成本”，或者路径的长度总是曼哈顿距离？ - tobias_k

@tobias_k 是的，它们会影响它，如果它的值为1，则此单元格不能成为路径的一部分。我会更新我的问题。 - Tak

@Tak 一个网格/二维数组很像一个图，如果您选择这样去思考的话。把相邻的点想象成它们之间有一条边，你就已经完成了一半。 - mypetlion

@mypetlion 但是我该如何调整已发布的代码以接受2D数组、起始单元格和要查找的值作为输入？ - Tak

@tobias_k 不知何时您能看一下，真的很感激。提前致谢。 - Tak

Answer 1

你可以使用简单的广度优先搜索来完成此任务。基本上，你格子中的每个单元格都对应着图中的一个节点，并且相邻单元格之间有边缘。从起始位置开始，不断扩展可通过的单元格，直到找到目标单元格。

def bfs(grid, start):
    queue = collections.deque([[start]])
    seen = set([start])
    while queue:
        path = queue.popleft()
        x, y = path[-1]
        if grid[y][x] == goal:
            return path
        for x2, y2 in ((x+1,y), (x-1,y), (x,y+1), (x,y-1)):
            if 0 <= x2 < width and 0 <= y2 < height and grid[y2][x2] != wall and (x2, y2) not in seen:
                queue.append(path + [(x2, y2)])
                seen.add((x2, y2))

网格设置和结果：（请注意，我使用符号而不是数字，仅因为这样更容易视觉分析网格并验证解决方案。）

wall, clear, goal = "#", ".", "*"
width, height = 10, 5
grid = ["..........",
        "..*#...##.",
        "..##...#*.",
        ".....###..",
        "......*..."]
path = bfs(grid, (5, 2))
# [(5, 2), (4, 2), (4, 3), (4, 4), (5, 4), (6, 4)]

- tobias_k

---

如果您能给予建议，我将不胜感激。 - Tak

很抱歉再次开启这个线程，但我正在实现这段代码，我不太明白为什么在 if grid[y][x] == goal: 中要反转 y 和 x。为什么不使用 if grid[x][y] == goal: 呢？谢谢！ - Blue Ross

@BlueRoss “grid” 是一个字符串列表，其中每个字符串都是“网格”中的一行。因此，在 grid[a][b] 中，a 选择了字符串（即行），然后 b 选择此字符串中的字符（即列）。因此，应该使用 grid[y][x]，因为 x 是列，而 y 是行。 - tobias_k

这个完美运行，谢谢！而且易于理解，非常优雅。 - ProfessorPorcupine

在开头添加'import collections'。 - salehinejad

Answer 2

如果列表不太大，我发现最简单的解决方案是使用NumPy库的where函数查找具有所需值的单元格。因此，您需要将列表转换为NumPy数组。

下面的代码可能会简化以使其更短，更高效，但这样做会更清晰。另外，您可以计算两种距离：典型的欧几里得距离和曼哈顿距离。

如果存在多个与起始单元格距离相同的目标单元格，则min_coords对应于找到的第一个单元格（首先按行，然后按列）。

import numpy as np

# The list needs to be transformed into an array in order to use the np.where method
# arr = np.random.randint(5, size=(6, 6))
arr = np.array([[0, 0, 0, 1, 1, 3],
                [0, 0, 2, 1, 1, 0],
                [0, 0, 1, 1, 1, 1],
                [3, 0, 3, 1, 1, 1], ])

# Origin cell to make the search
x0, y0 = (1, 1)
targetValue = 3

# This is the keypoint of the problem: find the positions of the cells containing the searched value
positions = np.where(arr == targetValue)
x, y = positions

dx = abs(x0 - x)  # Horizontal distance
dy = abs(y0 - y)  # Vertical distance

# There are different criteria to compute distances
euclidean_distance = np.sqrt(dx ** 2 + dy ** 2)
manhattan_distance = abs(dx + dy)
my_distance = euclidean_distance  # Criterion choice
min_dist = min(my_distance)
print(min_dist)

min_pos = np.argmin(my_distance)  # This method will only return the first occurrence (!)
min_coords = x[min_pos], y[min_pos]
print(min_coords)

- elthaniel

---

不错，但这并没有考虑到可能有“1”挡住了通往最近的“3”的路径。 - tobias_k