最小列总和差异是多少? [英] What's the minimal column sums difference?
问题描述
假设给定一个正整数矩阵(最大 25*15，数字的值不超过 3000000).当您进行列总和并选择最小和最大的时，它们之间的差必须尽可能小.
Imagine you are given a matrix of positive integer numbers (maximum 25*15, value of number does not exceed 3000000). When you do column sums and pick the smallest and the largest one, the difference between them must be the smallest possible.
您可以在每一行(置换行)中交换数字，而不是在列中交换您想要的次数.
You can swap numbers in every row (permute rows), not in column, how many times you want.
你会如何解决这个任务?
How would you solve this task?
我要的不是你的代码，而是你的想法.
I'm not asking for your code but your ideas.
提前致谢
推荐答案
我会尝试使用模拟退火来解决问题.这是计划的草图:
I would make an attempt to solve the problem using Simulated Annealing. Here is a sketch of the plan:
- 让距离优化最大和最小列总和之间的差异.
- 将目标设置为 0(即，尽量接近矩阵，且总和之间没有差异)
- 通过计算所有列的总和与其当前值的数组来初始化问题.
- 让当前矩阵的 邻居 为交换矩阵同一行中的两个条目所产生的矩阵.
- 通过行索引和两个交换列索引来表示邻居.
- 接受邻居时，不要再次计算所有总和.只需调整已交换的列中的总和数组以及交换的差异(您可以从交换的行索引中推断出)
- Let the distance to optimize the difference between the max and min column sums.
- Set the goal to be 0 (i.e., try to reach as close as possible to a matrix with no difference between sums)
- Initialize the problem by calculating the array of sums of all columns to their current value.
- Let a neighbor of the current matrix be the matrix that results from swapping two entries in the same row of the matrix.
- Represent neighbors by their row index and two swapping column indexes.
- When accepting a neighbor, do not compute all sums again. Just adjust the array of sums in the columns that have been swapped and by the difference of the swap (which you can deduce from the swapped row index)
第 6 步对于性能至关重要(大型矩阵).
Step 6 is essential for the sake of performance (large matrices).
这篇关于最小列总和差异是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
