where the amazing happens

算法2 : 动态规划

动态规划最优化原理中的一种重要的方法。

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决。

总的来说,动态规划的优势在于:

  • 重叠子问题
  • 最优子结构
  • 记忆化


问题描述:
动态规划举例
图10-3(a)示出了一个数字三角形,请编一个程序,
计算从顶至底的某处的一条路劲,
使该路劲所经过的数字的总和最大。
(1) 每一步可沿左斜线向下或右斜线向下;
(2) 1<三角形行数≤100;
(3) 三角形中的数字为0,1,……99。
输入数据:
由INPUT.TXT文件中首先读到的是三角形的行数,
在例子中INPUT.TXT表示如图13-3(b). 
                               
                               7 
                              3 8 
                             8 1 0 
                            2 7 4 4 
                           4 5 2 6 5
                          5 6 9 5 9 8



从别人blog里看到这个题目,手上痒痒,就写了一个.用的是逆向递推法从顶部往下.
分2个文件,一个主程序和一个用于读取文件的辅助类.


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

主程序

package  test;
import  java.util. * ;

/**
 *  用动态规划法求出最优路径
 *  
@author  zqc
 * 
*/

public   class  DynamicSolveTrianglePath  {
    
    
private  String[][] str_triangle  =   null ;
    
private  Node[][] triangle_nodes  =   null ;
    
private  List nodes;
    
private  List paths;
    
    
// 节点
     static   class  Node {
        
private   int  value;
        
private  List path  =   new  Vector();
        
public  List getPath()  {
            
return  path;
        }

        
public   void  setPath(List p) {
            path 
=  p;
        }

        
// n=(0,0) or (0,1) or (2,2)
         public   void  addPath(String n) {
            path.add(n);
        }

        
public   void  addPath(List pa) {
            path.addAll(pa);
        }

        
public   int  getValue()  {
            
return  value;
        }

        
public   void  setValue( int  value)  {
            
this .value  =  value;
        }

    }

    
    
public  DynamicSolveTrianglePath() {
        initNodes();
        findPath();
    }

    
    
//根节点开始,逆向推解出到达所有节点的最佳路径
    private void initNodes(){
        
this.str_triangle = ReadTriangle.getTriangle();
        triangle_nodes 
= new Node[str_triangle.length][];
        nodes 
= new Vector();
        
for(int i = 0 ; i < str_triangle.length; i++){
            triangle_nodes[i] 
= new Node[str_triangle[i].length];
            
for(int j = 0 ; j<str_triangle[i].length;j++){
                String currentPath 
= "("+i+","+j+")";
                Node n 
= new Node();
               
if(i==0&&j==0){
                   n.setValue(
                              c(str_triangle[
0][0])        
                            );
                   n.addPath(currentPath);
                   triangle_nodes[i][j] 
= n;
                   
continue;
               }

               
//左右边界节点
               if((j==0||j==str_triangle[i].length-1)){
                   
if(i==1){//第2行的节点
                       int value = c(str_triangle[0][0])+c(str_triangle[i][j]);
                       List ph 
= triangle_nodes[0][0].getPath();
                       n.addPath(ph);
                       n.addPath(currentPath);
                       n.setValue(value);
                       ph 
= null;
                   }
else{//0,1行以下的其他边界节点
                     int value = j==0?c(str_triangle[i][j])+triangle_nodes[i-1][j].getValue():
                         c(str_triangle[i][j])
+triangle_nodes[i-1][j-1].getValue();
                     List ph 
= j==0?triangle_nodes[i-1][j].getPath():
                         triangle_nodes[i
-1][j-1].getPath();
                     n.addPath(ph);
                     n.addPath(currentPath);
                     n.setValue(value);
                   }

               }
else{//除边界节点外其他节点
                       Node node1 = triangle_nodes[i-1][j-1];
                       Node node2 
= triangle_nodes[i-1][j];
                       Node bigger 
= max(node1,node2);
                       List ph 
= bigger.getPath();
                       n.addPath(ph);
                       n.addPath(currentPath);
                       
int val = bigger.getValue()+c(str_triangle[i][j]);
                       n.setValue(val);
               }

              triangle_nodes[i][j] 
= n; 
              n 
= null;
            }
//end of for j
        }
//end of for i
    }

    
    
private Node max(Node node1,Node node2){
        
int i1 = node1.getValue();
        
int i2 = node2.getValue();
        
return i1>i2?node1:node2;
    }

    
    
private int c(String s){
        
return Integer.parseInt(s);
    }

    
    
//找出最佳路径
    private void findPath(){
        
if(this.triangle_nodes==null)return;
        
int max = 0;
        
int mi = 0;
        
int mj = 0;
        
for(int i = 0 ; i < triangle_nodes.length; i++){
            
for(int j = 0 ; j<triangle_nodes[i].length;j++){
                
int t = triangle_nodes[i][j].getValue();
                
if(t>max){
                    max 
= t;
                    mi 
= i;
                    mj 
= j;
                }

            }

        }

        System.out.println(
"Max Path:"+triangle_nodes[mi][mj].getPath());
        System.out.println(
"Max Value:"+max);
    }

    
    
public static void main(String[] args)throws Exception{
        DynamicSolveTrianglePath dsp 
= new
           DynamicSolveTrianglePath();
    }

    
}

