2

私は誰かがこれを行うための効率的な方法を私に指摘できるかどうか疑問に思っていました：

すべての列で正確に3つの要素が選択され、すべての行で5つの要素が選択されるように、6行x10列の配列で選択された要素の合計を最大化します。

割り当ての問題（およびハンガリーのアルゴリズム）をこのタスクに拡張する簡単な方法がわかりません。より大きな問題のためにこれらの何千ものことをする必要があるので、ブルートフォースは問題外です。

4

1 に答える 1

2

Vaughnが書いたように、問題を解決するための迅速で簡単な方法は、整数線形計画問題に変換してから、多くの特殊なソルバーの1つで解決することです。やってみよう！

モデリング

まず、モデリング言語が必要です。GNUモデリング言語であるMathProgを使用します。これは、AMPL（のサブセット）に非常によく似ています。

問題の一般的なモデル：（max.mod）

param rows;
param columns;
param matrix{i in 1..rows, j in 1..columns}; # the input matrix

## the variables of our problem. choose[i,j] = 1 means that we 
## pick element (i,j), otherwise is choose[i,j] = 0
var choose{i in 1..rows, j in 1..columns} binary; 

## the linear function we want to maximize: the sum of all the 
## choosen elements in the matrix.
maximize Sum:
    sum{i in 1..rows, j in 1..columns} choose[i,j] * matrix[i,j];

## first linear constraint: we have to choose exactly 3 elements for each column
subject to Cols{j in 1..columns}:
    sum{i in 1..rows} choose[i,j] = 3;

## second linear constraint: we have to choose exactly 5 elements for each row
subject to Rows{i in 1..rows}:
    sum{j in 1..columns} choose[i,j] = 5;

solve;

## to print the solution
printf "Solution: \n";
for{i in 1..rows}
{
    for{j in 1..columns}
    {
        printf (if choose[i,j] = 1 then "%d " else "- "), matrix[i,j];
    }
    printf "\n";
}
printf "\nSum = %d", sum{i in 1..rows, j in 1..columns} choose[i,j]*matrix[i,j];

データファイルも必要です：（max.dat）

param rows := 6;
param columns := 10;

param matrix : 
    1 2 3 4 5 6 7 8 9 10 :=
1   1 6 9 1 0 7 5 4 3 2
2   9 7 4 6 4 3 2 1 4 9
3   9 6 4 3 2 1 5 7 8 9
4   6 5 4 3 7 8 9 6 4 2
5   7 5 4 3 2 8 9 6 7 8 
6   9 7 6 5 3 9 6 3 2 1;

解決する

ここで、ソルバーが必要です。コマンドラインから素敵なGLPK（GNU線形計画法キット）を使用しますが、それはたくさんのプログラミング言語への素敵なインターフェースのセットを持っています。

alberto@alberto-notebook:~/Desktop$ glpsol --model max.mod --data max.dat

INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.2 Mb (235703 bytes)

Solution: 
- 6 9 - - 7 5 - 3 - 
9 7 - 6 4 - - - - 9 
9 - - 3 - - - 7 8 9 
- - 4 - 7 8 9 6 - - 
- - - - - 8 9 6 7 8 
9 7 6 5 3 - - - - - 

Sum = 203
于 2012-11-18T14:31:07.487 に答える