给定一个大小为 n 的项目 l 的列表,并给定谓词 succeeds(i1,i2)
如果 i2
成功 i1
则返回 true >,什么是重新排列 l 的元素的最佳算法,以便对于 l 中的所有项目 i,succeeds(i,i.next)
返回 true?
最佳答案
如果对成功关系可以是什么没有限制(也就是说,它不必是传递的、自反的、对称的等),那么我认为这个问题是 NP-hard 的NP难 Hamiltonian path problem 强>。归约实际上非常简单:给定一个图 G,创建图中具有成功关系的节点数组,使得 v 成功 u 当且仅当在原始图中存在从 u 到 v 的边。使用此设置,找到一种通过成功关系(连接它们的边)对数组元素(节点)进行排序的方法等同于在原始图中找到哈密顿路径,因为每个节点只被访问一次。因此,除非 P = NP,否则您不太可能为此找到有效的算法。
对于负面结果,我们深表歉意,希望这对您有所帮助!
关于algorithm - 重新排序列表的元素,以便连续的元素彼此成功?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9309786/