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

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

您的问题是旅行商问题的一个稍微伪装的实例。

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

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

很容易看出，对于任何循环排列，该排列的成本（根据 计算d）n*M - sum of squares of differences因此是最小的，当且仅当差的平方和最大化时。

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

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

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