一类匹配问题的求解及应用

本文地址：blog.lucien.ink/archives/506
本篇以应用为主，不涉及算法细节

在生活当中有很多场景都可以抽象为多对多匹配问题，比如网约车和外卖派单、会员偏好分配、相亲问题等，可以观察出来，这些问题其实都可以抽象为 N 个物品分配给 M 个人，也就是本文所说的“一类匹配问题”。

大部分时间可以用二分图或者是网络流来解这类问题，小部分时候图论无法满足业务上的强约束，便只能考虑其它算法了。

一般来说，二分图能解决的问题网络流都可以解决，反之不行。

1. 相亲问题

假设有 N 个男生和 M 个女生，如果第 i 个男生可以和第 j 个女生配对，那么在下图中他们俩就会被一条边相连。

算法目标为让配对数量最多。

可以看出，男男1 和 女女2、男男2 和 女女1 相匹配是最优的。

对应的解法为二分图，或者是最大流。

1.1 相亲问题 Plus

假设每对男生女生之间有一个契合度，求怎样配对可以在配对数量最多的前提下契合度总和最高。

男男1 虽然和 女女2 的契合度很高，但是为了满足配对数量最多，他们俩不能配对，所以最优的结果是 男男1 和 女女1、男男2 和 女女2，契合度的总和为 140。

对应的解法为带权二分图，或者是费用流。

2. 网约车派单

假设有 N 个乘客，M 辆车，每辆车最多可以载 4 名乘客，如果第 i 名乘客能被第 j 辆车接到，那么在下图中他们就会被一条边相连。

可以看到，车车2 可以接这 5 名乘客中的任何一名，但是 车车1 却只能接 人人1 和 人人2，所以可行的分配方案之一就是 车车1 去接 人人1，车车2 去接剩下的所有人。

二分图虽然能够通过拆点来解决这个问题，但比较合适的解法是最大流。

2.1 网约车派单 S

每辆车去接每个乘客是需要一定路途时间的（单位：分钟），求怎样派单能够在接最多乘客的情况下，让路途时间总和最短。

可以发现，第 2 节中提到让 车车2 接 4 个人的方案是不够优秀的，总共需要 60 分钟。

最优的派单方案是让 车车1 去接 人人1 和 人人2，车车2 去接剩下的所有人，总共需要 35 分钟。

带权二分图虽然也能通过拆点来解决这个问题，但比较合适的解法是费用流。

2.2 网约车派单 S Plus

因为有的司机的车比较好，有的司机的车比较差，为了提高乘客的乘车体验，公司要求开好车的司机承接 70% 的客流量，开坏车的司机承接 30% 的客流量。

问最多能载多少客。

这个问题就只能用最大流来求解了，解法是新建两个虚拟汇点，一个汇点只属于好车，另一个汇点只属于坏车，然后再流向真正的汇点，流量分别为 70% 和 30% 即可。

求解出来的最大流就是满足群体限流条件下的最大载客数量。

假设 车车1 为好车，车车2 为坏车，建图如下。

其中 边集边集1 和 边集边集2 的流量都为 1，边集边集3 的流量为每辆车的最大载客量，在这里统一为 4。

2.3 网约车派单 Pro

在 2.2 节的基础之上，我们引入路途时间的概念，目标和 2.1 节一样，求怎样派单能够在接最多乘客的情况下，让路途时间总和最短。

这个问题也只能用费用流来求解，图的结构和 2.2 节一样，不同的是每条边会多一个权重。

边集边集2 的权重为路途时间，剩下所有边的权重为 0 即可。

求出的最大流和 2.2 一致，但是派单方案可能不一致。

2.4 网约车派单 Pro Max

假设出了新规定，每次载客的时候，最多载两个男生和两个女生，在满足这个要求和上述所有要求的前提下，求怎样分配能够让路途时间总和最小。

1. 边集边集1 的流量为 1，费用为 0
2. 边集边集2 的流量为 1，费用为路途时间
3. 边集边集3 的流量为 2，费用为 0
4. 边集边集4 的流量为每辆车的最大载客量，此处为 4，费用为 0

至此，我们借助网络流实现了在满足个体接单种类上限、个体流量控制、群里流量控制的前提下，求解最优匹配的功能。

虽然网络流是一个较为简单的算法，但网络流能实现的功能远不限于此。私以为，图论的精髓在于问题抽象与建图，而不是算法本身。本文只是列举了一类非常简单的例子，希望能对读者有一定的帮助。

4.1 最大流样例代码

Dinic，复杂度 O(V2E)

4.2 最小费用最大流样例代码

简称费用流

最小费用最大流，复杂度 最大流O(最大流×O(SPFA))