2个坐标之间的最短路径，通过一组坐标 - Javascript
Shortest path between 2 co-ordinates, through set of co-ordinates - Javascript
我需要编写一个 JavaScript 算法来找到 2 个坐标之间的最短路径。我研究过使用一些路径查找算法，例如 A* 算法。
然而，我的应用程序的不同之处在于我知道路径可以采用的所有坐标。
例如下图中，绿色方块为起点坐标，红色方块为终点坐标。每个黑色方块代表的坐标将存储在一个数组（或其他数据结构）中。
所以我需要从绿色方块到红色方块的最短路径，但它只能通过一个黑色方块才能到达那里。我还会使用 A* 算法来实现吗？
是的，您可以使用 A*。您将计算从每个黑色坐标到红色方块的距离（移动次数）。然后你得到一个图形结构，你可以从哪个方块移动到哪个方块，并且该图中的每个节点都存储到红色方块的距离。然后将 A* 应用于该图并获得最短路径。
编辑
对于 A*，您需要一个启发式算法，它会告诉您哪个节点更接近端点。计算黑色字段和红色字段之间的 "air distance" 可为您提供每个字段的启发式方法。然后你做 A*，这基本上是带有启发式的 Dijkstra 算法。在您的示例中，如果左上角为 (x = 0, y = 0)，红色为 (14, 7)，绿色为 (0, 1)，则绿色和红色区域之间的空气距离为ABS(14 - 0) + ABS(7 - 1) = 20。所以从坐标上很容易算出来。
我需要编写一个 JavaScript 算法来找到 2 个坐标之间的最短路径。我研究过使用一些路径查找算法，例如 A* 算法。
然而，我的应用程序的不同之处在于我知道路径可以采用的所有坐标。
例如下图中，绿色方块为起点坐标，红色方块为终点坐标。每个黑色方块代表的坐标将存储在一个数组（或其他数据结构）中。
所以我需要从绿色方块到红色方块的最短路径，但它只能通过一个黑色方块才能到达那里。我还会使用 A* 算法来实现吗？
是的，您可以使用 A*。您将计算从每个黑色坐标到红色方块的距离（移动次数）。然后你得到一个图形结构，你可以从哪个方块移动到哪个方块，并且该图中的每个节点都存储到红色方块的距离。然后将 A* 应用于该图并获得最短路径。
编辑
对于 A*，您需要一个启发式算法，它会告诉您哪个节点更接近端点。计算黑色字段和红色字段之间的 "air distance" 可为您提供每个字段的启发式方法。然后你做 A*，这基本上是带有启发式的 Dijkstra 算法。在您的示例中，如果左上角为 (x = 0, y = 0)，红色为 (14, 7)，绿色为 (0, 1)，则绿色和红色区域之间的空气距离为ABS(14 - 0) + ABS(7 - 1) = 20。所以从坐标上很容易算出来。