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

Question

这是我的问题:

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

例如，如果我要在 2x2 矩阵中定位数字 1、3、4、9、21，

我可以构建这个矩阵:

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! (654 764 331 820 982 885 260 361 465 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 数字的连续子序列，最低和最高之间的差异最小。然后排列非角边界数字，使(上+左)-(下+右)差异最小，注意每对之间可以插入多少个数字。最后，以任何合法的方式填充中间。

非常简单，这减少了顶部和左侧边缘的总和减去底部和右侧边缘。主要角球加倍；右上角和左下角以及所有内部项都被丢弃。

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