在基于二分图匹配的课题最优选取方案

在基于二分图匹配的课题最优选取方案
孙健温州大学物理与工程学院 07 计本 2
摘要 本文介绍一种利用最大权二分图匹配来解决学生选择课题的方法，这种方法既顾及到
学生课题选取的公平性，有考虑到学生的个人兴趣。引入 KM 算法是完成本方案的关键。基
于此算法，我们可以使每个同学跟他们自己感兴度比较大的课题配对，而且总体满意程度
的也会最大，也就是既考虑到了个人，也考虑到了整体。相对于按时间先后随机配对来说，
这种方法显得较为科学。
 
关键词 二分图 选题   最大权匹配   KM 算法
1 引言在我们的大学学习生活中，会有很多的学生课题可以让我们去选择和研究，有很多同学对课题研究很感兴趣。但是一个同学可能对很多个课
题感兴趣，但是一个课题只能由一个一个同学负责，一个同学也只能负责一个课题。由于课题是同学们自己选的，这样，先选的同学就会得到这个课题，而后来者就无法再选这个课题了，这样多少会产生一些不公平现象。如果我们选用计算机作为辅助的工具来对每个课题做一个匹配，这
样就会比较合适。但是单纯的匹配未必会令人满意，因为一旦我的选的课题被刷掉，我就没有机会去选择其他课题了，于是我们找到的解决办法是每个人可以选多个课题，然后经过随机筛选，我们会得到一个课题。这里，我们可以对选取课题选取方式做一个优化，使最后的课题选择更加
的符合大家的要求。
法，我们可以使同学们整体的满意度最大。
 
2 核心算法接下来我们所要讨论的是 Kuhn-Munkres 算
法，该算法是在 Hungarian 算法的基础上产生的。由于算法涉及到较多的图论概念，所以有必要先阐述一些概念。
 
2.1 基本概念二分图：如果图 G=(V,E)是一个无向图，如
果顶点 V 可分割为两个互不相交的子集(X,Y)，并且图中的每条边（i，j）所关联的两个顶点 i和 j 分别属于这两个不同的顶点集(i∈X,j∈Y)，则称图 G 为一个二分图。比如：x1 y1
我们每个同学可以根据自己的兴趣，给选择课题一个满意度，比如共五个等级，5 代表最喜欢，4 次之，依次类推。这样我们可以把同学与课题抽象成一个带权的二分图匹配，权就是同学对这个课题的满意度，通过最大权二分图匹配算
x2
 
x3
y2
 
y3
 
 
匹配：二分图 G=(V,E)中边集 E 的子集，其中的在 M 中的任意两边都没有公共顶点。交错路径：增广路,若 M 是二分图 G=(V,E)的
一个匹配,设从图 G 中的一个顶点到另一个顶点存在一条道路,这条道路是由属于 M 的边和不属于 M 的边交替出现组成的,则称这条道路为交错路或称增广路。如果交错路的头尾两个顶点不属于 M 则称这条增广路为可增广道路。
x1 y1
图的最大权匹配。
 
2.2 基本思想设二分图 G=(V,E),它的两部分点集分别为
X，Y。我们寻找最大权匹配其实的做法是不断寻找交错路径。初始时 lx[i]=max{w[i][j]|j 是右边的点}，ly[i]=0。然后就像匈牙利算法一样找一条类似的交错路径，不同之处是它的交错路径需满足
lx[u]+ly[v]==map[u][v]，而且，X 顶点集和 Y顶点集都要标记有没有被扫描过。遍历 A 中的每个点，如果以该点为起点的交
x2
 
 
x3
y2
 
 
y3错路径存在，那么，就说明该匹配加入到最大匹配 M 中，如果交错路径找不到，可以用某种方法对顶标进行调整。调整的方法是：根据最后一次
不成功的寻找交错路的 DFS，取所有 i 被访问到而 j 没被访问到的边(i,j)的 lx[i]+ly[j]-w[i]
最优匹配：有二分图 G=(X,Y,E)其中|X|=|Y|=匹配数，E 中每条边(Xi,Yj)有权 Wij>=0,若能找到一个匹配 M(|M|=匹配数),满足所有匹配的边权和最大(或最小),则称 M 为 G 的一个最优匹配(
或称最大权匹配’)。完备匹配：对于二分图 G=(X,Y,E)，M 是 G 中的一个匹配，如果 G 中每个顶点都是 M 中的一个匹配顶点，则称 M 为 G 的完备匹配(或称完全匹配%完美匹配)。
 
