组织矩阵以使邻居最近的算法

Question

我的问题是：

我想把N个正整数组织成一个AxB矩阵，这样相邻单元之间的差异就最小化了。N大于AxB，所以我有很多可能的选择。

例如，如果我把数字1,3,4,9,21放在2x2矩阵中，

我可以建立这个矩阵：

5 4
1 9

我们可以计算相邻单元之间的差之和：(5-4) + (5-1) + (9-4) + (9-1) = 1+4+5+8 = 18。

但如果我这样重新排列数字：

1 4
5 9

现在之和为(5-1)+(4-1)+(9-5)+(9-4) = 4+3+4+5 = 16。

我想使用蛮力，通过转换每个数并每次计算和，但我的实际问题是有一个4*5矩阵和41个数字可供选择，因此可能的矩阵数是41!/20！(654764331 882 885 3665 856)。

有没有人知道如何以不同的方式解决这个问题？

Answer 1

这实际上是一个更容易解决的问题。用你的小学代数来打。首先，一个小小的洞察力会显示，你总是希望把数字从左上角到右下角排序。无论是上升还是下降都可以；它们是同构的。让我们假设上升，以匹配您的例子。对于一组9个数字：

i1 i2 i3
i4 i5 i6
i7 i8 i9

我们需要把这些条件加起来

// ROWS
i2-i1 + i3-i2 +
i5-i4 + i6-i5 +
i8-i7 + i9-i8 +
// COLUMNS
i4-i1 + i7-i4 +
i5-i2 + i8-i5 +
i6-i3 + i9-i6

这将减少到i3-i1 + i6-i4 + i9-i7 + i7-i1 + i8-i2 + i9-i3。

然后变成2*i9 - 2*i1 + i6+i8 - (i2+i4)

首先对您的N数进行排序，并找到A*B数的连续子序列，最低和最高之间的差值最小。然后排列非角边框数，以使(upper+left) - (lower+right)差最小化，注意每对之间可以有多少个数字。最后，以任何合法的方式在中间填写。

非常简单，这减少到上边和左边的和，减去底部和右边的边。主角数双倍；右上角和左下角，以及所有内部术语，退出.

是的，我忽略了一些逻辑步骤.我希望这对你来说已经足够了。它将从A*B数到N数的搜索空间缩减为A*B序列中A+B-2数的两个连续序列。

Answer 2

不知道只是排序是否最理想。但这当然是一个很好的起点。对于随机数据集，我看到：

​

​

第二种解决方案是用混合整数编程模型实现的。它被证明是最优的(但我添加了一个约束，即值在行和列上都在增加)。

Answer 3

仅仅以一种聪明的方式填写矩阵不是一个好的开始吗？

假设您有以下数字:1、2、4、6、7、8、9、13、17不能按以下方式填写矩阵:从角落中的最低数开始，填写矩阵如下：

i1 i2 i4
i3 i5 i7
i6 i8 i9

这将导致以下情况：

1   2   6
4   7   9
8   13  17

从这个开始的结果，你可以尝试交换随机位置，看看每一个数字的和邻居得到的更低。如果结果较低，则重复此操作，否则将尝试不同的交换。

我不知道这是否会很快陷入局部最小退出，你也可以选择做多个掉期，然后再评估结果是否变低。

编辑:我现在看到你更多的数字，那实际上符合矩阵。我想这些都是独一无二的。因此，选择一个平均差最小的子集可能也会产生一个邻域和最小的矩阵。

祝好运