KM.txt

匹配问题的匈牙利方法
HW.Kuhn
引言
n个人对于n个工作，每个人对应每个工作都有一个分数。匹配问题是指，对人和工作进行匹配，使得获得的分数总和尽可能的大。两个匈牙利数学家的论文中潜在的思想也许可以用来产生一个该问题的新解法。
1.介绍
非正式地陈述：个人匹配问题所要求的是，人的集合对于工作集合的最优匹配，而可能的匹配的优劣程度是由总得分数来排序的。这个问题的变式，无论数学还是非数学的，都有很悠久的历史（见参考附录）。然而，当线性规划研究到这个问题时，我们发现，这个问题最新近的研究来自于“那帮人”的独立工作（自1949年起），他们认为这问题是运输问题的最“退化“情况。R认为它是TSP问题的近邻；。。。。略去一大堆“回顾“的话。
本算法的理论基础写于第二和第三部分。第二部分（派生于“匈牙利人“的证明）解决了只有两种分数0/1的匹配问题（即工人适用于该工作与否的判断）。第三部分（来源于blabla）表明一般匹配问题可以通过某种方法（？）规约到这种特殊情况。
算法在第四部分给出了一个独立完备的陈述。第五部分通过一个具体的例子说明了它的应用。
2.简单匹配问题
简单匹配问题通过如下简略模型描述：
四个人（用i=1，2，3，4表示）对应于四个工作（用j=1，2，3，4表示）。 约束如下：
1->1,1->2,1->3
2->3,2->4
3->4
4->4
此信息可以被一个限制矩阵有效表示
Q = 1 1 1 0
    0 0 1 1
    0 0 0 1
    0 0 0 1
行表示人，列表示工作；合格人被1标记，不合格为0.那么“简单匹配问题“所要求的是：
工作能够匹配给合格人的最大数目是多少（一个工作可以匹配给不超过一个人）？
在矩阵Q的形势下，这个问题可以抽象描述为：
在Q中最多能选多少个1（两个被选的“1”不能在同一行或者同一列）？
显然，我们能够通过将未匹配的人赋予任意满足约束的未匹配的工作来开始一个匹配。因为，我们可以把人1、2匹配给工作3，4，在矩阵中用星号表示这一过程：
    1 1 1* 0
    0 0 1 1*
    0 0 0 1
    0 0 0 1
因为不能再通过将未匹配人匹配给一个符合约束的未匹配工作来改进一个匹配，那么这个匹配就被成为“完备“的。如果一个匹配是完备的，那么自然会去尝试“转移“来改进匹配：
将人1从工作3转移到工作1
     2      4         3（对应）
结果导致了如下的不完备匹配：
    1* 1 1 0
    0 0 1* 1
    0 0 0 1
    0 0 0 1
这里我们可以将人3或者4匹配给工作4来完备这个匹配。任一结果,
    1 1 1* 0
    0 0 1 1*
    0 0 0 1*
    0 0 0 1
都是最优的，因为剩下的合法对要么包含人1要么包含工作3要么包含工作4，因为四个匹配就会导致这三者之一被包含两次。所以，纵然这个最优匹配中存在一个可能的转移（把人1从工作1移到工作2），它也只能导致另一个“并非更优的“完备匹配。下面的讨论确定了一般的情况，即，通过一系列转移的演替以增加额外匹配数直到不能再增加为止，总能够构建出一个最优匹配。
假定有n个人（i = 1,2...n）对应于n个工作（j = 1,2...n）并且约束矩阵Q={qij}已经给出，其中qij=1表示人i可以匹配工作j，相反则qij=0.如果一个确定的匹配（不一定是最优的）已经给出，那么改进它的最简单方法就是将任一未匹配的人匹配给任一符合约束的工作；如果这是可行的，那么所给匹配即为“不完备匹配“，否则就是“完备“的。如果一个匹配已经完备，那么通过“转移“的方法来改进一个它是一种合理的想法。一个转移改变了一个匹配数为r的匹配，其中人i1，...，ir对应于工作j1,...,jr。它将i1转移给未匹配的工作j0，以及ik到工作jk-1(对于每一个k=2,...,r）。假定所有的新匹配（ik到jk-1）都符合约束。当然，如果所有匹配均保持不变也可以叫做一种转移。一种改变了某些匹配的转移可以表示为：
   i1 i2 ... ir-1 ir
  /  /      /    /
j0 j1 j2...jr-2 jr-1 jr
我们将所有包含于这个转移中的匹配人成为“必要人“，所有匹配于一个”非必要人“的工作叫做一个“必要工作“。因此，
引理1，对于一个给定的匹配，如果一个人被匹配给了一个工作，那么要么这个人要么这个工作是必要的，两者不能同时成为必要的。
推论1，对于所有的匹配，“匹配人（已匹配给工作的人）“的总数等于“必要人“和“必要工作“的总数。
引理2，对于一个给定的匹配，如果一个人已经匹配给了一个工作，但又符合另一个未匹配工作的约束条件，那么这个人就是“必要”的。
证明：这个人到这个未匹配工作的转移使得这个人成为“必要“的。
引理3：
对于一个给定的匹配，如果每个转移都使某个工作变成“已匹配“的，那么这个工作是“必要“的。
证明：假定工作j是非必要的。假定某个人ik匹配于它并且ik包含于一个转移（按顺序转移i1,i2,...,ik）。表示为：
   i1 i2 ... ik-1 ik
  /  /      /    /
j0 j1 j2...jk-2 jk-1 j
其中j未匹配。这证明了这个引理。（这是什么证明方法- -？我翻译错了还是？！？？！）
以上的各个引理联合导出了如下关键理论：
定理1，对于一个给定的匹配，如果每个转移都推出一个完备匹配，那么对于每一个符合某一工作约束的人，要么这个人要么这个工作是“必要“的，或者两者都是。
证明，令人i对应于工作j（qij=1）。如果i匹配于j那么由引理1可以导出这两者之一为必要的。如果i被匹配给了另一个工作而j变成未匹配的，那么由引理2就会导出人i是必要的。如果i是未匹配的那么每个转移都会使j变成匹配的（否则这个匹配就是非完备的），因为由于引理3，可以导出j是必要的。定理1得证。。（这奇怪的证明。。）
从任意一个匹配出发（即一个人匹配于一个符合约束的工作），或者每一个转移都会推出一个完备匹配或者至少有额外的一个人能在某次转移后被匹配。因为最多有n个人能被匹配，这就证明了：
定理2，存在一个每次转移后仍完备的匹配。
我们现在从另一个角度来看待这个问题。考虑一个可能的预算，为一个匹配（的两方）赋予价值。这样的一个“预算“会给每一个人和每一个工作分配1单位或者0单位的权值。如果对于每一个符合某一工作约束的人，要么这个人要么这个工作要么两者都被赋予了1单位的权值，那么这个预算被称为“充分“的。
定理3，任一充分的预算的总分配权值都不小于可以被分配给符合约束人的工作的最大数目。
THEOREM 3.The total allotment of any adequate budget is not less than the largest number of jobs that can be assigned to qualified individuals.
（抽B阿抽B）
证明。如果统计了最优匹配中被分配给“已匹配的工作“的那一部分预算，这个数字看起来似乎不会小于“已匹配的工作“的数目，因为这些工作都被匹配给了符合约束的人。因此总预算不会少于这个数字，因而定理得证。
考虑任何可能的转移后形成的任一完备匹配（根据定理2，存在这样的匹配）并且考虑它的预算，这个预算给每个必要人或必要工作分配了1单位的权值而给非必要的分配了0.定理1导出这个预算是充分的。