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

Question

我试图找到从2D数组中的一个点（一个坐标为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，使用正确的工具即可轻松解决。

我们可以执行此操作的一种方法是根据网格的大小生成坐标的节点列表。对于共享示例，(3,3)网格。

x, y = 3, 3
nodelist =  [[(i,j) for j in range(y)] for i in range(x)]
# [[(0, 0), (0, 1), (0, 2)], [(1, 0), (1, 1), (1, 2)], [(2, 0), (2, 1), (2, 2)]]

现在，我们可以使用NetworkX构建图形，并通过压缩NetworkX中的连续节点及其转置来在相邻节点之间添加边，可以通过再次压缩并解压缩nodelist行来获得它的转置：

nodelist

import networkx as nx

G = nx.Graph()

for i in range(len(nodelist)-1):
    G.add_edges_from(zip(nodelist[i], nodelist[i+1]))

cols = list(zip(*nodelist))
for i in range(len(cols)-1):
    G.add_edges_from(zip(cols[i], cols[i+1]))

G.edges()
# EdgeView([((0, 0), (1, 0)), ((0, 0), (0, 1)), ((1, 0), (2, 0)), ((1, 0), (1, 1)),...

plt.figure(figsize=(6,6))
nx.draw(G, node_color='lightgreen', 
        with_labels=True,
        node_size=600)

现在我们可以使用networkX的查找两个坐标之间的最短路径：

nx.bidirectional_shortest_path