针对或疏或密的线性分派问题的最短增广路算法

（译者注：为了符合国内的称呼习惯，下文中“分派”将会被翻译为“匹配”，而“线性分派”将被翻译为“最小权匹配”。且本翻译仅针对“算法是什么”、“算法的正确性”、“算法复杂度正确性”进行翻译，故会删减与这些无关的部分。）

1、简介

　　考虑以$c[i,j]$（$i,j=1,...,n$）为权值的最小权匹配问题，其可以被形式化叙述为如下线性规划问题：

$$最小化\sum_{ij}c[i,j]\cdot x[i,j]\\满足\begin{cases}\sum_{j}x[i,j]=1(i=1,...,n),\\\sum_{i}x[i,j]=1(j=1,...,n),\\x[i,j]\geq0(i,j=1,...,n).\end{cases}$$ 该问题的对偶问题是： $$最大化\sum_{i}u[i]+\sum_{j}v[j]\\满足c[i,j]-u[i]-v[j]\geq0(i,j=1,...,n).$$ 其中$u[i]$和$v[j]$被称为对偶变量，而$c[i,j]-u[i]-v[j]$被称为残留权值。于是，对偶问题就是找到一个对权值矩阵的减小方法，其减小量的和最大且不会把残留权值减小到负。
　　接下来，下标$i$和$j$将分别指代行标和列标；$x[i]$是指和第$i$行相匹配的列标，$y[j]$是指和第$j$列相匹配的行标，用$x[i]=0$表示第$i$行尚未被匹配，用$y[j]=0$表示第$j$列尚未被匹配；对偶变量$u[i]$对应第$i$行，对偶变量$v[j]$对应第$j$列。将把残留权值记为：$cred[i,j]:=c[i,j]-u[i]-v[j]$，并且有时会把对偶变量称为“价格”。
　　

3、基于最短增广路的算法

　　接下来的几节将分别针对基于最短增广路的算法的各个步骤进行说明。几个步骤分别为：
第一步：初始化；
第二步：如果所有行都被匹配了，就结束；
第三步：增广
　　　　建立残量网络，并找到一条残留权值最小的从未匹配行$i$出发到未匹配列$j$的交错路，并用这条路增广答案。
第四步：调整对偶问题的结果来维持互补松弛性。
　　　　回到第二步。
　　　　
　　下一节说明初始化过程。第五节说明如何找用于增广匹配的最短路。第六节说明在找到最短增广路之后如何简单地修改行和列的价格。
　　

4、初始化过程

（译者注：该节其实原则上没必要翻译，因为这纯粹就只是常数优化，甚至是玄学的。直接就用第一段所说的标准初始化方法就可以，甚至随便怎么初始化，后边几节所说的阶段的时间复杂度还是$O(n^3)$的，只要保证初始化的时候$u[i]+v[j]$不要超过$c[i,j]$，正确性不会有问题。）
　　最小权匹配问题的一种标准初始化方法是对列和行减小。对每一列$j$，找到最小的$c[i,j]$（$i=1,...,n$），记此$i$为$i^*$，$v[j]$赋值为$c[i^*,j]$，这时，如果$i^*$还没被匹配，就将$j$和$i^*$匹配。接着，对每一未匹配行$i$，找到最小的$c[i,j]-v[j]$（$j=1,...,n$），记此$j$为$j^*$，如果$j^*$还没被匹配，将$j^*$和$i$匹配。
　　而在我们的算法中，初始化过程将着重关注使得权值矩阵高程度地被初始减小。这包括三个过程，叙述如下：
——对列减小，
——将减小从未匹配行转移给已匹配行，
——将未匹配行的减小增广。
　　第一个过程被称为标准列减小。一个执行细节是，逆序考虑列。于是乎，编号较小的列更可能保持未匹配的状态。这样做的话，如果某行的最小残留权值对应于未匹配的列，该列将自动地被选为第一个满足最小性的列。
　　第二个过程被称为减小的转移。其目的是更加深入地减小已匹配的行，而且其不会直接影响减小量的和。在这之后，如果有未匹配的行被减小的话，可能能得到一个更高的减小量的和。
　　考虑有一行$i$被匹配到某列$k$。依靠充分地降低列$k$的价格，行$i$可以减小当前第二小的残留权值。此针对已匹配行的追加减小会使得某些未匹配行的残留权值上升，以至于这些行会在之后被更深入地减小。此过程的影响是两面的，已匹配行的价格会变贵，而未匹配行的价格会变便宜。一般来说，经过这一过程，增广过程中的最短路能更快地到达未匹配点。

void reduction_transfer {
    for (int i = 1; i <= n; ++i) {
        if（!x[i]) {
            continue;
        }
        int j1 = x[i];
        int mu = inf;
        for (int j = 1; j <= n; ++j) {
            if (j == j1) {
                continue;
            }
            mu = std::min(mu, c[i][j] - v[j]);
        }
        v[j1] = v[j1] - (mu - u[i]);
        u[i] = mu;
    }
}

