3

假设给定一个方阵 A。我们的目标是通过行排列最大化最小对角线元素。换句话说，对于给定的矩阵 A，我们有 n 个对角线元素，因此我们有最小的 $min{d_i}$。我们的目的是通过行排列达到可能具有最大最小对角线元素的矩阵。

这就像所有行排列的 $max min{d_i}$ 。

例如，假设 A = [4 3 2 1; 1 4 3 2; 2 1 4 3; 2.5 3.5 4.5 1.5]。对角线是 [4, 4, 4, 1.5]。对角线的最小值为 1.5。我们可以交换第 3 行和第 4 行得到一个新矩阵 \tilde_A = [4 3 2 1; 1 4 3 2; 2.5 3.5 4.5 1.5；2 1 4 3]。新的对角线是 [4, 4, 4.5, 3]，新的最小值为 3。理论上，这是我能得到的最好结果，因为似乎没有更好的选择：3 似乎是最大值 min{d_i}。

在我的问题中，n 比 1000 大得多。我知道有 n！行排列，所以理论上我无法遍历每个排列。我知道贪心算法会有所帮助——我们从第一行开始。如果 a_11 不是第一列中的最小元素，我们将 a_11 与第一列中的最大元素逐行置换。然后我们通过将 a_22 与第二列中的所有剩余元素（a_12 除外）进行比较来查看第二行。如果 a_22 不是最小的，则交换它。... ...等等。我们一直这样做到最后一行。

有没有更好的算法来做到这一点？

这类似于最小欧几里得匹配，但它们并不相同。

4

2 回答 2

4

Suppose you wanted to know whether there was a better solution to your problem than 3.

Change your matrix to have a 1 for every element that is strictly greater than 3:

4    3   2   1     1 0 0 0
1    4   3   2     0 1 0 0
2.5 3.5 4.5 1.5 -> 0 1 1 0
2    1   4   3     0 0 1 0

Your problem can be interpreted as trying to find a perfect matching in the bipartite graph which has this binary matrix as its biadjacency graph.

In this case, it is easy to see that there is no way of improving your result because there is no way of reordering rows to make the diagonal entry in the last column greater than 3.

For a larger matrix, there are efficient algorithms to determine maximal matchings in bipartite graphs.

This suggests an algorithm:

  1. Use bisection to find the largest value for which the generated graph has a perfect matching
  2. The assignment corresponding to the perfect matching with the largest value will be equal to the best permutation of rows

EDIT

This Python code illustrates how to use the networkx library to determine whether the graph has a perfect matching for a particular cutoff value.

import networkx as nx

A = [[4,3,2,1],
     [1,4,3,2],
     [2,1,4,3],
     [2.5,3.5,4.5,1.5]]

cutoff = 3
G=nx.DiGraph()
for i,row in enumerate(A):
    G.add_edge('start','row'+str(i),capacity=1.0)
    G.add_edge('col'+str(i),'end',capacity=1.0)
    for j,e in enumerate(row):
        if e>cutoff:
            G.add_edge('row'+str(i),'col'+str(j),capacity=1.0)

if nx.max_flow(G,'start','end')<len(A):
    print 'No perfect matching'
else:
    print 'Has a perfect matching'

For a random matrix of size 1000*1000 it takes about 1 second on my computer.

于 2013-10-15T17:58:16.870 回答
2

如果将第 i 行移动到第 j 行，则令 $x_{ij}$ 为 1，否则为 0。

您对以下整数程序感兴趣：

最大 z

\sum_{i=0}^n x_{ij} = 1 \forall j

\sum_{j=0}^n x_{ij} = 1 \forall i

A[j,j]x_{ij} >= z

然后将其插入 GLPK、Gurobi 或 CPLEX。或者，使用您自己的分支定界求解来求解 IP。

于 2013-10-15T17:52:13.877 回答