matchpairs

線形の割り当て問題の解決

構文

M = matchpairs(Cost,costUnmatched)

[M,uR,uC] = matchpairs(Cost,costUnmatched)

[___] = matchpairs(Cost,costUnmatched,goal)

説明

M = matchpairs(Cost,costUnmatched) は、行列 Cost の行と列の線形の割り当て問題を解決します。各行は、合計コストが最小化されるような方法で列に割り当てられます。costUnmatched は、各行を割り当てないときの行あたりのコスト、および、行が各列に割り当てないときの列ごとのコストも指定します。

[M,uR,uC] = matchpairs(Cost,costUnmatched) は、追加で、uR の不一致の行のインデックスおよび uC の不一致の行のインデックスを返します。

[___] = matchpairs(Cost,costUnmatched,goal) は、前の構文での任意の出力引数の組み合わせを使用して、最適化の目標を指定します。goal は 'min' または 'max' に設定して、合計コストを最小化または最大化する一致を出力することができます。

例

最小コストのフライトを割り当てる

合計の移動コストが最小となるよう、営業部員をフライトに割り当てます。

会社には、国内の主要都市に出張する必要のある 4 人の営業部員がいます。会社はフライトを予約しなければならず、できるだけ費用を少なくしようとします。これらの営業部員は国内のさまざまな場所を拠点としており、そのため、彼/彼女らが各都市へ飛行する費用は異なります。

この表に、各営業部員が各主要都市へ飛行するコストを示します。

$$\begin{array}{|ccccc|}\hline & \text{Dallas}& \text{Chicago}& \text{New}\text{York}\text{City}& \text{St.}\text{Louis}\\ \text{Fred}& \$600& \$670& \$960& \$560\\ \text{Beth}& \$900& \$280& \$970& \$540\\ \text{Sue}& \$310& \$350& \$950& \$820\\ \text{Greg}& \$325& \$290& \$600& \$540\\ \hline\end{array}$$

各都市は販売機会を表します。都市が失われると、会社は平均で 2,000 ドルの収益を失います。

各営業部員が各都市へ飛行するコストを表すコスト行列を作成します。

C = [600 670 960 560
     900 280 970 540
     310 350 950 820
     325 290 600 540];

matchpairs を使用して、営業部員を最小コストの都市に割り当てます。未割り当てのコストを 1000 と指定します。これは、未割り当てのコストは、行と列が不一致のままの場合 2 回カウントされるためです。

M = matchpairs(C,1000)

M = 4×2

     3     1
     2     2
     4     3
     1     4

matchpairs は、ある営業部員を各都市へ送る最も廉価な方法を計算します。

$$\begin{array}{|ccccc|}\hline & \text{Dallas}& \text{Chicago}& \text{New}\text{York}\text{City}& \text{St.}\text{Louis}\\ \text{Fred}& \$600& \$670& \$960& \text{\$}\text{560}\\ \text{Beth}& \$900& \text{\$}\text{280}& \$970& \$540\\ \text{Sue}& \text{\$}\text{310}& \$350& \$950& \$820\\ \text{Greg}& \$325& \$290& \text{\$}\text{600}& \$540\\ \hline\end{array}$$

行数と列数が等しくない場合

コスト行列で行より列が多い場合は、行を列に一致させます。

3 行 8 列の行列を作成します。3 行しかないため、matchpairs は 8 列に対して最大で 3 つの一致を出力できます。

rng default % for reproducibility
C = randi([10 100], 3, 8)

C = 3×8

    84    93    35    97    97    22    82    13
    92    67    59    24    54    48    97    87
    21    18    97    98    82    93    69    94

matchpairs を使用して、コスト行列の行と列を一致させます。最大の一致数を得るには、(コスト行列のエントリの大きさに対して) 未割り当てのコストを大きくします。3 つの出力を指定して、不一致の行と列のインデックスを返します。

[M,uR,uC] = matchpairs(C,1e4)

M = 3×2

     3     2
     2     4
     1     8

uR =

  0x1 empty double column vector

uC = 5×1

     1
     3
     5
     6
     7

C の 5 つの列はどの行とも一致しません。

利益を最大化するタクシーの割り当て

利益が最大化するようタクシーをルートに割り当てます。

タクシー会社には市全体から多くの乗車リクエストが寄せられます。会社は限られた数のタクシーを、最大の金額を生み出すような方法で送り出すことを考えます。

この表は、5 つの乗車リクエストそれぞれの推定タクシー料金を示しています。5 つの乗車リクエストのうち 3 つしか満たせません。

