匹配算法(图论)
匹配算法是算法用于解决图匹配中存在的问题图论.当必须绘制一组不共享任何顶点的边时,就会出现匹配问题。
图匹配问题在日常活动中非常常见。从在线配对和约会网站,到医疗住院安置项目,匹配算法被用于调度、规划、顶点配对和网络流.更具体地说,匹配策略在流网络算法中非常有用,例如Ford-Fulkerson算法和Edmonds-Karp算法.
图匹配问题通常包括使用不共享公共顶点的边在图中进行连接,例如根据学生各自的资格对班级中的学生进行配对;或者它可能包括创建一个双方的匹配,其中两个顶点子集是区分的,并且一个子组中的每个顶点必须与另一个子组中的顶点匹配。例如,双方配对被用于在约会网站上配对男女。
交替和扩展路径
图匹配算法通常使用特定的属性来识别匹配中的次优区域,在这些区域可以进行改进以达到预期的目标。有两个著名的性质增广路径而且交替路径,用于快速判断一个图是否包含最大或最小匹配,或者可以进一步改进匹配。
显示所有连接二部图的边,用蓝色表示。匹配算法的目标,在这个和所有的二部图的情况下,是最大化顶点之间的连接数量的子集 ,到子集中的顶点 ,下面。
大多数算法首先在图中随机创建一个匹配,然后进一步优化匹配,以达到预期的目标。
,与之匹配, ,据说有一个交替路径如果有一条路径,它的边在匹配, ,而不是在匹配,以交替的方式。交替路径通常以一个不匹配的顶点开始,一旦它不能在保持交替序列的同时将另一条边附加到路径的尾部,则终止。
一个增广路径,那么,建立在an的定义之上交替路径描述一个路径,它的端点,即路径的起点和终点的顶点,都是自由的,或者无与伦比的顶点;不包括在匹配中的顶点。在图中寻找增广路径表明缺乏最大匹配。
匹配的, ,因为 的起始点和结束点都不在自由顶点上,因此它没有增广路径。这意味着匹配 是最大匹配。
如果存在增广路径, ,在匹配中, ,然后 不是最大匹配。另外,如果 是最大匹配,那么它没有增广路径。
这个图中的匹配是有增广路径,还是最大匹配?
试着画出交替的路径,看看路径的起点和终点是什么顶点。
图中确实包含交替路径,用下面的交替颜色表示。
一旦路径从 到节点 ,不再有红边,边在里面 ,可以添加到交替路径,意味着终止。注意,端点都是自由顶点,因此路径是交替的,这种匹配不是最大匹配。
匹配问题中的增广路径与最大流量问题中的增广路径密切相关最大流min-cut算法既是信号的次最优性,又是进一步细化的空间。在最大流量问题中,就像在匹配问题中一样,增加路径是源和汇之间的流量可以增加的路径。[1]
图标签
大多数现实的匹配问题比上面提到的要复杂得多。这种增加的复杂性通常来自于图标签,其中标记有量化属性的边或顶点,如权重、成本、偏好或任何其他规格,这为潜在匹配添加了约束。
在标记图中研究的一个共同特征是称为可行的标签在这种情况下,标签或分配给一条边的权值在值上永远不会超过各自顶点的权值之和。这个属性可以被认为是三角不等式.
可行的标签
在哪里 是标签 , 这条边的权值在中间吗 而且 , 节点集在二部图的一边,和 是图另一边的节点集合。
可行标记的作用与增广路径相反;即,存在一个可行的标签意味着一个最大加权匹配,根据Kuhn-Munkres定理.
Kuhn-Munkres定理
如果有一个可行的标签内的项目 , 那么,这是完美的匹配吗 是最大权值匹配。
相反,如果标签在 是可行的, 那么,最大重量匹配吗 是完美的搭配。
当一个图的标记是可行的,并且顶点的标记完全等于连接它们的边的权值,这个图被称为an平等图.
平等图
一个图的等式图 对匹配中的所有边包含以下约束:
相等图对于分部解题很有帮助,因为这些可以在图的子图中找到 ,并引导1到图内的总最大权值匹配。
如果等号子图, ,具有完美的匹配, ,然后 最大重量匹配吗 .
对于图和标签的特定配置,存在各种其他的图标记问题和各自的解决方案;等问题优雅的标签,和谐的标签,lucky-labeling,甚至是名人图着色问题。
匈牙利最大匹配算法
一种常用的二部图匹配算法是匈牙利最大匹配算法,它通过寻找增广路径来寻找最大匹配。更正式地说,该算法通过尝试建立当前匹配, ,旨在找到一个更大的匹配via增广路径.每找到一条增广路径,匹配的数量或总权重就增加1。主要思想是增强 通过最短的增广路径确保没有违反约束。
该算法从任意随机匹配开始,包括空匹配。然后,它使用广度优先搜索来构造一个树,以找到一个扩充路径。如果搜索找到一条增广路径,匹配就会多获得一条边。一旦匹配被更新,算法继续并再次搜索新的增广路径。如果搜索不成功,算法将终止,因为当前匹配必须是尽可能大的匹配。[2]
的时间复杂度原始算法的 ,在那里 是图中顶点的总数。该算法后来被改进为 使用性能更好的数据结构。
开花的算法
不幸的是,不是所有的图都可以用匈牙利匹配算法求解,因为图可能包含产生无限交替路径的循环。在这个特定的场景中开花的算法可以利用找一个最大匹配.blossom算法也被称为Edmonds的匹配算法,它在匈牙利算法的基础上进行了改进,将图中的奇长循环缩小到单个顶点,以便显示扩增路径,然后使用匈牙利匹配算法。
花开是一种循环 组成的 它们的边 属于 ,其中一个顶点, 在循环中,基位于一条交替的等长路径的头部,路径被命名阀杆,到一个暴露的顶点, [3].
花朵算法的工作原理是运行匈牙利算法,直到它遇到花朵,然后它缩小到一个单一顶点。然后,它再次开始匈牙利算法。如果找到了另一朵花,它会缩小花朵并再次启动匈牙利算法,以此类推,直到找不到更多的增广路径或循环。[5]
开花算法的总运行时间为 ,因为 边缘和总 图中的顶点总数。[6]
Hopcroft-Karp算法
匈牙利匹配算法的糟糕性能有时认为它在密集的图中无用,如社交网络。对匈牙利匹配算法进行了改进Hopcroft-Karp算法,这需要一个两偶图, ,输出最大匹配。该算法的时间复杂度为 在最坏的情况下 边缘和总 在图中找到的顶点总数。
Hopcroft-Karp算法使用的技术类似于匈牙利算法和Edmonds的blossom算法。Hopcroft-Karp的工作原理是通过增加路径来反复增加部分匹配的大小。不像匈牙利匹配算法,它找到一条增广路径并增加匹配的最大权值 在每一次迭代中,Hopcroft-Karp算法在每一次迭代中找到一个最短扩展路径的最大集合,允许它以大于的增量增加匹配的最大权值 .
在实践中,研究人员发现Hopcroft-Karp方法并不像理论所暗示的那样好——它通常被广度优先和深度优先的方法所超越,以寻找增广路径。[1]
参考文献
- ,。Hopcroft-Karp算法.检索于2016年6月19日https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
- ,。匈牙利最大匹配算法.检索于2016年6月19日http://demonstrations.wolfram.com/TheHungarianMaximumMatchingAlgorithm/
- ,。开花的算法.检索于2016年6月19日https://en.wikipedia.org/wiki/Blossom_algorithm
- ,一个。埃德蒙兹blossom.svg.检索于2016年6月19日https://en.wikipedia.org/wiki/File:Edmonds_blossom.svg
- Kusner, M。埃德蒙兹的开花算法.检索于2016年6月19日http://matthewkusner.com/MatthewKusner_BlossomAlgorithmReport.pdf
- 鞋匠,A. & Vare, S。埃德蒙兹的开花算法.检索于2016年6月19日http://stanford.edu/~rezab/dao/projects_reports/shoemaker_vare.pdf