图论算法的数学模型

神经网络系列之四–线性回归方法与原理

目录

图论算法的数学模型

今天听敦敦敦的课总结一下…

前置芝士:网络流,最小割

引入:最短路的数学形式

松弛操作:

对于一条边\((u,v,w)\)\(\text {if}~(dis_u+w(u,v)<dis_v)~\text{then}~dis_v=dis_u+w(u,v)\)

所以对于求出来的dis,有\(dis_v\leq dis_u+w(u,v)\)对吧。。。
那么这和差分约束中\(x_i-x_j\leq a_k\)是对应的,就可以从\(~j~\)连到\(~i~\)一条权值为\(~a_k~\)的边
这也给了我们一个启发:如果能把要求的贡献/条件转化为图论算法要求的形式,数学问题也可以解决

最小割的数学形式

考虑对于\(~01~\)变量\(~x~\),令\(x=0\)则与源点联通,\(x=1\)则与汇点联通

考虑边\((S,x,a)\),即从源点向\(x\)连了流量为\(a\)的边对最小割的贡献
那么仅当\(~x~\)连与汇点联通时才能算把这条边割掉的贡献,此时\(x=1\)

那么就可以简单地把答案表示为\(a*x\)

同样地,对于边\((x,T,a)\),答案即为\(a*(1-x)\)

最后考虑边\((x,y,a)\),注意是有向边
那么这条边要被割掉仅当\(x\)与源点联通,\(y\)与汇点联通,贡献即为\(a(1-x)y\)

求最小割的本质就是给x赋值对吧
那么我们把要求的贡献表示成这三种形式,不就可以通过最小割算出最小的贡献了?
(最大割是np问题~)

来看一道例题吧:

ZROJ1209

放心你们找不到

这道Java基础题真的有坑!我求求你,认真思考后再回答。

说下题意:

有一个 \(n×m\) 的方格,一开始所有格子都是白色的,你的最终目的是把方格涂成你想要的颜色

你有三种刷的方法:

  • 横着刷连续的 \(k\) 格,代价是 \(ak+b\)
  • 竖着刷连续的 \(k\) 格,代价是 \(ak+b\)
  • 只刷某个格子,代价是 \(c\)

每个格子的颜色是最后刷它的那个刷子的颜色,但是有以下几个限制:

  • 每个格子最多只能被刷两次,无论这些刷子是否同色
  • 每个格子不能先刷白色刷子再刷黑色刷子,因为白色染料比较特殊,这会导致格子变成灰色,但是你可以先刷黑色刷子再刷白色刷子,也可以在一开始格子是初始颜色白色时刷黑色刷子

现在你需要求出,刷出指定颜色的最小代价

有个结论:不会被横刷子涂两次,这样不是白给吗

因为最开始都是白的,我们考虑先刷黑的,再刷白的,最后刷单点,这样一定最优

\(bh[x][y]\)表示 (x,y)是否被横着的黑刷子刷了,\(wv[x][y]\) 表示是否被竖着的白刷子刷了
然后设\(\text{_bv[x][y]}\)表示1-(x,y)是否被竖着的黑刷子刷了,\(\text{_wh[x][y]}\)表示是否被横着的白刷子刷了
这样设是为了表示答案方便,好用最小割求解

考虑横竖刷子的代价\(ak+b\) ,可以把a摊到每个格子上,b算到最后一个格子
那么横着的黑刷子对每个点的贡献就是\(bh[x][y]*a+b*bh[x][y]*(1-bh[x][y+1])\)
其他的同理,显然符合最小割的贡献形式

考虑单点的代价,被单点修改仅当没有被刷子刷过
黑格子贡献:\(c*(1-bh[x][y])*(\text{_bv[x][y]})\)
又因为不能被白的刷过,贡献\(inf*wv[x][y]+inf*(1-\text{_wh[x][y]})\)

那么白格子单点贡献:之前涂了黑但没被涂白
\(c*bh[x][y]*(1-wv[x][y])+x*(1-\text{_bv[x][y]})*\text{_wh[x][y]}\)
而且不能被黑刷子刷两次:\(inf*bh[x][y]*\text{(1-_bv[x][y])}\)

然后对应连点,求最小割,就做完了

一些没用的总结

所以对于一些难抽象出图论模型的最小割题,可以转化成数学模型做,具体就是设设变量然后看看形式对不对应,变量可以设两种形式

比如有一道著名的文理分科题,你想想不就是设每个点选文还是选理,二分图染色设变量为x或1-x,贡献分别就是\(ax,a(1-x)\),组合的贡献就是\(c(x)(1-y),c(1-x)y\)这样讨论吗?

Ansible-上部

© 版权声明
THE END
喜欢就支持一下吧
点赞0
分享