关于带权皇后矩阵一个问题的求解,求一个高效的算法就是n行n列的矩阵,从中选n个数,要求这n个数都不同行不同列,并使这n个数中的最大值最小.如下面的3*3矩阵：123456789如果选择159,那

Question

关于带权皇后矩阵一个问题的求解,求一个高效的算法
就是n行n列的矩阵,从中选n个数,要求这n个数都不同行不同列,并使这n个数中的最大值最小.
如下面的3*3矩阵：
1 2 3
4 5 6
7 8 9
如果选择 1 5 9,那么这个最大数值就是9
如果选择 7 2 6,那么这个最大数值就是7
.
.
.
.
有很多中选择,找出一个选择,使它们中的最大值最小.
要求时间复杂度小.所以不能用全排列来一一比较!
想找一个比较好的算法!

Answer 1

这个其实应该叫"带权车"问题了吧?斜线没有限制呢.
是这样,由于只是横竖方向上不能冲突,所以一个可行解经过"行间"调换之后,仍然是一个可行解.
那么利用这一点,就可以进行贪心.
先将所有数字排序,然后每一行的数字也进行排序.排序的时候不是原地的,而是新开两个表.同时记录下每个数字对应的行列.
接下来先生成一个任意解,比如(1,1)(2,2)...(n,n).
然后,从大到小扫描对全部数字排序的数组.每次扫描到数字K,就先判断K是否在解之中(可以使用二维hash判断),然后尝试优化这个解.
优化的方式是,挨个的找数字K在它那行上的下一个比它小的数字P,然后尝试交换P所在列上冲突的那个数字,交换到K那行上去,看看会不会超过K.不会则交换,然后重新找K.否则继续找P
直到某一次找P失败,则解已经最优.
对于你的例子.
一开始的解集是{1,5,9}
第一大的数字是9,优化9.这行第二小是8.交换5-6.9-8,因为6