我有一些(我希望)关于可以解决“多米诺骨牌路径”问题的算法的简单问题。我正在寻找能够以低于 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)以内完成吗？
编辑:感谢图算法，但是没有它也能完成吗？我正在寻找一些棘手的递归算法或类似的东西。
最佳答案
是的。您应该阅读Dijkstra's algorithm其运行时间为 O(E+V log V)，其中 E 是图中的边数，V 是顶点数。一个breadth-first search也可以，因为该图未加权。这将在 O(E+V) 时间内运行。
虽然这些是解决此问题的常见方法，但它们是 by no means the only ones .
关于c++ - 多米诺路径算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28863619/