二分图匹配 匈牙利算法和KM算法简介.

Presentation on theme: "二分图匹配 匈牙利算法和KM算法简介."— Presentation transcript:

1 二分图匹配 匈牙利算法和KM算法简介

2 二分图的概念 二分图又称作二部图，是图论中的一种特殊模型。
设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。 1 2 3 4 5

3 最大匹配 给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem) 如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

4 匈牙利算法 求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。 增广路的定义(也称增广轨或交错轨)： 若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。

5 匈牙利算法 由增广路的定义可以推出下述三个结论： 1－P的路径长度必定为奇数，第一条边和最后一条边都不属于M。
3－M为G的最大匹配当且仅当不存在相对于M的增广路径。

6 匈牙利算法 用增广路求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出) 算法轮廓： (1)置M为空
(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M (3)重复(2)操作直到找不出增广路径为止

7 匈牙利算法 程序清单： Function find(k:integer):integer; var st,sf,i,j,t:integer;
queue,father:array[1..100] of integer; begin queue[1] := k; st := 1; sf := 1; fillchar(father,sizeof(father),0); repeat

8 匈牙利算法 for i:=1 to n do if (father[i]=0)and(a[queue[st],i]=1) then
begin if match2[i]<>0 then inc(sf); queue[sf] := match2[i]; father[i] := queue[st]; end else

9 匈牙利算法 begin j := queue[st]; while true do t := match1[j];
match1[j] := i; match2[i] := j; if t = 0 then break; i := t; j := father[t];

10 匈牙利算法 end; find := 1; exit; inc(st); until st>sf; find := 0;

11 匈牙利算法 在主程序中调用下面的程序即可得出最大匹配数。 Bmatch := 0;
For I:=1 to n do Bmatch := Bmatch + find(i); Writeln(Bmatch); 一个关于二分图的性质： 最大匹配数＋最大独立集＝X＋Y

12 最佳匹配 如果边上带权的话，找出权和最大的匹配叫做求最佳匹配。
实际模型：某公司有职员x1,x2,…,xn,他们去做工作y1,y2,…,yn,每个职员做各项工作的效益未必一致，需要制定一个分工方案，使得人尽其才，让公司获得的总效益最大。 数学模型：G是加权完全二分图，求总权值最大的完备匹配。

13 KM算法 穷举的效率－n！，我们需要更加优秀的算法。 定理：
设M是一个带权完全二分图G的一个完备匹配，给每个顶点一个可行顶标(第i个x顶点的可行标用lx[i]表示，第j个y顶点的可行标用ly[j]表示)，如果对所有的边(i,j) in G,都有lx[i]+ly[j]>=w[i,j]成立(w[i,j]表示边的权)，且对所有的边(i,j) in M,都有lx[i]+ly[j]=w[i,j]成立，则M是图G的一个最佳匹配。证明很容易。

14 KM算法 对于任意的G和M，可行顶标都是存在的： l(x) = maxw(x,y) l(y) = 0
欲求完全二分图的最佳匹配，只要用匈牙利算法求其相等子图的完备匹配；问题是当标号之后的Gl无完备匹配时怎么办？1957年（居然比匈牙利算法早？？？），Kuhn和Munkras给出了一个解决该问题的有效算法，用逐次修改可行顶标l(v)的办法使对应的相等子图之最大匹配逐次增广，最后出现完备匹配。

15 KM算法 修改方法如下： 先将一个未被匹配的顶点u(u in {x})做一次增广路，记下哪些结点被访问那些结点没有被访问。求出d=min{lx[i]+ly[j]-w[i,j]}其中i结点被访问，j结点没有被访问。然后调整lx和ly：对于访问过的x顶点，将它的可行标减去d，对于所有访问过的y顶点，将它的可行标增加d。修改后的顶标仍是可行顶标，原来的匹配M仍然存在，相等子图中至少出现了一条不属于M的边，所以造成M的逐渐增广。

16 KM算法 上述算法的证明也很容易 Kuhn－Munkras算法流程： (1)初始化可行顶标的值 (2)用匈牙利算法寻找完备匹配
(3)若未找到完备匹配则修改可行顶标的值 (4)重复(2)(3)直到找到相等子图的完备匹配为止

17 参考文献 王树禾《离散数学引论》 吴文虎 王建德《图论算法与程序设计》 刘汝佳 黄亮《算法艺术与信息学竞赛》
2002年冬令营论文－孙方成《偶图的算法及应用》 2004年冬令营论文－黄源河《浅谈图论模型的建立与应用》

18 例题1 Place the Robots（ZOJ1654）
问题描述 有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。 Wall Grass Empty

19 例题1 Place the Robots（ZOJ）
模型一 5 4 6 7 8 3 2 1 在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型： 以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图： 1 2 3 4 6 5 7 8 于是，问题转化为求图的最大独立集问题。

20 例题1 Place the Robots（ZOJ）
模型一 5 4 6 7 8 3 2 1 在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型： 以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图： 1 2 3 4 6 5 7 8 这是NP问题！

21 例题1 Place the Robots（ZOJ）
模型二 1 我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。我们把这些块编上号。 2 3 4 5 1 2 3 4 同样，把竖直方向的块也编上号。

22 例题1 Place the Robots（ZOJ）
模型二 1 把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。 2 3 4 于是，问题转化成这样的一个二部图： 5 1 2 3 4 1 2 3 4 5

23 例题1 Place the Robots（ZOJ）
模型二 1 1 2 3 4 5 2 3 4 5 由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配问题。 1 2 3 4

24 例题1 Place the Robots（ZOJ）
小结 比较前面的两个模型：模型一过于简单，没有给问题的求解带来任何便利；模型二则充分抓住了问题的内在联系，巧妙地建立了二部图模型。为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：模型一以空地为点，模型二以空地为边；其二是由于对原型中要素的选取有差异：模型一对要素的选取不充分，模型二则保留了原型中“棋盘”这个重要的性质。由此可见，对要素的选取，是图论建模中至关重要的一步。

25 例题2 救护伤员（TOJ1148） 无情的海啸夺取了无数人的生命.很多的医疗队被派往灾区拯救伤员.就在此时,医疗队突然发现自己带的药品已经不够用了,只剩下了N种。(1 < n <= 20)，随着病人病情的发展，每种药在每天能获得的效果是不一样的。同时，每天病人只能服用一种药。也就是说，这些药还够支持N天。现在，给出你每种药在每天使用的效果，请你判断当每种药都用完后所有药达到的效果之和最大可以是多少。

26 例题3 打猎 猎人要在n*n的格子里打鸟，他可以在某一行中打一枪，这样此行中的所有鸟都被打掉，也可以在某一列中打，这样此列中的所有鸟都打掉。问至少打几枪，才能打光所有的鸟？ 建图：二分图的X部为每一行，Y部为每一列，如果(i,j)有一只鸟，那么连接X部的i与Y部的j。 该二分图的最大匹配数则是最少要打的枪数。

27 例题4 最小路径覆盖 一个不含圈的有向图G中，G的一个路径覆盖是一个其结点不相交的路径集合P，图中的每一个结点仅包含于P中的某一条路径。路径可以从任意结点开始和结束，且长度也为任意值，包括0。请你求任意一个不含圈的有向图G的最小路径覆盖数。 理清一个关系：最小路径覆盖数＝G的定点数－最小路径覆盖中的边数

28 例题4 最小路径覆盖 试想我们应该使得最小路径覆盖中的边数尽量多，但是又不能让两条边在同一个顶点相交。
拆点：将每一个顶点i拆成两个顶点Xi和Yi。然后根据原图中边的信息，从X部往Y部引边。所有边的方向都是由X部到Y部。

29 例题4 最小路径覆盖 因此，所转化出的二分图的最大匹配数则是原图G中最小路径覆盖上的边数。因此由最小路径覆盖数＝原图G的顶点数－二分图的最大匹配数便可以得解。