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