# Change Dir

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

• 积分 - 417650
• 排名 - 133

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

   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 ShortestPathAcyclic {
  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, 3,      5,     INF },
  28:         { INF, INF, 1,     8 },
  29:         { INF, INF, INF, 5 },
  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){
  44:         if(currentNode==3) return 0.0;
  45:         else{
  46:             Set<Integer> possibleSuccessors = possibleNextNodes(currentNode);
  47:             double min = Double.MAX_VALUE;
  48:             for(Integer d : possibleSuccessors){
  49:                 double dis = distance[currentNode][d]+f(d);
  50:                 if(dis<min) {
  51:                     min = dis;
  52:                 }
  53:             }
  54:             return min;
  55:         }
  56:     }
  57:
  58:     /**
  59:      * @param args
  60:      */
  61:     public static void main(String[] args) {
  62:         double shortest = f(0);
  63:         System.out.println(shortest);
  64:     }
  65:
  66: }

posted on 2014-03-17 13:40 changedi 阅读(1541) 评论(0)  编辑  收藏 所属分类: 算法

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