`
128kj
  • 浏览: 604424 次
  • 来自: ...
社区版块
存档分类
最新评论

动态规划算法学习十例之一

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

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

1)动态规划是运筹学中用于求解决策过程中的最优化数学方法。 当然,我们在这里关注的是作为一种算法设计技术,作为一种使用多阶段决策过程最优的通用方法。它是应用数学中用于解决某类最优化问题的重要工具。


2)如果问题是由交叠的子问题所构成,我们就可以用动态规划技术来解决它,一般来说,这样的子问题出现在对给定问题求解的递推关系中,这个递推关系包含了相同问题的更小子问题的解。动态规划法建议,与其对交叠子问题一次又一次的求解,不如把每个较小子问题只求解一次并把结果记录在表中(动态规划也是空间换时间的),这样就可以从表中得到原始问题的解。

首先让我们看一个例子:
例1:如下图有一个数字三角阵,请编一个程序计算从顶点至底的某处的一条路径,使该路径所经过的数字的和最大。每一步可沿左斜线向下或右斜线向下走。
          7
      5     3
   4     2    1
2     1    3    7

   这个问题的实质实际上是一个有向图中最长路经问题,可以用经典的图论算法或者搜索来解决。

    考虑如何用搜索法来解这道题,从第一个点开始扩展,每次扩展2个可行节点,直到达到数字三角形的底部,从所有的可行路径中找出最优值,这样做的复杂度是o(2^n),当n很大的时候,普通的搜索法将不可行。

观察发现,搜索的效率低下很大程度上是因为做了大量的重复运算,因为对于任何一个节点,从他开始向下拓展的最优值是确定的,这启发了我们应当充分利用之前的运算结果。
 
下面我们来进行深入的分析,假如已经走第I行第J列,此时最大累加和S[I,J], 应选S[I-1,J-1],S[I-1,J+1]中较大者再加上(I,J)处的值A[I,J],即下式

  S[I,J]=A[I,J]+MAX(S[I-1,J-1],S[I-1,J+1])

  所以我们可以从第一行开始,向下逐行推出每一处位置的最大累加和S,最后从底行的N个S中选出最大的一个即为所求,这种算法的复杂度为o(n^2),比较搜索法,已经大大的降低了,这种充分利用已经计算出结果的方法,就叫做动态规划。

  通过上面的例子,我们对“动态规划”有了一个初步认识,它所处理的问题是一个“多阶段决策问题”。我们现在对一些概念进行具体定义:

状态(State):
   它表示事物的性质,是描述“动态规划”中的“单元”的量。如例1中的每个节点(指节点处的最大值)都为单个的状态。

阶段(Stage):
   阶段是一些性质相近,可以同时处理的状态集合。通常,一个问题可以由处理的先后次序划分为几个阶段。如例1中的问题,每一行若干节点组成一个阶段。一个阶段既可以包含多个状态,也可以只包含一个状态。描述各阶段状态的变量称为状态变量,例1中可用S[4 , j]来表示第四阶段(即第四行)走到第j列的最大值,即第四阶段状态变量。

状态转移方程:
    是前一个阶段的状态转移到后一个的状态的演变规律,是关于两个相邻阶段状态的方程,是“动态规划”的中心。

如例1中: S[I,J]=A[I,J]+MAX(S[I-1,J],S[I-1,J+1])

决策(Decision):
   每个阶段做出的某种选择性的行动。它是我们程序所需要完成的选择。如例1中
MAX(S[I-1,J],S[I-1,J+1])

    动态规划所处理的问题是一个“多阶段决策问题”,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)

动态规划的应用范围,要确定一个问题是否能用动态规划,需要考虑两个方面:


一:最优子结构
    即一个问题的最优解只取决于其子问题的最优解,也就是说,非最优解对问题的求解没有影响。

二:无后效性
     即一个问题被划分阶段后,阶段I中的状态只能由阶段I-1中的状态通过状态转移方程得来,与其他状态没有关系,特别是与未发生的状态没有关系,这就是无后效性。



例2:对于一个由数字组成的二叉树,求由叶子到根的一条路径的数字和的最大值.
           7
         3  8
       8  1  0
    2   7  4  4
  4   5  2  6  5

从上往下计算,对于每一点,只需要保留从上面来的路径中和最大的路径的和即可。
因为在它下面的点只关心到达它的最大路径和,不关心它从那条路经上来的。

import java.util.Scanner;
 
public class Test{
  public static void main(String args[]){
     int n=5;
    int a[][]={{0,0,0,0,0,7,0,0,0,0,0},
               {0,0,0,0,3,0,8,0,0,0,0},
               {0,0,0,8,0,1,0,0,0,0,0},
               {0,0,2,0,7,0,4,0,4,0,0},
               {0,4,0,5,0,2,0,6,0,5,0}};


    int s[][]=new int[5][11];  
    s[0][5]=a[0][5]; 
    for(int i=1;i<n;i++){
     for(int j=1;j<10;j++){
       s[i][j]=Math.max(s[i-1][j-1],s[i-1][j+1])+a[i][j];
     }
    }

    System.out.println("原始数据");
    for(int i=0;i<n;i++){
     for(int j=0;j<11;j++){
       System.out.printf("%-4d",a[i][j]);
    }
    System.out.println();
   }
    
   System.out.println();
   System.out.println("对应的最大路径");
   for(int i=0;i<n;i++){
     for(int j=0;j<11;j++){
       System.out.printf("%-4d",s[i][j]);
    }
    System.out.println();
   }

   System.out.println();
   System.out.println("最长路径的值为:");

    System.out.println(max(s[n-1]));
 
}

  public static int max(int b[]){
    int max=b[0];
   for(int i=1;i<b.length;i++){
     if(b[i]>max) max=b[i];
   }
   return max;
 }
     
}



下载源码:


  • 大小: 11.2 KB
分享到:
评论

相关推荐

    动态规划算法学习十例之八

    标题 "动态规划算法学习十例之八" 暗示了我们将探讨动态规划这一重要的算法概念,特别是通过一个具体的例子——Matrix Chain Multiplication(矩阵链乘法)来深入理解。动态规划是一种解决复杂问题的有效方法,它...

    动态规划算法学习十例之七

    在这个“动态规划算法学习十例之七”的主题中,我们将聚焦于一个具体的动态规划问题——最长公共子序列(Longest Common Subsequence,简称LCS)。这个问题在计算机科学中具有很高的实用价值,尤其是在比较和分析...

    动态规划算法学习十例之九

    在这个“动态规划算法学习十例之九”的主题中,我们将聚焦于如何通过DP来解决实际问题。尽管描述部分没有提供具体的实例,但从标题来看,我们可以推测这是一个关于动态规划应用的系列教程的第九个例子。 动态规划的...

    动态规划算法学习十例之六

    在这个主题“动态规划算法学习十例之六”中,我们将探讨如何利用动态规划方法来解决实际问题。博文链接虽然未提供具体内容,但我们可以根据提供的文件名推测讨论的是一个具体的编程实例。 `Main.java`通常是一个...

    动态规划算法学习十例之五

    标题中的“动态规划算法学习十例之五”表明这篇内容主要关注的是计算机科学中的动态规划算法,这是一种在解决复杂问题时非常有效的优化方法。动态规划通常用于处理具有重叠子问题和最优子结构的问题,通过将大问题...

    动态规划算法学习十例之四

    在这个“动态规划算法学习十例之四”的主题中,我们将专注于背包问题的解决方案。背包问题是一个经典的计算机科学问题,它通常涉及在给定容量的背包中选择物品以最大化总价值。 首先,我们来了解动态规划的基本思想...

    动态规划算法学习十例之二

    在这个"动态规划算法学习十例之二"中,我们很可能会探讨两个具体的动态规划应用:一个可能涉及二项式系数计算,另一个可能是斐波那契数列的求解。下面,我们将深入这两个主题,理解它们背后的动态规划策略。 首先,...

    动态规划算法学习十例之三

    动态规划是一种重要的算法思想,广泛应用于解决复杂问题的优化,如最短路径、背包问题、最长公共子序列等。在本篇文章中,我们将探讨动态规划的精髓,并通过具体实例进行深入学习。博客链接提供了详细的解析,虽然...

    学习常用算法之(7)动态规划

    动态规划算法通常包含以下几个步骤: 1. 定义状态:识别问题中的关键状态,它们通常是问题的某个阶段的特性描述。 2. 状态转移方程:建立从一个状态到下一个状态的转换规则,这个方程描述了如何根据先前的状态计算...

    C++經典算法一百例

    在C++编程中,算法是核心能力之一,它关乎程序的效率和解决问题的能力。"C++经典算法一百例"很可能是某本教程或资源集合,旨在通过一系列实例帮助学习者逐步掌握不同难度的算法。这些算法可能涵盖排序、搜索、图论、...

    算法提高-动态规划(二)

    动态规划是一种强大的算法思想,广泛应用于解决复杂的问题,如最优化、路径规划、背包问题等。在本课程“算法提高-动态规划(二)”中,我们将深入探讨动态规划的原理、应用及其优化技巧。 首先,理解动态规划的...

    算法实例50例

    《算法实例50例》是针对算法学习者的一份宝贵资源,它包含了50个具有代表性的算法案例,旨在帮助初学者深入理解算法的核心概念、逻辑结构和实际应用。算法在计算机科学中扮演着至关重要的角色,它们是解决问题和优化...

    c语言练习题基本算法一百例

    在计算机科学的领域中,算法是解决特定问题的一系列明确指令,而C语言作为实现算法的重要工具之一,一直扮演着极为关键的角色。掌握C语言算法对于任何渴望深化编程技能的程序员来说,是不可或缺的基础。本文将深入...

    算法与设计动态规划法PPT学习教案.pptx

    【算法与设计动态规划法】是计算机科学中解决最优化问题的一种重要方法。动态规划法源于数学优化领域,尤其在解决复杂问题时展现出强大的能力。它与分治法相似,都是通过将大问题分解为小问题来求解,但动态规划的...

    关于C语言学习资料,含算法和典例

    C语言学习资料中的算法部分可能包括排序(如冒泡排序、插入排序、快速排序)、搜索(如线性搜索、二分搜索)、递归、动态规划等经典算法。掌握这些算法对于提高编程能力至关重要。 3. **典例分析**:通过实际的代码...

    动态规划课件-动态规划入门

    动态规划是一种重要的算法,主要应用于解决具有重叠子问题和最优子结构的问题。在信息学竞赛和实际编程挑战中,动态规划是选手必备的技能,因为它可以处理多种复杂问题,如最优化、路径规划等。 首先,让我们理解...

    算法设计与分析实验之背包问题

    动态规划算法是一种精确算法,它可以解决背包问题的最优解。该算法的基本思想是:将背包问题分解成多个子问题,每个子问题的解决方案可以通过动态规划表来存储和查询。 在给定的代码中,动态规划算法的实现过程如下...

    C语言基本算法程序百例

    C语言以其简洁、高效的特点,成为了编写算法程序的首选语言之一。这本书通过大量的实例,帮助读者深入理解并掌握算法的精髓。 1. **基础知识**:在学习算法之前,首先要掌握C语言的基本语法,如变量定义、数据类型...

    C语言经典算法100例

    C语言作为编程领域的经典语言之一,其经典算法的学习与掌握对于提高编程能力与逻辑思维具有重要的意义。在众多的学习资源中,包含了100例C语言算法的文档为编程爱好者提供了一个全面的学习平台。这一系列算法涵盖了...

Global site tag (gtag.js) - Google Analytics