计算网格中点组合之间的距离
Compute distance between combinations of points in a grid
我正在寻找以下问题的有效解决方案。这应该适用于 python，但不必是 in python.
我有一个二维矩阵，矩阵的每个元素代表二维正交网格中的一个点。我想计算 网格中点对之间的最短距离 。如果网格中没有 "obstacles"，这将是微不足道的。
一张图帮助解释：
图中的每个单元格都是矩阵的一个元素（矩阵是正方形的，也可以是长方形的）。 灰色单元格是障碍物，两点之间的任何路径都必须绕过它们。 绿色细胞是我感兴趣的。我对红色细胞不感兴趣，但路径可以穿过它们。
A点和B点之间的距离计算起来很简单，但是如何计算图中A点和C点之间的路径呢？
我已经阅读了有关 A* algorithm 的信息，但由于我正在使用一个相当大的网格，通常是（几百）x（几百），我想知道是否有更聪明的选择。请记住：我必须找到所有 "green cells" 对之间的距离，而不仅仅是其中两个之间的距离。如果我有 n 个绿色单元格，我将有许多组合等于二项式系数 (n 2)。
网格是固定的，我必须计算一次所有的距离，然后他们在进一步的计算中使用它们，比如根据矩阵中的相关索引访问它们。
注意：问题不在于 this one，坐标在列表中。我的 2D 坐标组织在一个 2D 网格中，问题是关于利用这个方面来获得更有效的算法。
我认为最直接的解决方案是 Floyd-Warshall 算法，该算法计算图中所有节点对之间的最短距离。这不一定利用您碰巧有一个二维网格这一事实（它也可以用于其他类型的图形），但它应该可以正常工作。与必须为任意图形编写实现相比，您确实拥有 2D 网格这一事实可能使您能够更有效地实现它（例如，您可以只存储距离，因为它们是在矩阵中计算的，而不是一些效率较低的数据结构）。
常规版本只生成所有最短路径的距离作为输出，实际上并不存储路径本身作为输出。维基百科页面上有更多关于如何修改算法以使您能够在必要时有效地重建路径的信息。
凭直觉，我怀疑可能会利用您拥有 2D 网格这一事实实现更高效的实现，可能会使用 Rectangular Symmetry Reduction and/or Jump Point Search 中的想法。尽管这两种想法传统上都与 A* 一起用于单对寻路查询，但我不知道有任何工作将它们用于所有对最短路径计算。我的直觉表明它们也可以在那里被利用，但是在准确地弄清楚并正确实施它的时间里，您可能可以更轻松地实施和 运行 Floyd-Warshall。
我正在寻找以下问题的有效解决方案。这应该适用于 python，但不必是 in python.
我有一个二维矩阵，矩阵的每个元素代表二维正交网格中的一个点。我想计算 网格中点对之间的最短距离 。如果网格中没有 "obstacles"，这将是微不足道的。
一张图帮助解释：
图中的每个单元格都是矩阵的一个元素（矩阵是正方形的，也可以是长方形的）。 灰色单元格是障碍物，两点之间的任何路径都必须绕过它们。 绿色细胞是我感兴趣的。我对红色细胞不感兴趣，但路径可以穿过它们。
A点和B点之间的距离计算起来很简单，但是如何计算图中A点和C点之间的路径呢？
我已经阅读了有关 A* algorithm 的信息，但由于我正在使用一个相当大的网格，通常是（几百）x（几百），我想知道是否有更聪明的选择。请记住：我必须找到所有 "green cells" 对之间的距离，而不仅仅是其中两个之间的距离。如果我有 n 个绿色单元格，我将有许多组合等于二项式系数 (n 2)。
网格是固定的，我必须计算一次所有的距离，然后他们在进一步的计算中使用它们，比如根据矩阵中的相关索引访问它们。
注意：问题不在于 this one，坐标在列表中。我的 2D 坐标组织在一个 2D 网格中，问题是关于利用这个方面来获得更有效的算法。
我认为最直接的解决方案是 Floyd-Warshall 算法，该算法计算图中所有节点对之间的最短距离。这不一定利用您碰巧有一个二维网格这一事实（它也可以用于其他类型的图形），但它应该可以正常工作。与必须为任意图形编写实现相比，您确实拥有 2D 网格这一事实可能使您能够更有效地实现它（例如，您可以只存储距离，因为它们是在矩阵中计算的，而不是一些效率较低的数据结构）。
常规版本只生成所有最短路径的距离作为输出，实际上并不存储路径本身作为输出。维基百科页面上有更多关于如何修改算法以使您能够在必要时有效地重建路径的信息。
凭直觉，我怀疑可能会利用您拥有 2D 网格这一事实实现更高效的实现，可能会使用 Rectangular Symmetry Reduction and/or Jump Point Search 中的想法。尽管这两种想法传统上都与 A* 一起用于单对寻路查询，但我不知道有任何工作将它们用于所有对最短路径计算。我的直觉表明它们也可以在那里被利用，但是在准确地弄清楚并正确实施它的时间里，您可能可以更轻松地实施和 运行 Floyd-Warshall。