如何找到二维数组中两个坐标之间的最短路径？

Question

我正在尝试找到从二维数组中的一个点（一个坐标，x 和 y 值表示它在数组中的位置）到另一个点的最短路径。

我想输出一个坐标数组，从初始坐标到最终坐标必须经过这些坐标。

这样的数组的一个例子可以是

arr = [
          [15, 7, 3],
          [1, 2, 6],
          [7, 4, 67]
      ]

在这种情况下，我们可以说我们将从 arr[0][0] 开始并在 arr[2][2] 结束。因此，坐标将是 (0, 0) 和 (2, 2).

预期输出为：[(0, 2), (1, 2), (2, 2), (2, 1)] 或相同长度的内容。

我试过的

我在下面做了一个半成功的功能，但是在大一点的情况下效率很低，很耗时。

import math

arr = [
          [0, 1, 2],
          [3, 4, 5],
          [6, 7, 8]
      ]

coor1 = (0, 0) # seen as 2 in the arr array
coor2 = (2, 2) # seen as 7 in the arr array

def pythagoras(a, b):

    # find pythagorean distances between the two
    distance_y = max(a[0], b[0]) - min(a[0], b[0])
    distance_x = max(a[1], b[1]) - min(a[1], b[1])

    # calculate pythagorean distance to 3 d.p.
    pythag_distance = round(math.sqrt(distance_x**2 + distance_y**2), 3)

    return pythag_distance


def find_shortest_path(arr, position, target):
    ''' finds shortest path between two coordinates, can't go diagonally '''
    coordinates_for_distances = []
    distances = []

    for i in range(len(arr)):
        for r in range(len(arr)):
            coordinates_for_distances.append((i, r))
            distances.append(pythagoras((i, r), target))

    route = []

    while position != target:
        acceptable_y_range = [position[1] + 1, position[1] - 1]
        acceptable_x_range = [position[0] + 1, position[0] - 1]

        possibilities = []
        distance_possibilities = []

        for i in range(len(coordinates_for_distances)):
            if coordinates_for_distances[i][0] == position[0] and coordinates_for_distances[i][1] in acceptable_y_range:
                possibilities.append(coordinates_for_distances[i])
                distance_possibilities.append(distances[i])

            elif coordinates_for_distances[i][1] == position[1] and coordinates_for_distances[i][0] in acceptable_x_range:
                possibilities.append(coordinates_for_distances[i])
                distance_possibilities.append(distances[i])

        zipped_lists = zip(distance_possibilities, possibilities)
        minimum = min(zipped_lists)
        position = minimum[1]
        route.append(position)

    return route

Answer 1

为了找到一对坐标之间的最短路径，我们可以将其转化为图问题，其中每个坐标是一个图节点。现在在这个设置下，找到两个节点之间的最短路径是一个well known graph theory problem，并且使用正确的工具很容易解决。

我们可以使用 NetworkX, which actually has a Graph generator，即 returns mxn 个节点的二维网格图，每个节点都与其最近的邻居相连。这是完美的案例：

import networkx as nx
from matplotlib import pyplot as plt

G = nx.grid_2d_graph(3,3)

plt.figure(figsize=(6,6))
pos = {(x,y):(y,-x) for x,y in G.nodes()}
nx.draw(G, pos=pos, 
        node_color='lightgreen', 
        with_labels=True,
        node_size=600)

现在我们可以使用 networkX 的 nx.bidirectional_shortest_path 来找到两个坐标之间的最短路径：

coor1 = (0, 2) # seen as 2 in the arr array
coor2 = (2, 1) # seen as 7 in the arr array

nx.bidirectional_shortest_path(G, source=coor1, target=coor2)
# [(0, 2), (1, 2), (2, 2), (2, 1)]

请注意，nx.grid_2d_graph 将生成任意大 m 和 n 的网格图，通过定位标签，您还可以像上面一样绘制坐标网格:

如何找到二维数组中两个坐标之间的最短路径？

How to find the shortest path between two coordinates in a 2-dimensional array?

python

graph-theory

path-finding

coordinates

networkx