在线匹配算法

在线匹配算法（online matching algorithm），理学-计算机科学技术-计算机科学理论-算法-在线算法，在线带权二部图匹配问题是传统匹配问题在在线（见在线算法）场景下的扩展，用以解决动态数据、请求或机遇场景下的资源分配问题。例如企业需要在候选人顺序到来的情况下把他们分配到合适的岗位；搜索引擎需要针对合适的查询词展示能够带来更高收益的广告；男孩、女孩在不断结交新朋友的过程中选择他们的人生伴侣等等。上述场景都可以用在线带权二部图匹配问题来刻画。在1990年，卡普（Karp）等人[2]首次针对在线无权二部图匹配问题进行了研究，并提出了一个高效的算法。他们考虑一个二部图G=(L,R,E)，其中左边的点集L（表示空缺的工作、广告位等等）是已知的问题输入，而右边的点集R（表示候选人、搜索引擎等）以对手安排的顺序一个接一个的到来。当右边的某个点到来时，它所邻接的边才会暴露出来。这时算法必须立即决定是否匹配该点，以及若匹配的话，应该匹配左边的哪个点。当所有的点都到来以后，算法以在线的方式构造了一个二部图匹配。而算法的目标正是最大化该匹配中的边数。