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

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 ，实际上有一个 Graph generator ，返回 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 ，通过定位标签，您还可以像上面一样绘制坐标网格: