algorithm - 重新排序列表的元素,以便连续的元素彼此成功?

标签 algorithm list sorting data-structures

给定一个大小为 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/

相关文章:

python - pandas timeseries DF 切片和选择

c# - 列表、排序列表和数组列表之间有什么区别? (C#)

c++ - 寻找原根的更快算法

scala - 将列表转换为映射,其中键为 Scala 中的索引

algorithm - 应用动态规划技术的子问题的独立性

python - 通过将三个列表的元素添加在一起来创建新列表 - 关联错误(PYTHON)

java - 特定项目字段列表的比较器

javascript - 如何仅对数组中的数值进行排序?

algorithm - 具有快速插入和快速搜索的排序序列的最简单 DS 是什么?

algorithm - 在访问某些顶点时在加权图中找到最短路径