Change Dir

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

• 积分 - 414471
• 排名 - 133

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

source code：DPFE

1: /*
2:  * Copyright (C) 2013 changedi
3:  *
5:  * you may not use this file except in compliance with the License.
6:  * You may obtain a copy of the License at
7:  *
9:  *
10:  * Unless required by applicable law or agreed to in writing, software
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) {
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>();
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) {
68:         double shortest = f(0,path);
69:         System.out.println(shortest);
70:     }
71:
72: }

source code：松弛法

1: /*
2:  * Copyright (C) 2013 changedi
3:  *
5:  * you may not use this file except in compliance with the License.
6:  * You may obtain a copy of the License at
7:  *
9:  *
10:  * Unless required by applicable law or agreed to in writing, software
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) {
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 阅读(1928) 评论(1)  编辑  收藏 所属分类: 算法

评论

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

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