奇迹之流WonderfloW

Nothing Replaces Hard Work!

扯 && 最短路floyd的DP解法解释

| Comments

帮鱼头整理集训队训练教程,据说要出书,瞬间感到压力巨大。就那些平时大家随便写写,只是给自己看看的,非常散漫的解题报告,和专题上很多算法本质都不理解的各种报告组成的一个文档。我真的,压力巨大。那么尽自己力量去整理吧。

整本书的结构就是: 章节(专题介绍->讲的参差不齐);子目录(该专题算法介绍->伪代码(反正不是通俗易懂)); 子目录:例题->题意->思路->代码(这就导致小半本书代码)。

我也不知道这样是好是坏,是否适合读者入门。反正我最讨厌大段大段贴代码的书了。

然后尽力整理吧,其实这本书倒更像是一个模板库,对于把所有专题都了解过的人,是一本很好的复习资料。我就花了一个晚上好好的把整个图论复习了一把。学到不少啊。然后在复习的过程中纠正了书本的各种错误!然后想想,我整理两章都这么折磨了,鱼头可是要出一整本书啊,真是,蛋疼了。

之前鱼头请客带我们一起去游泳,跟鱼头在地铁上聊到我们judge有很多产品,上线了以后出现了一不小心就不能用,然后三天两头出bug的情况。然后鱼头说要来一个测试审核机制,审核通过了才能上线。当时我就说,哪里等的及啊,我们每一个应用完成,都是迫在眉睫需要的时候急急忙忙上线的,而本身我们做judge也不存在竞争关系,大家都是做不同的功能,做好了就能上线的。归根结底还是人手不够,需求太多,耐心不够,时间不够。(PS:做的好没奖金,做的不好也没什么惩罚~o(∩_∩)o ~)这样的情况就导致了每每都是到了deadline我们的任务才完成,也来不及缓冲。

然后我觉得,出书这个事情,其实跟产品上线这个事情是一样的。现在就前期朱艺楠一个人搞搞,后期鱼头一个人搞搞,我跟ZYZ瞎参合一下。还这么急。肯定后面又是一堆bug。

要我来安排的话,就应该把校验书本这个任务安排给每一个想要参加regional比赛的队伍,因为校验书本本身也是一个整理模板的过程啊(针对这本书的特殊性,就是一个模板介绍。)然后每个队各尽所能编排自己队的模板(整理算法教程)。最后把书本的好坏也加入到是否能获得regional比赛资格的一个要素。然后大家精心整理的书再一合并,把每个队的优势专题截取下来,效果一定不会差!

(当然,这前半部分都是我的个人扯淡。具体说不定还存在很多很多我没考虑过的问题。不过我要强调的是:跟鱼头一起去游泳真开心,哈哈~)

然后在校验算法教程的时候,发现了很久以前碰到的一个问题:floyd求最短路,为什么就是那么DP的,为什么?思考了很久,在网上找到了答案~

floyd算法是求解ASPS(all paris shortest paths)的一种算法,时间复杂度是O(n3). 边权可正可负。复杂度O(V3),求出任何一个点到其他点的最短路径。

floyd也是一种典型的动态规划算法。其动态规划方程是:

1
dp[i][j][k] = min( dp[i][k][k-1]+dp[k][j][k-1]);

很明显,对于一个N个节点的网络,可以设置状态数组为 dp[N][N][N] 然后根据状态转移的方程,得出代码如下:

1
2
3
4
5
6
7
8
for(int i=1;i<=N;i++)
  for(int j=1;j<=N;j++)
    dp[i][j][0] = 0;
      for(int k=1;k<=N;k++){
      for(int i=1;i<=N;i++){
      for(int j=1;j<=N;j++){
      dp[i][j][k] = min(dp[i][j][k-1], dp[i][k][k-1]+dp[k][j][k-1]);
}}}

这个状态除了可以用三维的表示外,还可以用二维(或者滚动数组)表示。因为每个k只和k-1有关。

1
2
3
4
5
6
7
8
for(int i=1;i<=N;i++)
  for(int j=1;j<=N;j++)
    dp[i][j] = 0;
    for(int k=1;k<=N;k++){
      for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
          dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
}}}

对于二维的实现一个简单的说明:只需要注意到dp[i][k][k-1]是不会再第k轮改变大小的,dp[k][j][k-1]也不会。也就是说,凡是和k节点相连的边,在第k轮的大小都不会变。所以我们可以放心大胆的把第三维去掉了。(为什么不会改变?把i或者j其中一个用k代替,放入松弛方程中你瞬间就明白了。)

对于floyd算法的一个简单的说明:长久以来,对于floyd的感觉就是那三个循环,很少关注过它的本质,甚至都能够搞混三个循环的嵌套关系,尤其是k。其实这是对于floyd的算法本质不了解,它的动态规划方程一旦知道了,就很清楚这三个循环怎么写了,也不会搞混了。我们学算法,其实最重要的还是要理解算法的本质。

转自:莫亚菜,原帖地址。发现这个哥们写的真的好赞!