python - 重新排序列表以最大化相邻元素的差异

Question

我有兴趣以最大化相邻元素(循环)之间差异的平方和的方式重新排序列表。这是一段 Python 代码，它在阶乘时间内暴力破解解决方案，因此您可以明白我的意思:

def maximal_difference_reorder(input):

   from itertools import permutations

   best_sum = 0
   best_orderings = []

   for x in permutations(input):
        d = np.sum(np.diff(x)**2) + (x[0] - x[-1])**2
        if d > best_sum:
            best_orderings = [x]
            best_sum = d
        elif d == best_sum:
            best_orderings.append(x)

   return best_orderings

这会为 maximal_difference_reorder(range(4)) 产生以下结果:

[(0, 2, 1, 3),
 (0, 3, 1, 2),
 (1, 2, 0, 3),
 (1, 3, 0, 2),
 (2, 0, 3, 1),
 (2, 1, 3, 0),
 (3, 0, 2, 1),
 (3, 1, 2, 0)]

如你所见，所有的结果都是循环旋转，相互反射。如果分数是由差值之和决定的，而不是平方，我相信所有的排列都会得到均匀的分数，给定一个均匀间隔的输入。

暴力破解效果很好，但 O(n!) 很糟糕，那么是否有可能在更小的渐近计算时间内做到这一点？如果它适用于不均匀的输入网格或其他评分函数，则可加分。

顺便说一句，这不是家庭作业或面试问题，尽管它可能是一个很好的问题。相反，我试图为一系列参数化数据生成一系列颜色，并且我试图避免彼此相邻的相似颜色。

Answer 1

您的问题是 Traveling Salesman Problem 的一个稍微伪装的实例.

调用输入列表c(对于“城市”)。选择任何 M 是 (c[i]-c[j])**2 的上限 这很容易在线性时间内完成，因为最小值和最大值列表的 可以在单次通过中计算，在这种情况下 M = (max - min)**2 有效。通过以下方式定义从 c[i] 到 c[j] 的距离 d[i,j]:

d(i,j) = 0 if i == j else M - (c[i]-c[j])**2

很容易看出，对于任何循环排列，该排列的成本(根据 d 计算)是 n*M - 差的平方和 因此它当且仅当差异的平方和最大化时，它才被最小化。

解决 TSP 的方法有很多种。尽管它是 NP-hard，但在实践中，最先进的方法非常擅长解决实践中出现的问题。此外，好的启发式方法通常可以达到最优值的百分之几。

您的特定问题是 TSP 的特例。因此，这种特殊情况可能更容易，并且实际上有一个多项式时间解，但我对此表示怀疑。我猜想它也是 NP-hard 但没有证据。另外——即使它是 NP 难的，也可能有一种解决方案(可能是整数规划公式)比将其简化为上述 TSP 更有效。

关于编辑:根据 Dave Gavin 的评论和@SergeBallesta 的回答，我现在认为多项式时间算法是可能的。我会留下这个答案，如果除了多项式时间算法有效之外没有其他原因，那么这个问题将是一个很好的例子，表明 TSP 的某些子类有更简单的解决方案。