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

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

0. 前言

在生活当中有很多场景都可以抽象为多对多匹配问题,比如网约车和外卖派单、会员偏好分配、相亲问题等,可以观察出来,这些问题其实都可以抽象为 $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$

3. 小结

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

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

4. 附录

4.1 最大流样例代码

Dinic,复杂度 $O(V^2E)$

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

简称费用流

最小费用最大流,复杂度 $O(最大流 \times O(SPFA))$

最后修改:2020 年 10 月 12 日
谢谢老板!