假设我有一个带有加权边的 N*N 二维网格。我在网格上做的每个 Action 都有一个限制，即始终具有固定的 X 或 Y 分量，即:在每个 Action 中，我必须在 X 中移动 1 个单位坐标和 Y 坐标中的 3。
我考虑过移除我不应该走过的边缘，但这并没有解决我必须做这些 Action 的事实。我如何修改 dijkstra(或任何寻路算法，但最好是 dijkstra)，以便它在具有这些约束的情况下为我提供从 A 到 B 的最短路径？
最佳答案
我知道这已经很长时间了，但我只想提供我对这个问题的看法，因为还没有具体的答案。
因为遍历网格有一个约束(类似于您必须使用 (1,3) 向量移动的示例，即 X 方向为 1，Y 方向为 3)，当给定起点时，只有一些单元格是可达的，它们将形成我们将在其上执行 Dijkstra 算法的图形。我们可以在原始网格本身上执行 Dijkstra，无法到达的节点将与源有无限的距离。然而，这是非常昂贵的，因为我们实际上增加了我们必须在算法的每次迭代中检查的细胞数量。
我们可以通过执行修改后的 BFS 来计算所有可达单元格的图形。在搜索的每次迭代中，只会检查有效的单元格。这里的“有效”是指满足遍历约束，在原网格范围内。例如，如果我们使用从 (0,0) 开始的非负数对 6x6 网格中的所有单元格进行索引，并且约束为 (1,2)，那么如果对单元格 (0,0) 执行 BFS，则唯一有效的邻居将是 (1,2)。然后，BFS 将通过选择两条可能路径中成本较低的一条来计算连接 (0,0) 和 (1,2) 的边的权重:(0,0)->(0,1)->(1, 1)->(1,2) 和 (0,0)->(0,1)->(0,2)->(1,2)。对 (0,0) 的所有邻居执行此操作，然后是所有邻居及其邻居，依此类推，就像常规 BFS 一样。不同之处在于，在 BFS 迭代期间，当遇到一个已经发现的单元时，该单元与 BFS 中正在迭代的单元之间的边权重仍然会被计算(因为我们正在制作一个包含所有可能和有效连接的图可达单元，而不仅仅是 BFS 树)。最后，我们将创建所需的图表。
如果最终目的地不在结果图中(我们可以有一个集合来跟踪图中的所有单元格)，那么我们得出结论，从源到目的地没有路径。
如果目的地在图中，那么我们将在图中正常执行 Dijkstra 算法。结果将是最短路径。
关于algorithm - 具有强制运动约束的 Dijkstra，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37277673/