注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

zkw费用流算法的启示  

2010-07-27 22:41:43|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
集训结束后按计划膜拜了一下zkw的blog,发现了一个用zkw命名的费用流算法。

它的精髓在于:reduced cost,即我们可以按某种规则修改边权,透过流量平衡使得最终答案不变。
修改的方法类似km,为顶点计算标号,之后新边权=旧边权+两点之间的标号差。实际上,标号就是从原点到这个点的距离。
看着如此之短的代码,我被震撼了。于是立刻着手实验。
根据blog上的说法,为了解决在稀疏图上速度慢的问题,zkw算法还有一个利用BellmanFord计算距离标号的改进版(算法2)。
我一直使用的是被zkw称为“暴力”的每次用BellmanFord计算最小增广路的算法。
飞速地写了以上3个程序,测时,结果很诡异:
对2000点,10000边的稀疏随机图,“暴力”约等于算法2,比zkw快20倍
对500点,30000边的稠密随机图,“暴力”5.6s,算法二3.34s,zkw1.9s(我的笔记本比较慢,正好用来放大速度的差异)
对2000点,100000边的极限随机图,“暴力”38s,算法二20s,zkw15.8s
总结一下,算法2大约比“暴力”快一倍,而zkw的表现取决于图的稠密性。

为什么呢?

我好好想了一下,发现:zkw算法其实只是“暴力”的一个“小”优化!
它试图通过前一次的距离标号快速计算新的距离标号,之后试图多次增广。
多次增广是这个优化的精髓。
有点像dinic,计算一次bfs层次之后不停增广。

如何验证呢?那就是:让“暴力”算法也多次增广。
BellmanFord出最短路之后,类似dinic,每次只沿着dist[v]=dist[u]+cost(u,v)的边增广,并多路、多次增广。
再次使用数据测试,“暴力”在所有数据上约等于算法2。

看来,剥去reduced cost的神秘面纱,我弄清楚了zkw的真面目:调整标号求最短路,多次增广。
虽然调整标号看起来很神奇,但就求最短路来说,他其实是一个相当糟糕的算法。
而经过优化的“暴力”,就是算法2,也是zkw的优化2。

从山麓分手,到山顶汇合。
一个是“稀疏图专用算法bruteforce”,一个是“稠密图专用算法zkw”,最终取长补短,找到了折衷的平衡点。

http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/costflow^_with^_BellmanFord.cpp
  评论这张
 
阅读(3688)| 评论(5)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017