在加权的二维数组中，围绕目标的最短路径

Question

在加权的二维数组中，围绕目标的最短路径

algorithmbreadth-first-searchpseudocodeshortest-pathdijkstra

4

我在编程时遇到了一些麻烦。

有一个随机生成的二维数组，大约为50x50，每个单元格的值为1~99。
从一个随机位置“Green”开始，目标是用最少的移动次数将目标“Red”包围起来。
移动到相邻单元格需要1~99次操作，具体取决于它的值。
以下是具有较低值的小数组示例：

[]

目前我想到的最好的方法是，基于目标点的对角线生成4组检查点，然后使用大量的Dijkstra算法找到经过所有检查点和起始点的路径。

我遇到的一个问题是，这很快就变成了极其多的路径。
从任何起点“NorthWest-1 to NW-20”到“NE-1 to NE-20”的任何结束点，有400种可能性。加上第三个和第四个对角线后，变成了400 * 20 * 20。

使用对角线检查点的另一个问题是该问题不是[从绿色到对角线（橙色路径）的最短路径]。

[]

而是“从绿色到红色路径周围的任何点”。

当前伪代码：

take 2 sets of diagonals nearest to Green/start
find the shortest path that connects those diagonals while going through Green
(backtracking through the path is free)

draw a line starting from the target point, in-between the 2 connected diagonals,
set those cells to value infinite to force going around them (and thus around the target)

find the shortest path connecting the now-seperated diagonals

很不幸，这份伪代码已经包含了一些边缘情况，其中“墙”挡住了最高效的路径。

如果相关，这将会使用JavaScript编写。

编辑，作为一种极端情况，它可能会在围住目标之前将其螺旋起来，尽管非常罕见。

编辑2; “围住”意味着将目标从场地的其余部分断开，无论被围住的区域有多大，甚至是否包含起点（例如，所有边缘都是0）。

这里有另一个更大的场地，可能具有最优路径，并且还有两个文本形式的场地：
https://i.imgur.com/yMA14sS.png
https://pastebin.com/raw/YD0AG6YD

- Lughaidh

有趣的问题。我能想到的一种方法是将其分成两个不同的问题：a. 找到包含目标的最低成本的闭环。b. 从源开始运行BFS，直到您遇到在a中找到的闭环的一个单元格。第一个问题（a）当然更难。 - c0der

请问您能否编辑问题，将其中一个测试用例的数据作为代码（即2D数组）包含在内，以便可以复制/粘贴？ - kaya3

篱笆有两面。包围起始节点的篱笆是否也被认为是“包围”目标节点？如果不是，您能否澄清“包围”的含义，即对于任何断开起始节点和目标节点的路径，哪些路径被认为是“包围”目标节点，哪些不是？ - tucuxi

2个回答

0

你可能想考虑使用A*搜索算法，这样你可以调整算法以一次搜索所有4个位置。

https://en.wikipedia.org/wiki/A*_search_algorithm

基本上，A*算法通过将搜索重点放在“更接近”目标的位置上来扩展Dijkstra算法。

还有许多其他搜索算法的变体，在“另请参阅”部分中可能更适合您的情况，尽管其中一些更适用于视频游戏路径规划而不是2D网格路径。

在重新审查问题后进行编辑：

似乎每个位置都有一个权重。这使得距离计算变得有些复杂。在这种情况下，我会将其视为一种优化。对于启发式成本函数，最好只使用最直接的路径（对角线）到目标作为启发式成本，然后使用A*搜索来寻找更好的路径。

关于围绕逻辑。我会将其视为自己的逻辑和一个单独的步骤（可能是第二步）。首先找到到目标的最小成本路径。然后找到围绕路径的最便宜的方法。老实说，围绕一个点的最便宜的方法可能值得一问。

一旦您拥有了两个部分，将它们合并应该很容易。两个部分会有一些重叠的地方，那就是它们被合并在一起的地方。

- Nuclearman

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tucuxi · Accepted Answer

简单来说，我们把围绕目标的路径称为栅栏。一个有效的栅栏是一组（连通的）节点，使得从起点到目标的路径被切断，但不包括目标本身。最小的栅栏是指在成本最小的情况下实现这一点的栅栏。一个套索可以是包含到起始节点的路径的栅栏。目标是构建一个成本最小的套索。

一个简单的算法是使用目标的直接邻居作为栅栏，并运行Dijkstra算法到任何一个栅栏节点来构建一个（可能非最优的）套索。请注意，如果需要最优答案，栅栏的选择实际上会影响从起点到栅栏的路径的选择——反之亦然，从起点到栅栏的路径的选择也会影响如何选择栅栏本身。这个问题无法很好地分成两个部分。

我相信以下算法将产生最优的栅栏：

使用Dijkstra算法从起点到目标点（不包括端点）构建路径。我们将其称为黄色路径。
构建两组节点，一组在黄色路径的左侧，另一组在右侧。这些组分别称为红色和蓝色。请注意，对于任何与路径相邻的节点，它可以是路径的一部分、蓝色集合、红色集合，或实际上是一个端点。
对于红色集合中的每个节点，运行Dijkstra算法，找到到达蓝色集合中一个没有穿过黄色路径的节点的最短路径。
对于这些先前的路径，请查看在添加（缺失的）连接蓝色和红色端点的黄色路径后哪条路径最短。

成本为length(yellowPath) * cost_of_Dijkstra(redStart, anyBlue)

要制作一个好的套索，只需从起点运行Dijkstra算法到任何围栏节点即可。但是，我不确定最终的套索是否是最优的。