Change Dir

先知cd——热爱生活是一切艺术的开始

统计

留言簿(18)

积分与排名

“牛”们的博客

各个公司技术

我的链接

淘宝技术

阅读排行榜

评论排行榜

深入理解动态规划的一系列问题(5)

今天主要面对的问题还是路径问题,回顾最短路的Floyd-Warshall算法,决定还是这里把它实现以下。经过前面的训练,当我们确定一个问题可用动态规划方法求解时,最重要的一步就是要先给出状态定义,其后就可以列出DPFE方程了。那么对于FW算法所求解的全路径最短路问题,问题是要求解一个有向图中的所有节点之间的最短路径。也就是说对于一个N个节点的图,总共有N(N-1)/2个可能组合,求解他们的最短路径。对于这时的状态定义,我们可以参考SPC问题,我们可以定义一个状态(k,p,q)表示从p到q的最短路径,其中k表示不超过k段组成。也就是从p到q不超过k段路径的组合中,最短路径的状态。于是,转移方程也就可以列出来了:

F(k,p,q) = min r∈S{b(p, r)+F(k−1,r,q)},k>0。其中当p=q时,F(0,p,q)=0,当p≠q时,F(0,p,q)=∞,b(p,p)=0,b是路径长度函数。

这样,列出方程,我们可以轻松写递归代码求解问题了。

当然这里还是补充一下Floyd-Warshall算法的状态转移方程:F(k,p,q) = min{F(k−1,p,q),F(k−1,p,k)+F(k−1,k,q)},其中当p=q时,F(0,p,q)=0,当p≠q时,F(0,p,q)=b(p,q)。可以看出两者的差异,FW算法缩减了SPC问题求解方法的中间变量r,也就是说每次求解min值不需要在一个状态集合里寻求最短,而把min缩小到(k-1,p,q)和(k-1,p,k)+(k-1,k,q)中,这样直接把计算复杂度降了一个量级。

递归Java source code:

   1: /*
   2:  * Copyright (C) 2013 changedi
   3:  *
   4:  * Licensed under the Apache License, Version 2.0 (the "License");
   5:  * you may not use this file except in compliance with the License.
   6:  * You may obtain a copy of the License at
   7:  *
   8:  * http://www.apache.org/licenses/LICENSE-2.0
   9:  *
  10:  * Unless required by applicable law or agreed to in writing, software
  11:  * distributed under the License is distributed on an "AS IS" BASIS,
  12:  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13:  * See the License for the specific language governing permissions and
  14:  * limitations under the License.
  15:  */
  16: package com.jybat.dp;
  17:  
  18: public class APSP {
  19:  
  20:     private static final int INF = Integer.MAX_VALUE;
  21:  
  22:     // nodes (s,x,y,t) = {0,1,2,3}, so (s,x) = 3 means d[0][1] = 3
  23:     private static int[][] distance = { 
  24:         { INF, 5,      3,     INF }, 
  25:         { INF, INF, 2,     5 },
  26:         { INF, 1,       INF, 8 }, 
  27:         { INF, INF, INF, INF } 
  28:     };
  29:     
  30:     private static int maxNodeIndex = distance.length-1;
  31:     
  32:     private static int[] possibleSuccessors = { 0, 1 };
  33:     
  34:     public static double f(int k, int p, int q) {
  35:         if (k == 0 && p == q)
  36:             return 0;
  37:         if (k == 0 && p != q)
  38:             return distance[p][q];
  39:         double min = Double.MAX_VALUE;
  40:         for (int d : possibleSuccessors) {
  41:             double t = (1 - d) * f(k - 1, p, q) + d * f(k - 1, p, k) + d
  42:                     * f(k - 1, k, q);
  43:             if (t < min)
  44:                 min = t;
  45:         }
  46:         return min;
  47:     }
  48:     /**
  49:      * @param args
  50:      */
  51:     public static void main(String[] args) {
  52:         System.out.println(f(maxNodeIndex,0,3));
  53:     }
  54:  
  55: }

posted on 2014-04-08 10:30 changedi 阅读(1643) 评论(11)  编辑  收藏 所属分类: 算法

评论

# re: 深入理解动态规划的一系列问题(5) 2014-04-08 11:27 金利锁业

支持博主分享  回复  更多评论   

# re: 深入理解动态规划的一系列问题(5) 2014-04-08 15:23 无添加

网址动态好还是静态好呢?  回复  更多评论   

# re: 深入理解动态规划的一系列问题(5) 2014-04-10 09:17 开锁者

期待更新啊博主  回复  更多评论   

# re: 深入理解动态规划的一系列问题(5) 2014-04-10 10:40 零柒锁业

谢谢博主分享啊  回复  更多评论   

# re: 深入理解动态规划的一系列问题(5) 2014-04-10 15:06 柚子舍

动态链接对SEO也越来越友好了。  回复  更多评论   

# re: 深入理解动态规划的一系列问题(5) 2014-04-11 09:36 鹏达锁业

期待更新阿博主  回复  更多评论   

# re: 深入理解动态规划的一系列问题(5) 2014-04-11 10:39 万利锁业

谢谢博主分享  回复  更多评论   

# re: 深入理解动态规划的一系列问题(5) 2014-04-11 22:34 wingsBlog

不明觉厉  回复  更多评论   

# re: 深入理解动态规划的一系列问题(5) 2014-04-12 10:12 万利锁业

期待 更新楼主  回复  更多评论   

# re: 深入理解动态规划的一系列问题(5) 2014-04-12 13:51 魏五锁业

给力支持楼主  回复  更多评论   

# re: 深入理解动态规划的一系列问题(5) 2014-04-12 13:52 鹏达锁业

期待更新AB制  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航: