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

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

为了找到一对坐标之间的最短路径，我们可以将其转化为一个图形问题，其中每个坐标是一个图形节点。现在在这种设置下，寻找两个节点之间的最短路径是一个 众所周知的图论问题，而且用正确的工具相当容易解决。

我们可以用 联网，它实际上有一个 图表生成器的二维网格图，返回 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通过定位标签，你也可以像上面一样绘制坐标网格。