什么是 C 或 python 中的有效算法，给定一个表示两个数字之间关系的无序对列表，将组合这些对，使它们形成一个连续列表。
例如，给定以下内容：
(0, 1)
(1, 2)
(3, 2)
(4, 3)
产生以下内容：[0, 1, 2, 3, 4]
显然，这在对中存在间隙或循环的情况下不起作用，例如 ，(0, 1) (3, 4)并且在这些情况下，会抛出错误消息或类似的东西。
问问题
66 次
2 回答
1
这些数字可以建模为图中的一个顶点。然后列表中的每个元素将代表节点之间的一条边。
您正在寻找的是该图的“欧拉路径”。为此有多种算法。查看众所周知的算法：http ://en.wikipedia.org/wiki/Eulerian_path
于 2013-03-11T02:53:39.423 回答
0
您尝试做的不是欧拉路径（访问每个边一次），而是哈密顿路径（访问每个顶点一次），因为您不希望路径中有循环，而循环的定义意味着您没有'不想访问任何顶点两次。
众所周知，这个问题是NP 完全的，这意味着没有已知的有效算法（如果“有效”是指多项式时间）。
如果你能找到一个有效的算法来解决这个问题，你也可以通过证明 P 和 NP 相等来解决P vs NP 问题。大多数计算机科学家认为 P 与 NP 问题的答案是“不，NP 问题的有效算法是不可能的”，这意味着您的问题不可能有有效的算法（尽管仍有待证明）。
于 2013-03-11T07:58:08.063 回答