　　上方代码给出了转移减小的说明。注意，第一过程（标准列减小）结束的时候，所有$u[i]$都是零。更进一步，也可以选择在列减小过程中一直紧跟着，这样针对行的转移减小就没有用了。
　　第三个过程被称为行减小的增广。此过程的一个任务是找到从未匹配行出发的增广路，于是可以给这些行转移一些减小量。在这一过程中，已匹配的列还是被匹配，但是行可能改变匹配性。

void augmenting_row_reduction {
    for (int i = 1; i <= n; ++i) {
        if (x[i]) {
            continue;
        }
        while (true) {
            int u1 = inf;
            int j1;
            for (int j = 1; j <= n; ++j) {
                if (c[i][j] - v[j] < u1) {
                    u1 = c[i][j] - v[j];
                    j1 = j;
                }
            }
            int u2 = inf;
            int j2;
            for (int j = 1; j <= n; ++j) {
                if (j == j1) {
                    continue;
                }
                if (c[i][j] - v[j] < u2) {
                    u2 = c[i][j] - v[j];
                    j2 = j;
                }
            }
            u[i] = u2;
            if (u1 < u2) {
                v[j1] = v[j1] - (u2 - u1);
            } else if (y[j1]) {
                j1 = j2;
            }
            int k = y[j1];
            if (k) {
                x[k] = 0;
                x[i] = j1;
                y[j1] = i;
                i = k;
            }
            if (u1 == u2 || !k) {
                break;
            }
        }
    }
}

　　上方代码给出了增广行减小的说明。在每一次for循环中，都有一条交错路从某未匹配行出发，该行记为$i$。考虑使得对应于$i$的最小残留权值的列$j$。如果$j$是未匹配的，那么这条交错路就带来了一次增广。如果不是，该交错路依靠将$j$和$i$配对来延长，同时会将原先和$j$配对的行$k$标为未配对的。显然，现在行$i$可以减小其最小的残留权值，但是如果第二小的残留权值大一些，那么可以将列$j$中的残留权值提升，来使得该减小可能发生。如果发生这种情况了，我们就考虑行$k$，对于该行，最小残留权值可能发生在$j$之外的列。如果确实是这样，那么交错路会像过去那样延长。如果不是，并且最小残留权值依旧是唯一的，那么该路甚至可能反着走，并且沿着已经访问过的行和列延长。该过程会持续到无增广路，或者没有减小量被转移为止。
　　前边两个过程都具有时间复杂度$O(n^2)$。可以看出，减小的增广过程最多$O(n^2R)$步，而$R$是权值系数的范围。而每一步有$O(n)$个操作，总时间复杂度为$O(n^3R)$。而还有如下的增广方式。我们找$O(n)$条交错路。每条交错路就只执行$O(n)$次延长。于是像这样简单地限制每次延长只走$n$步，就能让时间复杂度为$O(n^3)$。

5、增广过程

　　增广始于找一条交错路。此交错路始于未匹配行标，终于列标。如果终点的列标未匹配，那么意味着可以沿着此交错路增广一次，使得匹配数加一。

void shpath1(int kk)
{
    for (int i = 1; i <= n; ++i) {
        toscan[i] = i != k;
    }
    int toscansz = n - 1;
    for (int j = 1; j <= n; ++j) {
        d[j] = inf;
    }
    int i = kk;
    d[kk] = 0;
    int mu = 0;
    while (true) {
        for (int j = 1; j <= n; ++j) {
            if (!a[i][j] || !toscan[j]) {
                continue;
            }
            if (mu + c[i][j] < d[j]) {
                d[j] = mu + c[i][j];
                pred[j] = i;
            }
        }
        mu = inf;
        for (int j = 1; j <= n; ++j) {
            if (!toscan[j]) {
                continue;
            }
            if (d[j] < mu) {
                mu = d[j];
                i = j;
            }
        }
        toscan[i] = false;
        --toscansz;
        if (!toscansz) {
            break;
        }
    }
}
void shpath_augment(kk)
{
    for (int j = 1; j <= n; ++j) {
        d[j] = inf;
        toscan[j] = true;
    }
    int i = kk;
    d[kk] = 0;
    int mu = 0;
    int muj;
    while (true) {
        for (int j = 1; j <= n; ++j) {
            if (!a[i][j] || !toscan[j]) {
                continue;
            }
            if (mu + cred[i][j] < d[j]) {
                d[j] = mu + cred[i][j];
                pred[j] = i;
            }
        }
        mu = inf;
        for (int j = 1; j <= n; ++j) {
            if (!toscan[j]) {
                continue;
            }
            if (d[j] < mu) {
                mu = d[j];
                muj = j;
            }
        }
        i = y[muj];
        toscan[muj] = false;
        if (!y[muj]) {
            break;
        }
    }
    //此处沿着从列muj到行kk的交错路增广。
}

上方的代码SHPATH1是普通的用于求出从$kk$出发的单源最短路树的狄克斯特拉算法，$A[i][j]$表示边$\left<i,j\right>$的存在性。而SHPATH-AUGMENT是针对最小权匹配问题调整过的版本，用于求从行$kk$出发的最短增广路。