algorithm - 订购最大距离的数字集

Question

您有（最多 100 个）不同的（2-4）组数字。集合或集合中数字的顺序无关紧要。最高的数字与套数有关，最高可达 30。如：

{1 2 3 4} {1 2 3 5} {1 2 3} {1 2 4 5} {6 2 4} {6 7 8 9} {6 7 9} {7 8 9} {2 4 8 9}

目标是按特定顺序排列这些集合，其中两个连续的集合不包含共同的数字。那是

{1 2 3 4} {2 4 8 9}

不好（因为 2）。和

{1 2 3 4} {6 7 8 9}

很好。

当然，尤其是在给定的示例中，这对于整个集合是不可能的。但是违反规则的集合的数量应该近似地最小化。

我假设，对于相对大量的集合，一些蛮力+评分算法是不可行的。对于确定性算法来解决此问题，您有任何其他想法或提示吗？

您认为 shuffle + score 算法可以找到不错的解决方案吗（在某些有限的时间范围内，例如 5 秒，标准计算机）？

Answer 1

您可以从集合中创建一个图形，其中顶点是集合，如果它们在列表中可以连续（即没有公共元素），则它们之间存在边。

在此，您可以运行任何找到哈密顿路径的算法，这是一个 NP-hard 问题。

Answer 2

是的，如果算法设计得当，我认为这是可能的。这是在 2.7*10^5 操作中解决 60 个“集合”的类似问题的示例。对于一台普通的现代计算机来说，这个数字似乎已经足够了。