c++ - 多米诺路径算法

Question

我有一些(我希望)关于可以解决“多米诺路径”问题的算法的简单问题。我正在寻找能够以低于 O(n^2) 复杂度的方式解决此问题的解决方案。

我有一组 n 点(n 在 [1,100 000] 中，每个点都是不同的)，具有 x 和 y 坐标:
(0,1)
(1,3)
(1,2)
(2,4)
(3,5)
(4,2)
(5,0)

我正在寻找从起点 (0,y) 到终点 (x,0) 的“路径”(另一点需要像多米诺骨牌一样粘起来)。在此示例中，路径将如下所示:(0,1) > (1,3) > (3,5) > (5,0)。如果这些点将创建多条路径 - 选择其中任何一条。能不能做到小于O(n^2)？

编辑:感谢图形算法，但是没有它可以完成吗？我正在寻找一些棘手的递归算法或类似的东西。

Answer 1

是的。您应该阅读 Dijkstra's algorithm它在 O(E+V log V) 中运行，其中 E 是图中的边数，V 是顶点数。 breadth-first search也会工作，因为图表未加权。这将在 O(E+V) 时间内运行。

尽管这些是解决此问题的常用方法，但它们是 by no means the only ones .