将一组数字排序以最大化相邻差异

Question

给定一组N个数字x1, x2, ..., xN，如何找到它们的排序方式以最大化相邻数字之间的最小绝对差？这可能是一个NP困难问题，因此任何有效的近似方法都可以。

- Victor Liu

---

仅仅按照从低到高或从高到低的顺序排序不是最好的解决方案吗？您需要寻找哪种语言的解决方案？可以参考这些排序算法：）http://faculty.cs.niu.edu/~hutchins/csci230/sorting.htm - haxxxton

不，排序顺序实际上是最差的。对于1-5这些数字，排序为1、3、5、2、4更好，因为任何相邻两个数字之间的最小差值为2。 - Victor Liu

好的，抱歉，我误解了你所说的“最大化最小差异”的意思。（我建议在你的问题中去掉“最小”这个词） - haxxxton

这很重要，因为我想在L-infinity范数中进行优化，而不是其他任何范数（如L2）。 - Victor Liu

Answer 1

假设您已将数据定义为x_i，其中i=1，...，n。我们可以定义二进制变量p_{ij}，其中i=1，...，n，j=1，...，n，如果数字i按排序顺序j，则为1，否则为0。添加一个变量e，我们的优化模型可能如下所示：

绝对值的限制条件确保了e（我们的最小间隔）不超过排序序列中每对相邻元素之间的间隔。然而，在线性优化模型中，绝对值是不允许的，通常需要添加一个二进制变量来表示绝对值大于或等于某个其他值。因此，让我们添加二进制变量r_j，其中j=2，...，n，并替换我们有问题的约束条件：

这里M是一个很大的数字；2（max（x）-min（x））应该足够大。现在，我们准备实际实施这个模型。您可以使用任何MIP求解器;我将在R中使用lpSolveAPI，因为它是免费和易于访问的。p_{ij}存储在变量1到n ^ 2中; r_j存储在变量n ^ 2 + 1到n ^ 2 + n-1中; e存储在变量n ^ 2 + n中。

x = 1:5
n = length(x)
M = 2*(max(x) - min(x))
library(lpSolveAPI)
mod = make.lp(0, n^2+n)
set.type(mod, 1:(n^2+n-1), "binary")
set.objfn(mod, c(rep(0, n^2+n-1), 1))
lp.control(mod, sense="max")
for (j in 2:n) {
  base.cons <- rep(0, n^2+n)
  base.cons[seq(j-1, by=n, length.out=n)] = x
  base.cons[seq(j, by=n, length.out=n)] = -x
  base.cons[n^2+j-1] = M
  first.cons = base.cons
  first.cons[n^2+n] = -1
  add.constraint(mod, first.cons, ">=", 0)
  second.cons = -base.cons
  second.cons[n^2+n] = -1
  add.constraint(mod, second.cons, ">=", -M)
}

for (j in 1:n) {
  this.cons = rep(0, n^2+n)
  this.cons[seq(j, by=n, length.out=n)] = 1
  add.constraint(mod, this.cons, "=", 1)
}

for (i in 1:n) {
  this.cons = rep(0, n^2+n)
  this.cons[seq((i-1)*n+1, i*n)] = 1
  add.constraint(mod, this.cons, "=", 1) 
}

现在我们已经准备好解决这个模型了：

solve(mod)
# [1] 0
get.objective(mod)
# [1] 2
get.variables(mod)
# [1] 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 2

最后，我们可以使用 x_i 和 p_{ij} 变量提取排序后的列表：

sapply(1:n, function(j) sum(get.variables(mod)[seq(j, by=n, length.out=n)]*x))
# [1] 1 3 5 2 4

- josliber