$$\begin{array}{|clllll|}\hline & \text{Ride}\text{1}& \text{Ride}\text{2}& \text{Ride}\text{3}& \text{Ride}\text{4}& \text{Ride}\text{5}\\ \text{Cab}\text{A}& \$5.70& \$6.30& \$3.10& \$4.80& \$3.50\\ \text{Cab}\text{B}& \$5.80& \$6.40& \$3.30& \$4.70& \$3.20\\ \text{Cab}\text{C}& \$5.70& \$6.30& \$3.20& \$4.90& \$3.40\\ \hline\end{array}$$

各タクシー乗車の利益を表す利益行列を作成します。

P = [5.7 6.3 3.1 4.8 3.5
     5.8 6.4 3.3 4.7 3.2
     5.7 6.3 3.2 4.9 3.4];

matchpairs を使用してタクシーを最大の利益につながる乗車に一致させます。不一致の行と列を返す 3 つの出力を指定し、利益を最大化する 'max' オプションを指定します。空車のタクシーや満たせなかった乗車リクエストからは利益は生じないため、未割り当てのコストをゼロとして指定します。

costUnmatched = 0;
[M,uR,uC] = matchpairs(P,costUnmatched,'max')

M = 3×2

     1     1
     2     2
     3     4

uR =

  0x1 empty double column vector

uC = 2×1

     3
     5

matchpairs が、満たすべき最大の利益を生む乗車を計算します。この解ではリクエスト 3 およびリクエスト 5 が満たされないままとなります。

$$\begin{array}{|clllll|}\hline & \text{Ride}\text{1}& \text{Ride}\text{2}& \text{Ride}\text{3}& \text{Ride}\text{4}& \text{Ride}\text{5}\\ \text{Cab}\text{A}& \$5.70& \$6.30& \$3.10& \$4.80& \$3.50\\ \text{Cab}\text{B}& \$5.80& \$6.40& \$3.30& \$4.70& \$3.20\\ \text{Cab}\text{C}& \$5.70& \$6.30& \$3.20& \$4.90& \$3.40\\ \hline\end{array}$$

計算された解について合計利益を計算します。costUnmatched がゼロのため、各一致の利益の合算のみが必要です。

TotalProfits = sum(P(sub2ind(size(P), M(:,1), M(:,2))))

TotalProfits = 17

時間経過に沿った点の位置の追跡

matchpairs を使用して、距離の変化の合計を最小化していくつかの点の移動を追跡します。

$\mathit{t}=0$ の時点での点のグリッドを緑でプロットします。$\mathit{t}=1$ の時点では、いくつかの点はランダムな方向に短い距離を移動します。

[x,y] = meshgrid(4:6:16);
x0 = x(:)';
y0 = y(:)';
plot(x0,y0,'g*')
hold on
rng default % for reproducibility
x1 = x0 + randn(size(x0));
y1 = y0 + randn(size(y0));
plot(x1,y1,'r*')

matchpairs を使用して、$\mathit{t}=0$ での点を $\mathit{t}=1$ での点と一致させます。これを行うには、まず、コスト行列を計算します。ここで、C(i,j) は点 i から点 j までのユークリッド距離です。

C = zeros(size(x).^2);
for k = 1:length(y1)
  C(k,:) = vecnorm([x1(k)-x0; y1(k)-y0],2,1)';
end
C

C = 9×9

    2.8211    3.2750    9.2462    6.1243    6.3461   10.7257   11.7922   11.9089   14.7169
    4.9987    2.2771    7.5752    6.2434    4.3794    8.4485   11.1792   10.2553   12.5447
   15.2037    9.3130    3.7833   17.1539   12.2408    8.7988   20.7211   16.8803   14.5783
    6.9004    8.6551   13.1987    1.1267    5.3446   11.3075    5.1888    7.3633   12.3901
    8.6703    6.3191    8.7571    5.9455    0.3249    6.0714    8.2173    5.6816    8.3089
   13.5530    8.1918    4.7464   12.7818    6.8409    1.4903   14.6652    9.9242    7.3426
   11.5682   13.1257   16.8150    5.5702    8.3359   13.4144    0.4796    6.2201   12.2127
   13.6699   12.3432   13.7784    8.6461    6.3438    8.8167    5.8858    0.3644    6.1337
   20.6072   17.2853   15.6495   16.5444   12.1590    9.6935   13.9562    8.3006    3.8761

次に、matchpairs を使用してコスト行列の行と列を一致させます。未割り当てのコストを 1 に指定します。未割り当てのコストがコスト行列のエントリと比較して低いため、matchpairs はいくつかの点を不一致のままにすると思われます。

M = matchpairs(C,1)

M = 5×2

     4     4
     5     5
     6     6
     7     7
     8     8

