Go语言视频零基础入门到精通

javalearner

1. 
   
2.                           

复制代码

动态规划 是最优化原理 中的一种重要的方法。        动态规划在查找有很多 重叠子问题 的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。       动态规划只能应用于有 最优子结构 的问题。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决。

总的来说，动态规划的优势在于：  
     
      
      
      
      

      
     
   
   
     
     重叠子问题
     最优子结构
     记忆化
     
     问题描述:
动态规划举例
图10-3（a）示出了一个数字三角形，请编一个程序， 计算从顶至底的某处的一条路径， 使该路径所经过的数字的总和最大。

（1） 每一步可沿左斜线向下或右斜线向下；
（2） 1＜三角形行数≤100；
（3） 三角形中的数字为0，1，……99。

输入数据：
由INPUT.TXT文件中首先读到的是三角形的行数，
在例子中INPUT.TXT表示如图13-3（b）.


   
   

1.                            
   
2.                                7
   
3.                               3 8
   
4.                              8 1 0
   
5.                             2 7 4 4
   
6.                            4 5 2 6 5
   
7.                           5 6 9 5 9 8
   
8.                           

复制代码

   
  
  思路:
1.算出每个节点的规划值(也就是待比较的最大值),并记录搜索路径
2.取三角形底边所有规划值中的最大值
3.输出路径

主程序

1. 
   
2. import  java.util. * ;
   
3. /**
   
4. *  用动态规划法求出最优路径
   
5. *   @author  zqc
   
6. *  */
   
7.   public   class  DynamicSolveTrianglePath   {
   
8.    
   
9.      private  String[][] str_triangle  =   null ;
   
10.      private  Node[][] triangle_nodes  =   null ;
    
11.      private  List nodes;
    
12.      private  List paths;
    
13.    
    
14.      // 节点
    
15.        static   class  Node  {
    
16.          private   int  value;
    
17.          private  List path  =   new  Vector();
    
18.          public  List getPath()   {
    
19.              return  path;
    
20.         }
    
21.           public   void  setPath(List p)  {
    
22.             path  =  p;
    
23.         }
    
24.          // n=(0,0) or (0,1) or (2,2)
    
25.            public   void  addPath(String n)  {
    
26.             path.add(n);
    
27.         }
    
28.           public   void  addPath(List pa)  {
    
29.             path.addAll(pa);
    
30.         }
    
31.           public   int  getValue()   {
    
32.              return  value;
    
33.         }
    
34.           public   void  setValue( int  value)   {
    
35.              this .value  =  value;
    
36.         }
    
37.     }
    
38.    
    
39.      public  DynamicSolveTrianglePath()  {
    
40.         initNodes();
    
41.         findPath();
    
42.     }
    
43.    
    
44.      // 从根节点开始,逆向推解出到达所有节点的最佳路径
    
45.     private void initNodes(){
    
46.         this.str_triangle = ReadTriangle.getTriangle();
    
47.         triangle_nodes = new Node[str_triangle.length][];
    
48.         nodes = new Vector();
    
49.         for(int i = 0 ; i < str_triangle.length; i++){
    
50.             triangle_nodes[i] = new Node[str_triangle[i].length];
    
51.             for(int j = 0 ; j< str_triangle[i].length;j++){
    
52.                 String currentPath = "("+i+","+j+")";
    
53.                 Node n = new Node();
    
54.                if(i==0&&j==0){
    
55.                    n.setValue(c(str_triangle[0][0]));
    
56.                    n.addPath(currentPath);
    
57.                    triangle_nodes[i][j] = n;
    
58.                    continue;
    
59.                }
    
60.                //左右边界节点
    
61.                if((j==0||j==str_triangle[i].length-1)){
    
62.                    if(i==1){//第2行的节点
    
63.                        int value = c(str_triangle[0][0])+c(str_triangle[i][j]);
    
64.                        List ph = triangle_nodes[0][0].getPath();
    
65.                        n.addPath(ph);
    
66.                        n.addPath(currentPath);
    
67.                        n.setValue(value);
    
68.                        ph = null;
    
69.                    }else{//0,1行以下的其他边界节点
    
70.                      int value = j==0?c(str_triangle[i][j])+triangle_nodes[i-1][j].getValue():
    
71.                          c(str_triangle[i][j])+triangle_nodes[i-1][j-1].getValue();
    
72.                      List ph = j==0?triangle_nodes[i-1][j].getPath():
    
73.                          triangle_nodes[i-1][j-1].getPath();
    
74.                      n.addPath(ph);
    
75.                      n.addPath(currentPath);
    
76.                      n.setValue(value);
    
77.                    }
    
78.                }else{//除边界节点外其他节点
    
79.                        Node node1 = triangle_nodes[i-1][j-1];
    
80.                        Node node2 = triangle_nodes[i-1][j];
    
81.                        Node bigger = max(node1,node2);
    
82.                        List ph = bigger.getPath();
    
83.                        n.addPath(ph);
    
84.                        n.addPath(currentPath);
    
85.                        int val = bigger.getValue()+c(str_triangle[i][j]);
    
86.                        n.setValue(val);
    
87.                }
    
88.               triangle_nodes[i][j] = n;
    
89.               n = null;
    
90.             }//end of for j
    
91.         }//end of for i
    
92.     }
    
93.    
    
94.     private Node max(Node node1,Node node2){
    
95.         int i1 = node1.getValue();
    
96.         int i2 = node2.getValue();
    
97.         return i1>i2?node1:node2;
    
98.     }
    
99.    
    
100.     private int c(String s){
     
101.         return Integer.parseInt(s.trim());
     
102.     }
     
103.    
     
104.     //找出最佳路径
     
105.     private void findPath(){
     
106.         if(this.triangle_nodes==null)return;
     
107.         int max = 0;
     
108.         int mi = 0;
     
109.         int mj = 0;
     
110.         for(int i = 0 ; i < triangle_nodes.length; i++){
     
111.             for(int j = 0 ; j< triangle_nodes[i].length;j++){
     
112.                 int t = triangle_nodes[i][j].getValue();
     
113.                 if(t>max){
     
114.                     max = t;
     
115.                     mi = i;
     
116.                     mj = j;
     
117.                 }
     
118.             }
     
119.         }
     
120.         System.out.println("Max Path:"+triangle_nodes[mi][mj].getPath());
     
121.         System.out.println("Max Value:"+max);
     
122.     }
     
123.    
     
124.     public static void main(String[] args)throws Exception{
     
125.         DynamicSolveTrianglePath dsp = new
     
126.            DynamicSolveTrianglePath();
     
127.     }
     
128.    
     
129. }
     