用于读取文件的辅助类

package  test;
import  java.io. * ;
import  java.util. * ;

/**
 *  输入文本格式为
 *  类似这样一个数字三角形
 *  
 *          x
 *         x x
 *        x x x
 *       x x x x
 *      x x x x x 
 *      
 *  
@author  zqc
 * 
*/

public   class  ReadTriangle  {

    
public   static  String TRIANGLE_FILE  =   " d:/triangle.txt " ;
    
    
public   static  String[][] getTriangle() {
        String[][] rtn;
        
try   {
            File f 
=   new
                   File(ReadTriangle.TRIANGLE_FILE);
            BufferedReader br 
=   new  
                BufferedReader(
               
new  FileReader(f)        
            );
            List l 
=   new  Vector();
            String line 
=  br.readLine();
            
while (line != null ) {
                l.add(line.trim());
                line 
=  br.readLine();
            }

            
int  heigth  =  l.size();
            rtn 
=   new  String[heigth][];
            
for ( int  i  =   0  ; i  <  heigth ; i ++ ) {
                String s 
=  (String)l.get(i);
                String[] tk 
=  s.split( "   " );
                
int  tklen  =  tk.length;
                rtn[i] 
=   new  String[tklen];
                
for ( int  k  =   0  ; k  <  tklen ; k ++ ) {
                    rtn[i][k] 
=  tk[k];
                }

            }

            
return  rtn;
        }
  catch  (FileNotFoundException e)  {
            e.printStackTrace();
        }
  catch  (IOException e)  {
            e.printStackTrace();
        }

        
return   null ;
    }

    
}


结果输出如下:

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


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

posted on 2006-04-23 20:47 where the amazing happens 阅读(1800) 评论(5)  编辑  收藏 所属分类: 算法&数据结构

评论

# re: 算法2 : 动态规划 2006-05-09 08:27 T.Sing

排列三角形 你居然用节点写,服了...  回复  更多评论   

# re: 算法2 : 动态规划 2006-05-10 15:46 鸟不生蛋蛋的地方

只要思路清晰,代码自然而然也就写出来了,不过肯定不是最好的方法:)  回复  更多评论   

# re: 算法2 : 动态规划 2006-05-21 10:49 123

、用关系“<”和“=”将3个数A、B和C依次排列时,有13种不同的序关系:
A=B=C,A=B<C,A<B=C,A<B<C,A<C<B,A=C<B,B<A=C,
B<A<C,B<C<A,B=C<A,C<A=B,C<A<B,C<A<B。
若要将n个数依序进行排列,试设计一个动态规划算法,计算出有多少钟不同的序关系?



求解,谢谢  回复  更多评论   

# re: 算法2 : 动态规划 2006-05-22 16:40 鸟不生蛋蛋的地方

楼上的兄弟,最近事情比较多没法静下来好好想.如果不急的话请留下email地址.  回复  更多评论   

# re: 算法2 : 动态规划 2006-07-11 17:45 iris

可否把那个动态规划排序的程序发我一份?我看了你5.22的留言,不好意思不知道还在不在?谢谢
junmei0825@sina.com  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航:
 

公告

点击这里给我发消息

导航

<2006年7月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

统计

常用链接

留言簿(3)

随笔分类(18)

随笔档案(17)

文章分类

相册

其他我的blog

技术Blog

最新随笔

搜索

最新评论

阅读排行榜

评论排行榜