Change Dir

• 随笔 - 123
• 文章 - 0
• 评论 - 182
• 引用 - 0

• 积分 - 367249
• 排名 - 139

深入理解动态规划的一系列问题（5）

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是路径长度函数。

   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 阅读(1469) 评论(11)  编辑  收藏 所属分类: 算法

评论

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

 只有注册用户登录后才能发表评论。 网站导航: 相关文章: