组织矩阵以使邻居最接近的算法
Algorithm to organize a matrix so that neighbors are closest
这是我的问题：
我想将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 ！ (654 764 331 820 982 885 260 361 465 856).
有没有人知道如何以不同的方式解决问题？
以巧妙的方式填充矩阵不是一个好的开始吗？
假设您有以下数字：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
根据这个开始结果，您可以尝试交换随机位置，看看每个相邻数字的总和是否更低。如果结果变低，重复此操作，否则尝试不同的交换。
我不知道这是否会遇到局部最小值快速退出，您也可以选择在评估结果是否变低之前进行多次交换。
编辑：
我现在看到你比实际适合矩阵的数字更多。我认为这些都是独一无二的。因此，选择一个具有最低平均差异的子集也可能会导致一个具有最低邻居和的矩阵。
祝你好运
这其实是一道比较简单的题。用你的小学代数来解决它。
首先，稍微了解一下就会发现您总是希望数字按照从左上角到右下角的顺序排序。上升或下降都可以；他们是同构的。让我们假设升序，以匹配您的示例。对于一组 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 个数字的连续子序列，其中最低和最高之间的差异最小。然后排列非角边界数字，使（上+左）-（下+右）差异最小，注意每对之间可以插入多少个数字。最后，以任何合法方式填写中间。
非常简单，这减少了顶部和左侧边缘的总和，减去底部和右侧边缘。主要角球加倍；右上角和左下角以及所有内部项都被丢弃。
是的，我省略了一些逻辑步骤...我希望这对您来说已经足够提示了。它将搜索 space 从 N 中的 A*B 数字减少到 A*B.
序列中两个连续的 A+B-2 数字序列
要回到@Prune 解决方案和不同的评论，理解生成的方程式很重要。
因为数字在每一行和每一列上排序，所以带有 abs() 的全局方程简化为 for all lines and columns sum(last-first).
生成的等式包含六个相加的组 2*RB - 2*TL + RE + BE - LE - TE 其中：
- 左上角元素的两倍为负数：TL
- 右下角元素的两倍为正：RB
- 最右列除角点外所有元素的总和：RE
- 底线上除角点外所有元素之和：BE
- 最左列除角点外所有元素的总和：LE
- 顶行除角点外所有元素之和：TE
想法是最小化所选 RB 和 TL 元素的 RE + BE - LE - TE 边缘元素。
如果我们将此公式应用于下面的矩阵，边缘元素的结果为 8+12+14+15-2-3-5-9 = 49-19 = 30
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
如果我们将此公式应用于下面的矩阵，边缘元素的结果是 11+14+13+15-2-4-3-6 = 53-15 = 38，这不是最小值。
1 2 4 7
3 5 8 11
6 9 12 14
10 13 15 16
因此，就此而言，边缘分量的最小化似乎是一种不错的方法。 问题是如何在遵守>沿行和列的规则的同时最小化这个元素。然而，从左到右、从上到下依次用数字填充矩阵可能会得到足够好的结果。
关于您的矩阵 4*5 有 41 个可用值的问题，比较您在对这 41 个数字排序后获得的 22 个矩阵，线性填充它们并查看矩阵 s 极端元素之间的间隙最小（我刚刚意识到你可以有几个矩阵，第一个和最后一个元素之间的距离相同但总距离不同）实际上是一个 s 最小 "distance" 由 abs() 公式定义。
让我们知道。
附录
这里有一些示例，用于 4x5（行 x 列）矩阵。我很想看看其他方法的结果，看看该方法离理想有多远！
Elements = [3, 6, 59, 75, 76, 120, 132, 140, 226, 233, 237, 296, 349, 351, 351, 381, 422, 468, 478, 499, 523, 540, 570, 588, 597, 629, 687, 707, 714, 740, 742, 746, 755, 781, 812, 845, 897, 902, 927, 982, 999]
Distances for the 22 possible matrices = [2447, 2459, 2420, 2464, 2510, 2386, 2336, 2357, 2318, 2319, 2310, 2192, 2096, 2093, 2038, 1961, 1893, 1952, 2000, 2025, 2127, 2128]
List of indexes where min values are = [16]
Minimum value found = 1893
Matrix found = [422, 468, 478, 499, 523, 540, 570, 588, 597, 629, 687, 707, 714, 740, 742, 746, 755, 781, 812, 845]
Elements = [37, 45, 55, 78, 87, 110, 142, 157, 287, 294, 302, 309, 313, 333, 356, 379, 380, 406, 422, 456, 461, 466, 467, 475, 506, 551, 556, 575, 578, 610, 689, 717, 748, 757, 773, 935, 944, 954, 956, 994, 998]
Distances for the 22 possible matrices = [2106, 2126, 2105, 1921, 1866, 1745, 1679, 1574, 1402, 1411, 1492, 1687, 1766, 1876, 1882, 1906, 2322, 2433, 2603, 2658, 2655, 2871]
List of indexes where min values are = [8]
Minimum value found = 1402
Matrix found = [287, 294, 302, 309, 313, 333, 356, 379, 380, 406, 422, 456, 461, 466, 467, 475, 506, 551, 556, 575]
Elements = [25, 26, 28, 78, 80, 92, 93, 100, 115, 149, 170, 209, 222, 252, 269, 333, 344, 366, 371, 371, 384, 412, 437, 446, 469, 498, 547, 553, 557, 563, 597, 626, 642, 730, 756, 771, 771, 793, 798, 856, 937]
Distances for the 22 possible matrices = [1797, 1839, 1875, 1841, 1885, 1878, 1962, 2041, 2042, 1990, 1883, 1832, 1827, 1793, 1907, 1913, 2010, 2124, 2167, 2211, 2235, 2340]
List of indexes where min values are = [13]
Minimum value found = 1793
Matrix found = [252, 269, 333, 344, 366, 371, 371, 384, 412, 437, 446, 469, 498, 547, 553, 557, 563, 597, 626, 642]
Elements = [19, 82, 97, 108, 123, 162, 178, 207, 224, 243, 264, 290, 307, 333, 350, 364, 393, 419, 428, 459, 514, 582, 646, 679, 696, 698, 758, 761, 786, 815, 833, 853, 875, 875, 894, 902, 905, 923, 959, 961, 962]
Distances for the 22 possible matrices = [2000, 2002, 2147, 2337, 2475, 2547, 2582, 2693, 2733, 2740, 2754, 2695, 2754, 2778, 2745, 2722, 2547, 2446, 2307, 2138, 1952, 1706]
List of indexes where min values are = [21]
Minimum value found = 1706
Matrix found = [582, 646, 679, 696, 698, 758, 761, 786, 815, 833, 853, 875, 875, 894, 902, 905, 923, 959, 961, 962]
Elements = [190, 220, 240, 249, 259, 264, 349, 353, 365, 380, 392, 399, 410, 427, 437, 491, 501, 522, 564, 578, 621, 627, 639, 643, 657, 662, 668, 684, 712, 713, 714, 733, 782, 804, 840, 881, 909, 910, 911, 944, 990]
Distances for the 22 possible matrices = [1815, 1853, 1902, 1874, 1863, 1760, 1679, 1651, 1624, 1669, 1593, 1620, 1564, 1557, 1569, 1517, 1603, 1614, 1607, 1625, 1644, 1746]
List of indexes where min values are = [15]
Minimum value found = 1517
Matrix found = [491, 501, 522, 564, 578, 621, 627, 639, 643, 657, 662, 668, 684, 712, 713, 714, 733, 782, 804, 840]
Elements = [50, 64, 82, 114, 142, 173, 181, 183, 228, 237, 279, 340, 340, 356, 359, 379, 400, 415, 425, 427, 453, 532, 547, 587, 606, 619, 650, 671, 687, 707, 718, 739, 765, 803, 832, 837, 853, 861, 917, 923, 954]
Distances for the 22 possible matrices = [1878, 1844, 1993, 1953, 2070, 2068, 2060, 2179, 2086, 2107, 2029, 1906, 2036, 2050, 2157, 2214, 2162, 2214, 2144, 2176, 2107, 1971]
List of indexes where min values are = [1]
Minimum value found = 1844
Matrix found = [64, 82, 114, 142, 173, 181, 183, 228, 237, 279, 340, 340, 356, 359, 379, 400, 415, 425, 427, 453]
Elements = [48, 49, 75, 107, 108, 126, 132, 142, 142, 167, 170, 216, 220, 222, 246, 250, 253, 269, 374, 425, 464, 469, 484, 505, 539, 540, 602, 620, 641, 677, 719, 748, 751, 777, 817, 830, 893, 904, 932, 952, 997]
Distances for the 22 possible matrices = [1536, 1680, 1817, 1871, 1994, 2119, 2138, 2258, 2241, 2312, 2469, 2538, 2693, 2678, 2690, 2726, 2619, 2655, 2467, 2426, 2482, 2515]
List of indexes where min values are = [0]
Minimum value found = 1536
Matrix found = [48, 49, 75, 107, 108, 126, 132, 142, 142, 167, 170, 216, 220, 222, 246, 250, 253, 269, 374, 425]
Elements = [7, 39, 46, 62, 66, 85, 127, 151, 191, 205, 220, 221, 228, 234, 240, 303, 324, 329, 338, 352, 364, 366, 408, 408, 498, 559, 624, 624, 640, 654, 655, 740, 742, 757, 825, 862, 879, 908, 950, 956, 977]
Distances for the 22 possible matrices = [1674, 1670, 1647, 1628, 1586, 1608, 1753, 1928, 2066, 2162, 2256, 2317, 2449, 2484, 2413, 2521, 2605, 2822, 2942, 2952, 3004, 2875]
List of indexes where min values are = [4]
Minimum value found = 1586
Matrix found = [66, 85, 127, 151, 191, 205, 220, 221, 228, 234, 240, 303, 324, 329, 338, 352, 364, 366, 408, 408]
Elements = [17, 161, 185, 192, 211, 231, 291, 307, 319, 346, 348, 369, 391, 415, 447, 449, 473, 477, 491, 498, 518, 525, 529, 545, 589, 625, 632, 639, 645, 655, 680, 770, 795, 798, 802, 812, 836, 889, 892, 931, 931]
Distances for the 22 possible matrices = [2079, 1729, 1697, 1616, 1524, 1546, 1484, 1526, 1523, 1477, 1475, 1453, 1578, 1628, 1651, 1729, 1755, 1857, 1949, 1952, 1996, 1951]
List of indexes where min values are = [11]
Minimum value found = 1453
Matrix found = [369, 391, 415, 447, 449, 473, 477, 491, 498, 518, 525, 529, 545, 589, 625, 632, 639, 645, 655, 680]
Elements = [10, 23, 29, 50, 61, 71, 72, 82, 137, 147, 249, 262, 267, 295, 303, 340, 346, 366, 369, 415, 489, 500, 582, 659, 662, 667, 683, 705, 716, 731, 734, 776, 785, 803, 819, 841, 877, 883, 949, 951, 995]
Distances for the 22 possible matrices = [1919, 2197, 2292, 2465, 2756, 2761, 2948, 2870, 2774, 2725, 2492, 2541, 2496, 2491, 2541, 2478, 2465, 2384, 2276, 2224, 2041, 1986]
List of indexes where min values are = [0]
Minimum value found = 1919
Matrix found = [10, 23, 29, 50, 61, 71, 72, 82, 137, 147, 249, 262, 267, 295, 303, 340, 346, 366, 369, 415]
不知道只排序是否最优。但这当然是一个很好的起点。使用随机数据集，我看到：
第二个解决方案是通过混合整数规划模型找到的。它被证明是最佳的（但我添加了值按行和列增加的约束）。
这是我的问题：
我想将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 ！ (654 764 331 820 982 885 260 361 465 856).
有没有人知道如何以不同的方式解决问题？
以巧妙的方式填充矩阵不是一个好的开始吗？
假设您有以下数字：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
根据这个开始结果，您可以尝试交换随机位置，看看每个相邻数字的总和是否更低。如果结果变低，重复此操作，否则尝试不同的交换。
我不知道这是否会遇到局部最小值快速退出，您也可以选择在评估结果是否变低之前进行多次交换。
编辑： 我现在看到你比实际适合矩阵的数字更多。我认为这些都是独一无二的。因此，选择一个具有最低平均差异的子集也可能会导致一个具有最低邻居和的矩阵。
祝你好运
这其实是一道比较简单的题。用你的小学代数来解决它。 首先，稍微了解一下就会发现您总是希望数字按照从左上角到右下角的顺序排序。上升或下降都可以；他们是同构的。让我们假设升序，以匹配您的示例。对于一组 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 个数字的连续子序列，其中最低和最高之间的差异最小。然后排列非角边界数字，使（上+左）-（下+右）差异最小，注意每对之间可以插入多少个数字。最后，以任何合法方式填写中间。
非常简单，这减少了顶部和左侧边缘的总和，减去底部和右侧边缘。主要角球加倍；右上角和左下角以及所有内部项都被丢弃。
是的，我省略了一些逻辑步骤...我希望这对您来说已经足够提示了。它将搜索 space 从 N 中的 A*B 数字减少到 A*B.
A+B-2 数字序列
要回到@Prune 解决方案和不同的评论，理解生成的方程式很重要。
因为数字在每一行和每一列上排序，所以带有 abs() 的全局方程简化为 for all lines and columns sum(last-first).
生成的等式包含六个相加的组 2*RB - 2*TL + RE + BE - LE - TE 其中：
- 左上角元素的两倍为负数：TL
- 右下角元素的两倍为正：RB
- 最右列除角点外所有元素的总和：RE
- 底线上除角点外所有元素之和：BE
- 最左列除角点外所有元素的总和：LE
- 顶行除角点外所有元素之和：TE
想法是最小化所选 RB 和 TL 元素的 RE + BE - LE - TE 边缘元素。
如果我们将此公式应用于下面的矩阵，边缘元素的结果为 8+12+14+15-2-3-5-9 = 49-19 = 30
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
如果我们将此公式应用于下面的矩阵，边缘元素的结果是 11+14+13+15-2-4-3-6 = 53-15 = 38，这不是最小值。
1 2 4 7
3 5 8 11
6 9 12 14
10 13 15 16
因此，就此而言，边缘分量的最小化似乎是一种不错的方法。 问题是如何在遵守>沿行和列的规则的同时最小化这个元素。然而，从左到右、从上到下依次用数字填充矩阵可能会得到足够好的结果。
关于您的矩阵 4*5 有 41 个可用值的问题，比较您在对这 41 个数字排序后获得的 22 个矩阵，线性填充它们并查看矩阵 s 极端元素之间的间隙最小（我刚刚意识到你可以有几个矩阵，第一个和最后一个元素之间的距离相同但总距离不同）实际上是一个 s 最小 "distance" 由 abs() 公式定义。
让我们知道。
附录
这里有一些示例，用于 4x5（行 x 列）矩阵。我很想看看其他方法的结果，看看该方法离理想有多远！
Elements = [3, 6, 59, 75, 76, 120, 132, 140, 226, 233, 237, 296, 349, 351, 351, 381, 422, 468, 478, 499, 523, 540, 570, 588, 597, 629, 687, 707, 714, 740, 742, 746, 755, 781, 812, 845, 897, 902, 927, 982, 999]
Distances for the 22 possible matrices = [2447, 2459, 2420, 2464, 2510, 2386, 2336, 2357, 2318, 2319, 2310, 2192, 2096, 2093, 2038, 1961, 1893, 1952, 2000, 2025, 2127, 2128]
List of indexes where min values are = [16]
Minimum value found = 1893
Matrix found = [422, 468, 478, 499, 523, 540, 570, 588, 597, 629, 687, 707, 714, 740, 742, 746, 755, 781, 812, 845]
Elements = [37, 45, 55, 78, 87, 110, 142, 157, 287, 294, 302, 309, 313, 333, 356, 379, 380, 406, 422, 456, 461, 466, 467, 475, 506, 551, 556, 575, 578, 610, 689, 717, 748, 757, 773, 935, 944, 954, 956, 994, 998]
Distances for the 22 possible matrices = [2106, 2126, 2105, 1921, 1866, 1745, 1679, 1574, 1402, 1411, 1492, 1687, 1766, 1876, 1882, 1906, 2322, 2433, 2603, 2658, 2655, 2871]
List of indexes where min values are = [8]
Minimum value found = 1402
Matrix found = [287, 294, 302, 309, 313, 333, 356, 379, 380, 406, 422, 456, 461, 466, 467, 475, 506, 551, 556, 575]
Elements = [25, 26, 28, 78, 80, 92, 93, 100, 115, 149, 170, 209, 222, 252, 269, 333, 344, 366, 371, 371, 384, 412, 437, 446, 469, 498, 547, 553, 557, 563, 597, 626, 642, 730, 756, 771, 771, 793, 798, 856, 937]
Distances for the 22 possible matrices = [1797, 1839, 1875, 1841, 1885, 1878, 1962, 2041, 2042, 1990, 1883, 1832, 1827, 1793, 1907, 1913, 2010, 2124, 2167, 2211, 2235, 2340]
List of indexes where min values are = [13]
Minimum value found = 1793
Matrix found = [252, 269, 333, 344, 366, 371, 371, 384, 412, 437, 446, 469, 498, 547, 553, 557, 563, 597, 626, 642]
Elements = [19, 82, 97, 108, 123, 162, 178, 207, 224, 243, 264, 290, 307, 333, 350, 364, 393, 419, 428, 459, 514, 582, 646, 679, 696, 698, 758, 761, 786, 815, 833, 853, 875, 875, 894, 902, 905, 923, 959, 961, 962]
Distances for the 22 possible matrices = [2000, 2002, 2147, 2337, 2475, 2547, 2582, 2693, 2733, 2740, 2754, 2695, 2754, 2778, 2745, 2722, 2547, 2446, 2307, 2138, 1952, 1706]
List of indexes where min values are = [21]
Minimum value found = 1706
Matrix found = [582, 646, 679, 696, 698, 758, 761, 786, 815, 833, 853, 875, 875, 894, 902, 905, 923, 959, 961, 962]
Elements = [190, 220, 240, 249, 259, 264, 349, 353, 365, 380, 392, 399, 410, 427, 437, 491, 501, 522, 564, 578, 621, 627, 639, 643, 657, 662, 668, 684, 712, 713, 714, 733, 782, 804, 840, 881, 909, 910, 911, 944, 990]
Distances for the 22 possible matrices = [1815, 1853, 1902, 1874, 1863, 1760, 1679, 1651, 1624, 1669, 1593, 1620, 1564, 1557, 1569, 1517, 1603, 1614, 1607, 1625, 1644, 1746]
List of indexes where min values are = [15]
Minimum value found = 1517
Matrix found = [491, 501, 522, 564, 578, 621, 627, 639, 643, 657, 662, 668, 684, 712, 713, 714, 733, 782, 804, 840]
Elements = [50, 64, 82, 114, 142, 173, 181, 183, 228, 237, 279, 340, 340, 356, 359, 379, 400, 415, 425, 427, 453, 532, 547, 587, 606, 619, 650, 671, 687, 707, 718, 739, 765, 803, 832, 837, 853, 861, 917, 923, 954]
Distances for the 22 possible matrices = [1878, 1844, 1993, 1953, 2070, 2068, 2060, 2179, 2086, 2107, 2029, 1906, 2036, 2050, 2157, 2214, 2162, 2214, 2144, 2176, 2107, 1971]
List of indexes where min values are = [1]
Minimum value found = 1844
Matrix found = [64, 82, 114, 142, 173, 181, 183, 228, 237, 279, 340, 340, 356, 359, 379, 400, 415, 425, 427, 453]
Elements = [48, 49, 75, 107, 108, 126, 132, 142, 142, 167, 170, 216, 220, 222, 246, 250, 253, 269, 374, 425, 464, 469, 484, 505, 539, 540, 602, 620, 641, 677, 719, 748, 751, 777, 817, 830, 893, 904, 932, 952, 997]
Distances for the 22 possible matrices = [1536, 1680, 1817, 1871, 1994, 2119, 2138, 2258, 2241, 2312, 2469, 2538, 2693, 2678, 2690, 2726, 2619, 2655, 2467, 2426, 2482, 2515]
List of indexes where min values are = [0]
Minimum value found = 1536
Matrix found = [48, 49, 75, 107, 108, 126, 132, 142, 142, 167, 170, 216, 220, 222, 246, 250, 253, 269, 374, 425]
Elements = [7, 39, 46, 62, 66, 85, 127, 151, 191, 205, 220, 221, 228, 234, 240, 303, 324, 329, 338, 352, 364, 366, 408, 408, 498, 559, 624, 624, 640, 654, 655, 740, 742, 757, 825, 862, 879, 908, 950, 956, 977]
Distances for the 22 possible matrices = [1674, 1670, 1647, 1628, 1586, 1608, 1753, 1928, 2066, 2162, 2256, 2317, 2449, 2484, 2413, 2521, 2605, 2822, 2942, 2952, 3004, 2875]
List of indexes where min values are = [4]
Minimum value found = 1586
Matrix found = [66, 85, 127, 151, 191, 205, 220, 221, 228, 234, 240, 303, 324, 329, 338, 352, 364, 366, 408, 408]
Elements = [17, 161, 185, 192, 211, 231, 291, 307, 319, 346, 348, 369, 391, 415, 447, 449, 473, 477, 491, 498, 518, 525, 529, 545, 589, 625, 632, 639, 645, 655, 680, 770, 795, 798, 802, 812, 836, 889, 892, 931, 931]
Distances for the 22 possible matrices = [2079, 1729, 1697, 1616, 1524, 1546, 1484, 1526, 1523, 1477, 1475, 1453, 1578, 1628, 1651, 1729, 1755, 1857, 1949, 1952, 1996, 1951]
List of indexes where min values are = [11]
Minimum value found = 1453
Matrix found = [369, 391, 415, 447, 449, 473, 477, 491, 498, 518, 525, 529, 545, 589, 625, 632, 639, 645, 655, 680]
Elements = [10, 23, 29, 50, 61, 71, 72, 82, 137, 147, 249, 262, 267, 295, 303, 340, 346, 366, 369, 415, 489, 500, 582, 659, 662, 667, 683, 705, 716, 731, 734, 776, 785, 803, 819, 841, 877, 883, 949, 951, 995]
Distances for the 22 possible matrices = [1919, 2197, 2292, 2465, 2756, 2761, 2948, 2870, 2774, 2725, 2492, 2541, 2496, 2491, 2541, 2478, 2465, 2384, 2276, 2224, 2041, 1986]
List of indexes where min values are = [0]
Minimum value found = 1919
Matrix found = [10, 23, 29, 50, 61, 71, 72, 82, 137, 147, 249, 262, 267, 295, 303, 340, 346, 366, 369, 415]
不知道只排序是否最优。但这当然是一个很好的起点。使用随机数据集，我看到：
第二个解决方案是通过混合整数规划模型找到的。它被证明是最佳的（但我添加了值按行和列增加的约束）。