# Change Dir

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

• 积分 - 365378
• 排名 - 137

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

source code：DPFE

   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: import java.util.HashSet;
  19: import java.util.Set;
  20:
  21: public class ShortestPathCyclic {
  22:
  23:     private static final int INF = Integer.MAX_VALUE;
  24:
  25:     private static Set<Integer> path = new HashSet<Integer>();
  26:     // nodes (s,x,y,t) = {0,1,2,3}, so (s,x) = 3 means d[0][1] = 3
  27:     private static int[][] distance = {
  28:         { INF, 5,      3,     INF },
  29:         { INF, INF, 2,     5 },
  30:         { INF, 1,       INF, 8 },
  31:         { INF, INF, INF, INF }
  32:     };
  33:
  34:     private static Set<Integer> possibleNextNodes(int node) {
  35:         Set<Integer> result = new HashSet<Integer>();
  36:         for (int i = 0; i < distance[node].length; i++) {
  37:             if (distance[node][i] != INF) {
  38:                 result.add(new Integer(i));
  39:             }
  40:         }
  41:         return result;
  42:     }
  43:
  44:     public static double f(int currentNode, Set<Integer> nodesVisited){
  45:         if(currentNode==3) return 0.0;
  46:         else{
  47:             Set<Integer> possibleSuccessors = possibleNextNodes(currentNode);
  48:             possibleSuccessors.removeAll(nodesVisited);
  49:             double min = Double.MAX_VALUE;
  50:             for(Integer a : possibleSuccessors){
  51:                 Set<Integer> set = new HashSet<Integer>();
  52:                 set.addAll(nodesVisited);
  53:                 set.add(a);
  54:                 double dis = distance[currentNode][a]+f(a,set);
  55:                 if(dis<min) {
  56:                     min = dis;
  57:                 }
  58:             }
  59:             return min;
  60:         }
  61:     }
  62:
  63:     /**
  64:      * @param args
  65:      */
  66:     public static void main(String[] args) {
  67:         path.add(0);
  68:         double shortest = f(0,path);
  69:         System.out.println(shortest);
  70:     }
  71:
  72: }

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: import java.util.HashSet;
  19: import java.util.Set;
  20:
  21: public class ShortestPathCyclic2 {
  22:
  23:     private static final int INF = Integer.MAX_VALUE;
  24:
  25:     // nodes (s,x,y,t) = {0,1,2,3}, so (s,x) = 3 means d[0][1] = 3
  26:     private static int[][] distance = {
  27:         { INF, 5,      3,     INF },
  28:         { INF, INF, 2,     5 },
  29:         { INF, 1,       INF, 8 },
  30:         { INF, INF, INF, INF }
  31:     };
  32:
  33:     private static Set<Integer> possibleNextNodes(int node) {
  34:         Set<Integer> result = new HashSet<Integer>();
  35:         for (int i = 0; i < distance[node].length; i++) {
  36:             if (distance[node][i] != INF) {
  37:                 result.add(new Integer(i));
  38:             }
  39:         }
  40:         return result;
  41:     }
  42:
  43:     public static double f(int currentNode, int noOfEdgesToTarget){
  44:         if(currentNode==3)
  45:             return 0.0;
  46:         else if(noOfEdgesToTarget==0&&currentNode!=3)
  47:             return INF;
  48:         else{
  49:             Set<Integer> possibleSuccessors = possibleNextNodes(currentNode);
  50:             double min = Double.MAX_VALUE;
  51:             for(Integer d : possibleSuccessors){
  52:                 double dis = distance[currentNode][d]+f(d,noOfEdgesToTarget-1);
  53:                 if(dis<min) {
  54:                     min = dis;
  55:                 }
  56:             }
  57:             return min;
  58:         }
  59:     }
  60:
  61:     /**
  62:      * @param args
  63:      */
  64:     public static void main(String[] args) {
  65:         double shortest = f(0,3);
  66:         System.out.println(shortest);
  67:     }
  68:
  69: }

posted on 2014-03-24 09:44 changedi 阅读(1763) 评论(1)  编辑  收藏 所属分类: 算法

### 评论

#### #re: 深入理解动态规划的一系列问题（3） 2014-03-25 08:46 魏五锁业

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