围绕加权二维数组中的目标的最短路径
shortest path to surround a target in a weighted 2d array
我在寻找正确的编码方法时遇到了一些麻烦。
取一个随机生成的二维数组，大约 50x50，每个单元格的值为 1~99。
从随机位置“绿色”开始，目标是用最少的动作包围目标“红色”。
移动到相邻单元格需要 1~99 次操作，具体取决于它的值。
具有低值的示例小数组：
[
目前我最好的想法是，根据目标的对角线生成 4 组检查点，然后使用大量 Dijkstra 来找到一条通过所有这些检查点的路径，以及起点。
我遇到的一个问题是，这很快就会变成极端数量的路径。
从任何起点“NorthWest-1 到 NW-20”到“NE-1 到 NE-20”中的任何终点，有 400 种可能性。将第 3 条和第 4 条对角线相加就变成 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
不幸的是，这个伪代码已经包含了一些边缘情况，其中 'wall' 阻塞了最有效的路径。
如果相关，这将写入javascript。
编辑，作为一种极端情况，它可以在包围目标之前使目标旋转，尽管这种情况极为罕见
编辑2； “包围”意味着断开目标与场地的其余部分，无论包围区域有多大，或者即使它包括起点（例如，所有边缘均为 0）
这是另一个具有（可能）最佳路径的较大字段，以及 2 个文本格式的字段：
https://i.imgur.com/yMA14sS.png
https://pastebin.com/raw/YD0AG6YD
您可能需要考虑改用 A* 搜索算法，您可以调整算法以一次搜索所有 4 个地点。
https://en.wikipedia.org/wiki/A*_search_algorithm
基本上，A* 扩展了 Dijkstra 算法，将其搜索重点放在离目的地“更近”的地点。
搜索算法还有许多其他变体可能对您的情况更有用，在“另请参阅”部分中也是如此，尽管其中一些更适合视频游戏路径规划而不是 2D 网格路径.
再次审阅问题后编辑：
似乎每个点都有重量。这使得距离计算有点不那么直接。在这种情况下，我会将其视为优化。对于启发式成本函数，最好只使用到目标的最直接路径（对角线）作为启发式成本，然后使用 A* 搜索尝试找到更好的路径。
至于环绕逻辑。我会把它当作它自己的逻辑和一个单独的步骤（可能是第二步）。首先找到到达目标的最低成本路径。然后找到最便宜的方法来包围路径。老实说，围绕一个点的最便宜的方法可能值得它自己的问题。
一旦你拥有了这两个部分，合并这两个部分应该很容易。两者首先会在某个点重叠，那就是它们合并在一起的地方。
简而言之，我们将围绕目标的路径称为 fences。有效的栅栏是一组（连接的）节点，它们使目标从一开始就断开连接，但不包括目标。最小栅栏是一种成本最低的栅栏。 套索 可以是包含到起始节点路径的栅栏。目标是构建一个 minimal-cost 套索。
一个简单的算法是使用目标的直接邻域作为栅栏，运行 Dijkstra 对其中任何一个 fence-nodes 构建一个（可能 non-optimal）套索.请注意，如果需要最佳答案，围栏的选择实际上会影响从起点到围栏的路径选择——并且vice-versa、从起点到栅栏的路径选择会影响栅栏本身的选择方式。这个问题不能简单地分成两部分。
我相信以下算法会产生最佳 fences:
- 使用 Dijkstra 从开始到目标构建路径（不包括 end-points）。让我们称之为 黄色 路径。
- 构建 2 组节点，在这条 黄色 路径的每一侧各一个，并与它相邻。将这些集合称为 red 和 blue。请注意，对于与路径相邻的任何给定节点，它可以是路径、蓝色集、红色集的一部分，或者实际上是 end-point.
- 对于red集合中的每个节点，运行Dijkstra寻找到blue中节点的最短路径设置不穿过黄色路径。
- 对于之前的每条路径，在添加（缺失的）yellow-path 位以将蓝色和红色端连接在一起后，查看哪条路径最短。
成本是length(yellowPath) * cost_of_Dijkstra(redStart, anyBlue)
要制作一个好的套索，从头到任何栅栏节点 运行 Dijkstra 就足够了。 但是，我不确定最后的套索是否是最优的。
我在寻找正确的编码方法时遇到了一些麻烦。
取一个随机生成的二维数组，大约 50x50，每个单元格的值为 1~99。
从随机位置“绿色”开始，目标是用最少的动作包围目标“红色”。
移动到相邻单元格需要 1~99 次操作，具体取决于它的值。
具有低值的示例小数组：
[
目前我最好的想法是，根据目标的对角线生成 4 组检查点，然后使用大量 Dijkstra 来找到一条通过所有这些检查点的路径，以及起点。
我遇到的一个问题是，这很快就会变成极端数量的路径。
从任何起点“NorthWest-1 到 NW-20”到“NE-1 到 NE-20”中的任何终点，有 400 种可能性。将第 3 条和第 4 条对角线相加就变成 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
不幸的是，这个伪代码已经包含了一些边缘情况，其中 'wall' 阻塞了最有效的路径。
如果相关，这将写入javascript。
编辑，作为一种极端情况，它可以在包围目标之前使目标旋转，尽管这种情况极为罕见
编辑2； “包围”意味着断开目标与场地的其余部分，无论包围区域有多大，或者即使它包括起点（例如，所有边缘均为 0）
这是另一个具有（可能）最佳路径的较大字段，以及 2 个文本格式的字段：
https://i.imgur.com/yMA14sS.png
https://pastebin.com/raw/YD0AG6YD
您可能需要考虑改用 A* 搜索算法，您可以调整算法以一次搜索所有 4 个地点。
https://en.wikipedia.org/wiki/A*_search_algorithm
基本上，A* 扩展了 Dijkstra 算法，将其搜索重点放在离目的地“更近”的地点。
搜索算法还有许多其他变体可能对您的情况更有用，在“另请参阅”部分中也是如此，尽管其中一些更适合视频游戏路径规划而不是 2D 网格路径.
再次审阅问题后编辑：
似乎每个点都有重量。这使得距离计算有点不那么直接。在这种情况下，我会将其视为优化。对于启发式成本函数，最好只使用到目标的最直接路径（对角线）作为启发式成本，然后使用 A* 搜索尝试找到更好的路径。
至于环绕逻辑。我会把它当作它自己的逻辑和一个单独的步骤（可能是第二步）。首先找到到达目标的最低成本路径。然后找到最便宜的方法来包围路径。老实说，围绕一个点的最便宜的方法可能值得它自己的问题。
一旦你拥有了这两个部分，合并这两个部分应该很容易。两者首先会在某个点重叠，那就是它们合并在一起的地方。
简而言之，我们将围绕目标的路径称为 fences。有效的栅栏是一组（连接的）节点，它们使目标从一开始就断开连接，但不包括目标。最小栅栏是一种成本最低的栅栏。 套索 可以是包含到起始节点路径的栅栏。目标是构建一个 minimal-cost 套索。
一个简单的算法是使用目标的直接邻域作为栅栏，运行 Dijkstra 对其中任何一个 fence-nodes 构建一个（可能 non-optimal）套索.请注意，如果需要最佳答案，围栏的选择实际上会影响从起点到围栏的路径选择——并且vice-versa、从起点到栅栏的路径选择会影响栅栏本身的选择方式。这个问题不能简单地分成两部分。
我相信以下算法会产生最佳 fences:
- 使用 Dijkstra 从开始到目标构建路径（不包括 end-points）。让我们称之为 黄色 路径。
- 构建 2 组节点，在这条 黄色 路径的每一侧各一个，并与它相邻。将这些集合称为 red 和 blue。请注意，对于与路径相邻的任何给定节点，它可以是路径、蓝色集、红色集的一部分，或者实际上是 end-point.
- 对于red集合中的每个节点，运行Dijkstra寻找到blue中节点的最短路径设置不穿过黄色路径。
- 对于之前的每条路径，在添加（缺失的）yellow-path 位以将蓝色和红色端连接在一起后，查看哪条路径最短。
成本是length(yellowPath) * cost_of_Dijkstra(redStart, anyBlue)
要制作一个好的套索，从头到任何栅栏节点 运行 Dijkstra 就足够了。 但是，我不确定最后的套索是否是最优的。