【算法】模拟费用流问题

费用流是我们常常用来解决最优匹配问题的手段,但是由于算法特性,数据集较大的时候便无能为力了;但是,我们仍然可以应用费用流的思想,利用其他某些数据结构,来完成不同的任务

事实上任何最大流,最小费用流,上下界网络流都是在解决一个线性规划问题

也就是说,如果一个题目在抽象为线性规划问题后能够用(流量,权值)的方式表述出来,那么可以考虑进行费用流求解

而费用流问题往往又能够转化为一个全局最优匹配的问题,一般来说,我们通过寻找当前最小权值匹配的方式一步步增广,最终获得全局最优解

而模拟费用流便是指运用费用流的思想,使用任何其他的方式来解决费用流问题的一类解题方式

一般来说,由于费用流的复杂度来说较高,使用其他的方式进行求解往往能够达到优化时空复杂度的目的,这也是我们使用模拟费用流算法的原因

由于模拟费用流算法的多样性和抽象性,并不能将其一一列举出来,故只在此处介绍一些基本的模型,希望能够引起大家的思考

模型一

每只老鼠只能往左走
求所有老鼠都进洞的最小总代价(即行走的最小总距离)

观察发现,问题等价于将老鼠和洞进行匹配,老鼠的权值为 $x_i$ ,洞的权值为 $-x_i$
求最小权值和

由于老鼠只能向左走,考虑费用流的增广,每只老鼠必然选择当前能够走到的权值最小(尽量靠右)的一个洞进行匹配

所以可以使用一个栈来维护当前有哪些洞可以走到,每次遇到老鼠匹配栈顶的洞即可

模型二

每只老鼠能往左走或者往右走
求所有老鼠都进洞的最小总代价(即行走的最小总距离)

首先可以很简单的建出费用流的模型

mnfyl1
mnfyl1

观察发现,增广某个 $mouse$ 后,将会改变路径的权值,也就是说,改变某些点的距离

假设 $mouse1$ 走到了 $hole2$ ,那么 $D-A$ 路径的距离将会变为 $-(y[D]-x[A])$
也就是说,如果 $mouse2$ 想要匹配 $hole2$ 左侧的节点 $hole1$,距离会减少 $-2(y[D]-x[A])$

换句话说,匹配 $hole2$ 左侧的节点相当于 $mouse2$ 走到 $hole2$ ,而原来匹配 $hole2$ 的 $mouse1$ 退回去走到 $hole1$

观察发现假设 $C$ 在 $A,D$ 之间也是同样的情况

可以考虑对其进行模拟

为了方便,只考虑向左侧进行选择,原来的向右走等价于洞向左走

假设当前位置为一只老鼠,那么我需要找到前面的一个洞进行匹配,并且必须找到一个洞进行匹配,从而保证每时每刻每个老鼠都有它的匹配洞

那么为了防止有些老鼠在左侧没有洞的情况,一开始在最左侧放一些权值巨大的洞,强行进行匹配,这就保证了每个老鼠至少有一个前面的洞可以匹配

假设有一只牛皮哄哄的老鼠,它会抢夺前面老鼠匹配的洞,如果能够使得总距离更小,这样的行为也是没有问题的
也就相当于该老鼠走到前面老鼠的位置,前面老鼠退回到原地,并匹配更前面的位置

为什么被抢夺匹配洞的老鼠一定有更前面的洞匹配呢?
如果一个老鼠的洞被抢夺,说明这个洞肯定不是前面权值巨大的洞,因为抢权值巨大的洞没有意义(答案无法变小)

所以至少还有一个洞可以给被抢匹配洞的老鼠进行匹配

同样,若当前位置为一个洞,也可以抢夺前面洞匹配的老鼠
而且对于一个匹配了巨大权值的洞的老鼠,一定会被当前位置的洞抢夺,因为一次就可以减少很多距离
而且一个洞的成功抢夺,必定是使一只往左跑的老鼠改为往右跑,因为若本来就是往右跑,那么距离肯定是增加了,显然不会抢夺成功

对于洞来说,退回到匹配前状态后,可能是没有匹配的,不过这没有关系,因为不一定要求它一定有匹配,不管就好了

那么,对于老鼠,使用堆维护其每个匹配的贡献
对于洞,使用堆维护其每个匹配的贡献
每次取贡献值最大的进行匹配即可,由于我们需要减去上次的贡献,这样就能保证这次的贡献尽可能小,从而获得全局的最优解

也就是说,相当于我们将所有可以被选择的洞和老鼠丢到了堆中,保存了选择他们能够减少的贡献,这些可以选择的老鼠和洞,有可能是已经匹配的,那么就相当于是例子中的情况;有可能是没有匹配的,那么可以直接匹配

感性的理解,放到堆里面的元素是一类匹配方案每次对答案的增量,每次去掉一个最大的增量,塞入新的增量就是我们算法的基本思路,也就是所谓的对之前的匹配进行“反悔”

模型三

每只老鼠能往左走或者往右走,每个洞有附加权值
求所有老鼠都进洞的最小总代价(即行走的最小总距离)

和上题类似,只需要在计算权值时加上贡献即可

模型四

每只老鼠能往左走或者往右走
每个洞可以容纳多只老鼠,有一个容量上限
求所有老鼠都进洞的最小总代价(即行走的最小总距离)

考虑之前的做法,当加入一个老鼠的匹配时,我们的操作是不变的
当加入一个洞时,我们可以往堆中丢一个 pair,分别表示匹配的代价和容量

注意到,每次进行匹配都会使一只未匹配的老鼠匹配或者使一只往左跑的老鼠改为往右跑,所以堆操作的总次数依然是线性的

模型五

每只老鼠能往左走或者往右走
每个位置有一群老鼠
每个洞可以容纳多只老鼠,有一个容量上限
求所有老鼠都进洞的最小总代价(即行走的最小总距离)

根据之前的做法,应该是老鼠和洞每次操作都丢一个 pair 进去

具体复杂度的证明我暂时还不会,咕咕咕警告

模型六

考虑将模型五放到树上

由于树优秀的性质,我们可以将老鼠们的匹配分为在子树中匹配或者是在祖先处匹配

一开始将所有没有匹配的老鼠强行匹配一个垃圾的洞,不能加入到返回序列中以防其被抢走这唯一的洞

然后从底向上合并老鼠和洞即可

Comments

添加新评论