匹配问题2014.ppt

匹配理论（Matching Theory） 图论--二元关系 问题一：怎么把二元关系转化成一个图 问题二：怎么把图输入计算机（无向图、有向图、赋权图） 问题三：什么叫做匹配，匹配怎么在计算机中表示？ 问题一：怎么把二元关系转化成一个图 有一个谍报小组,共有5名成员,他们的名字分别为:ace, bc, dab, fe，现在问: 能否从每个人的名字中各取出一个字母来.作为彼此联络的代号? 要给n个工作人员安排m项工作，已知每个工作人员能胜任这m项工作中的一项或几项，现在问：如何配对，才能尽可能多的工作人员得到满意的工作。 第二次世界大战中，欧洲很多飞行员从沦陷国应募加入英国皇家空军， 由皇家空军送出的每一架飞机上都要配备有航行技能与语言上能相互 搭配的两名飞行员，空军希望能同时送出尽可能多的飞机，如何解决？ 有一个交易会，有n家企业家参与，其中每一家企业都希望与其他企业商谈，假设每次商谈持续一天，并且每次商谈都恰有两家参与，问这次交易会至少多少天才能结束？ 某家公司生产若7种化学制品，分别标号为1--7，其中某些制品是互不相容的，如果存放在一起，则可能发生化学反应，引发危险。其中不能存放在一起的是：（1，2）（1，4）（2，3）（2，5）（2，7）（3，4）（3，5）（3，6）（4，5）（4，7）（5，6）（6，7）。因此公司必须把仓库分成相互隔离的若干区，以便把不相容的制品分开存放，其中，问：至少要划分多少小区，怎么才能保证安全？ 问题二：怎么把图输入计算机（无向图、有向图、赋权图） 常用的图矩阵： 邻接矩阵（点与点的关系）、关联矩阵（点与边的关系） 关联矩阵： 邻接矩阵 问题三：什么叫做匹配，匹配怎么在计算机中表示？ 定义：对于一个图G=（V,E），若有边子集 , 使M中任意两边 均无公共端点，则称边集M为图G的一个匹配。 最大匹配：边数最多的匹配（不惟一）称为最大匹配。 完美匹配：若匹配包含图G的所有点，则称该匹配为完美匹配 写出匹配的邻接矩阵、关联矩阵表示 二分图的最大匹配求法 四、算法：如何寻找最大匹配 如何寻找更大的匹配？（增广路、饱和点） 饱和点：匹配M上的顶点称被M饱和的点，不在M上的顶点称为M的非饱和点。 M-增广路：起点和终点都为M的非饱和点的路 初始条件：寻找任一个匹配M 方法：在图G中找到一个M-增广路，得到一个新的匹配M， |M||M|，不断进行下去，直到找不到增广路，则此时的匹配为最大 匹配 1965年, Edmonds提出匈牙利算法,解决了人员分配问题. 我们将给出该算法的思想及其Matlab实现. 人员工作问题 要给n个工作人员安排m项工作，已知每个工作人员能胜任这m项工作中的一项或几项，现在问：如何配对，才能尽可能多的工作人员得到满意的工作。 第二次世界大战中，欧洲很多飞行员从沦陷国应募加入英国皇家空军， 由皇家空军送出的每一架飞机上都要配备有航行技能与语言上能相互 搭配的两名飞行员，空军希望能同时送出尽可能多的飞机，如何解决？ Kuhn-Munkres算法 问题起源: 最优分派问题是在人员分派问题中把工人对各种工作的效率考虑进去,以便工人的总效率达到最大,此问题称为最优分派问题.