値 M(:,2) は元の点 $\left({\mathit{x}}_0,{\mathit{y}}_0\right)$ に対応し、値 M(:,1) は移動した点 $\left({\mathit{x}}_1,{\mathit{y}}_1\right)$ に対応します。

一致する点のペアをプロットします。元の点から 2*costUnmatched よりも長い距離を移動した点は不一致のままです。

xc = [x0(M(:,2)); x1(M(:,1))];
yc = [y0(M(:,2)); y1(M(:,1))];
plot(xc,yc,'-o')

入力引数

Cost — コスト行列

行列

コスト行列。各エントリ Cost(i,j) は、行 i を列 j に割り当てるコストを指定します。

データ型: single | double

costUnmatched — 一致しない場合のコスト

スカラー

一致しない場合のコスト。スカラーとして指定します。matchpairs は 2*costUnmatched の値を Cost のエントリと比較して、ある行またはある列が不一致のままであるほうが利益が大きいかどうかを判断します。このパラメーターを使用して、アルゴリズム内で一致が行われやすいかどうかを設定します。詳細については、線形の割り当て問題を参照してください。

例: M = matchpairs(C,10) は、C の行または列が一致しないことのコストを 10 に指定します。

データ型: single | double

goal — 最適化の目標

'min' (既定値) | 'max'

最適化の目標。'min' または 'max' のいずれかとして指定します。最適化の目標は、合計のコストが最小化されるか最大化されるかを指定します。

例: M = matchpairs(Cost,costUnmatched,'max') は、Cost の行および列が共に一致して合計のコストを最大化することを指定します。

出力引数

M — 一致するもの

行列

一致するもの。行列として返されます。M は p 行 2 列の行列であり、M(i,1) および M(i,2) はコスト行列で一致する行および列のインデックスです。M の行は 2 番目の列で昇順に並べ替えられます。

• 各行および各列は 1 回のみ一致できるため、各 M(i,1) の値および各 M(i,2) の値は一意です。

• M には p 個の一致が含まれており、p は一致の最大数 min(size(Cost)) 以下です。

• M の一致のコストは sum([Cost(M(1,1),M(1,2)), Cost(M(2,1),M(2,2)), ..., Cost(M(p,1),M(p,2))]) です。

uR — 未割り当ての行

列ベクトル

未割り当ての行。インデックスの列ベクトルとして返されます。uR のエントリは、Cost のどの行が未割り当てであるかを示します。uR および uC の各エントリは costUnassigned に従って解の合計のコストに貢献します。

uC — 未割り当ての列

列ベクトル

未割り当ての列。インデックスの列ベクトルとして返されます。uC のエントリは、Cost のどの列が未割り当てであるかを示します。uR および uC の各エントリは costUnassigned に従って解の合計のコストに貢献します。

詳細

線形の割り当て問題

"線形の割り当て問題" は、各行が列に割り当てられるようにし、割り当ての合計のコストが最小化 (または最大化) されるようにする方法です。各行を各列に割り当てるコストは "コスト行列" に取得されます。エントリ Cost(i,j) は、行 i を列 j に割り当てるコストです。

"未割り当てのコスト" は、コストを、一致しない任意の行または列に割り当てます。この手法により、すべての行または列を割り当てるわけではない最小コストの解が得られます。ある行と列が一致しない場合、これは合計のコストを 2*costUnmatched だけ増加させます。

解の合計コスト M は、すべての不一致のペアのコストに、一致するペアの合計コストを加算したものです。

$$TC={\displaystyle \sum _{i=1}^p\mathrm{Cost}}\left(M\left(i,1\right),M\left(i,2\right)\right)+\mathrm{costUnmatched}\cdot \left(m+n-2p\right)$$

コードでの合計コストは

CostAssigned = sum(Cost(sub2ind(size(Cost), M(:,1), M(:,2))));
CostUnassigned = costUnmatched*(sum(size(Cost))-2*size(M,1));
TotalCost = CostAssigned + CostUnassigned;

• Cost は m 行 n 列の行列です。

• M は p 行 2 列の行列であり、M(i,1) および M(i,2) は一致するペアの行と列です。

• (m+n-2*p) は "不一致" の行および列の合計数です。

参照

[1] Duff, I.S. and J. Koster. "On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix." SIAM J. Matrix Anal. & Appl. 22(4), 2001. pp 973–996.

拡張機能

C/C++ コード生成

MATLAB® Coder™ を使用して C および C++ コードを生成します。

使用上の注意事項および制限事項:

• コード生成では、この関数のスパース行列入力はサポートされません。

バージョン履歴

R2019a で導入

参考

equilibrate | sprank | dmperm