algorithm - 二维网格上从 (0,0) 到 (N,N) 的最小成本路径

Question

我有一个二维网格的问题，你试图找到从 (0, 0) 到 (N, N) 的最短路径，其中 1 < N < 10^9。还有 P (1 < P < 10^5) 快捷键，可以从 (x1, y1) 跳转到 (x2, y2)。

旅行时，您只能向上或向右走。同样，快捷方式永远不会将您向下或向左移动。

示例案例：您在 (0, 0) 并试图到达 (3, 3)。有两种快捷方式：一种将您从 (0, 1) 移动到 (0, 2)，另一种将您从 (1, 2) 移动到 (2, 3)。

最佳路径是：

从 (0,0) 移动到 (0,1)（1 个单位）。(0,2) 的快捷方式。从 (0,2) 移动到 (1,2)（1 个单位）。(2,3) 的快捷方式。从 (2,3) 移动到 (3,3)（1 个单位）。

所以总长度是3个单位。

时间范围也是2秒。

编辑 1：我想到了使用动态编程来做一个成本矩阵。矩阵[i][j] = 到达路径的总成本 (i, j)。但是，网格很大，矩阵将有 10^18 个插槽，这太大了，不适合时间范围。

编辑 2：我的下一个想法是使用 Dijkstra 算法；只需将结束、开始和快捷方式设置为图中的所有节点即可。但是，这变成了 O(N^2) 解决方案（最多有 10^10 条边！）

编辑 3：我想出了另一个 O(N^2) 解决方案。基本上，您会根据它们与原点的距离对所有快捷方式进行排序。然后，通过遍历已处理的所有快捷方式，您将找到每个快捷方式的最短路径。你会找到（distTo（每个快捷方式）+ manhattan_distance（每个快捷方式，当前快捷方式））的最小值。最后，您将处理 (N, N) 点，就好像它是找到最终解决方案的捷径一样。

但是，这仍然太慢 - 有没有办法进一步优化我的解决方案或更好的解决方案？

标签： algorithmdynamicgraphlanguage-agnosticshortest-path

Answer 1

让我们注意，我们可以在 const time abs(ax - bx) + abs(ay - by) 中计算从 A 点到 B 点的距离。我们可以通过它的协调对所有点进行排序。在我们运行类似 dp -> dist for point x 之后，将是来自门户的最小 dist 分数，i.x <= x.x && i.y <= x.x其中 i 是门户的出口，+ 从出口到点 x 的距离。（如果 x 是数组的入口或结尾，则仅考虑它）。如果我们将 x 视为我们的第二个 for 循环，我们还需要删除先前考虑的点，如果该点在 x 坐标上的坐标中得分最差，则将其替换为得分最高的新“虚拟”点。