复制代码

用于读取文件的辅助类

1. import  java.io. * ;
   
2. import  java.util. * ;
   
3. /**
   
4. *  输入文本格式为
   
5. *  类似这样一个数字三角形
   
6. *  
   
7. *          x
   
8. *         x x
   
9. *        x x x
   
10. *       x x x x
    
11. *      x x x x x
    
12. *      
    
13. *   @author  zqc
    
14. *  */
    
15.   public   class  ReadTriangle   {
    
16.      public   static  String TRIANGLE_FILE  ="c:/java/triangle.txt" ;
    
17.    
    
18.      public   static  String[][] getTriangle()  {
    
19.         String[][] rtn;
    
20.          try{
    
21.             File f  =new File(ReadTriangle.TRIANGLE_FILE);
    
22.             BufferedReader br=new BufferedReader(new  FileReader(f));
    
23.             List l  =new Vector();
    
24.             String line  =br.readLine();
    
25.              while (line != null )  {
    
26.                 l.add(line.trim());
    
27.                 line=br.readLine();
    
28.             }
    
29.              int heigth=l.size();
    
30.             rtn  =new  String[heigth][];
    
31.              for ( int i  =0  ; i< heigth ; i ++ )  {
    
32.                 String s  = (String)l.get(i);
    
33.                 String[] tk  =s.split(" ");
    
34.                  int  tklen  =tk.length;
    
35.                 rtn[i]  =new String[tklen];
    
36.                  for ( int  k  =0  ; k  < tklen ; k ++ )  {
    
37.                     rtn[i][k]  =  tk[k];
    
38.                 }
    
39.             }
    
40.              return  rtn;
    
41.         }   catch  (FileNotFoundException e)   {
    
42.             System.out.println("err1="+e);
    
43.         }   catch  (IOException e)   {
    
44.             System.out.println("err2="+e);
    
45.         }
    
46.          return   null ;
    
47.     }
    
48.    public static void main(String args[]){
    
49.        String[][] trn=ReadTriangle.getTriangle();
    
50.        System.out.println("toal="+trn.length);
    
51.        for(int i=0;i< trn.length;i++){
    
52.             System.out.println("ok="+trn[i].length);
    
53.             for(int j=0;j< trn[i].length;j++)              
    
54.               System.out.println(trn[i][j]);
    
55.       }
    
56.      }
    
57.    
    
58. }
    

复制代码

结果输出如下:

Max Path:[(0,0), (1,0), (2,0), (3,1), (4,1), (5,2)]
Max Value:39

同样的方法可以解决很多类似的问题,比如,游戏中的最短路径;最优化投资问题;背包问题等等.  

  
  
   
   

     
   

     
   
  


源码下载：http://file.javaxxz.com/2014/10/28/235738531.zip