# 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'` 以生成总成本最小化或最大化的匹配。`

## 示例

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

`M = matchpairs(C,1000)`
```M = 4×2 3 1 2 2 4 3 1 4 ```

`matchpairs` 计算为每个城市分配一位销售人员的最经济的方式。

```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 ```

`[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` 中有五列不匹配任何行。

```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];```

```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 个乘车请求未得到满足。

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

```[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*')```

```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 ```

`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)$

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

## 输出参数

• 每行和每列只能匹配一次，因此每个 `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))])`

## 详细信息

### 线性分配问题

`M` 的总成本是所有已匹配对组的成本加上所有未匹配对组的成本之和：

`$TC=\sum _{i=1}^{p}\mathrm{Cost}\left(M\left(i,1\right),M\left(i,2\right)\right)+\mathrm{costUnmatched}\text{\hspace{0.17em}}\cdot \text{\hspace{0.17em}}\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.