接下来是二分图特有的概念：可行顶标：可行顶标是指关于二分图两边的每个点的一个值 lx[i]或 ly[j]，保证对于每条边 w[i][j]都有 lx[i]+ly[j]-w[i][j]>=0。定理：若由二分图中所有满足 A[i]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等
子图）有完备匹配，那么这个完备匹配就是二分[j]的最小值 d。将交错树中的所有左端点的顶标减小 d，右端点的顶标增加 d。经过这样的调整以后：原本在相等子图里面的边，两边的顶标都变了，不等式的等号仍然成立，仍然在相等子图
里面；原本不在相等子图里面的边，它的左端点的顶标减小了，右端点的顶标没有变，而且由于d 的定义，不等式仍然成立，所以他就可能进入了相等子图里，即可能出现新的交错路径。这样等我们全部遍历完 X 中的点后，留在内存中的数组就记录了所有的匹配信息，以及可行
标顶的值。这时我们遍历 ly[j]即可输出最大匹配权。
 
下面是我的伪代码：FindPathFrom uu is visited
for v in adj[u]
 
if v is not visited and lx[u]+lv[v]=w{u,v}v is visitedif v is matched and
FindPathFrom v is truev is matched ureturn truereturn false
 
Kuhn_Munkras:for u in Xlx[u]=max{w{u,v} | v is in Y}for v in Yly[v]=0
 
for u in Xwhile truefor each vertex uif FindPathFrom u is truebreakelse
find the d=min{ lx[i]+l[j]-w{i,j} } that i is in X and j is in Yfor each i is visitedlx[i] = lx[i]-dfor each j is visitedly[j] = ly[j]+d
在导出子图的边对应的 lx[i]+ly[j]-w[i][j]的最小值，在 find 过程中，若某条边不在导出子图中就用它对相应的 slack 值进行更新。然后求d 只要用 O(N)，而不是原来的 O(N2)的时间找到
slack 中的最小值就可以了。
 
3 应用：KM 算法能够很好地应用在课题选择系统中，解决题目与学生最优匹配的问题。假设我们有 n
个同学选了课题 x1,x2,...,xn,并且有 m 个课题y1,y2,...,ym,第 i 个同学对第 j 门课题的感兴趣程度可以用 w[i][j]这个二维矩阵来表示。匹配可以用 match[m]记录，表示第 j 课题的匹配学生是 match[j]。这样，等主要程序运行完毕后，存储在 match 数组里的数据就是匹配的内容。输出
所有 match[i]的内容就表示第 i 个课题被第match[i]个同学选取。这里需要考虑一个问题，就是 m 与 n 值，如果 m=n 那么肯定可以得到一个匹配，但是 mn 则需要考虑一些问题，需要建一些虚顶点，用权 0 来标记顶点与虚顶点之间的权。所以可以
用 0 初始化所有 w 数组。可以据一个简单的例子：假设我们有三个同学 x1,x2,x3，三个课题 y1,y2,y3。每个同学最多可以选两个课题，各个同学的对兴趣程度在图中已标出。这样它的最大权匹配为 x1～y2，x2～y3，x3～y1
x1 y1
该算法的时间复杂度是 O(n4),尽管这样，它在实际应用中还是能够比较快的完成任务。如果对时间要求比较高，还句话说数据量非常庞大，本算法还可以优化成 O(n3)，这样，时间量会减少比较大。
具体做法是用 slack[j]表示右边的点 j 的所有不
 
4 结束语这篇文章只是在单纯计算机编程的角度讨论了这种课题方案，对于简单应用还是能够游刃有余，但是这个算法对于大量数据来说，内存占用
量还是比较大，话说回来，毕竟现在的计算机的内存已经是海量存储了，对于这些内存的消耗还是可以接受。从时间上考虑，这个算法的如果能再优化一下，那么时间上可能会比较容易接受。
 
参 考文献
[1] Richard A.Brualdi 组合数学  第四版 机械工业出版社[2] 杨胜超 张瑞军 基于二分图最优匹配算法的
毕业文档选题系统 计算机系统应用 2008 年第 7期

相关论文