精华内容
下载资源
问答
  • 动态规划法与分治法的区别 动态规划法与贪心法的区别 分枝限界法与回溯法的异同 等自己的总结
  • 动态规划法

    2014-04-26 21:26:38
    在学习动态规划法之前,我们先来了解动态规划的几个概念 1、 阶段:把问题分成几个相互联系的有顺序的几个环节,这些环节即称为阶段。 2、 状态:某一阶段的出发位置称为状态。 3、 决策:从某阶段的一...
    http://blog.chinaunix.net/uid-313981-id-2417901.html
    在学习动态规划法之前,我们先来了解动态规划的几个概念
    1、  阶段:把问题分成几个相互联系的有顺序的几个环节,这些环节即称为阶段。
    2、  状态:某一阶段的出发位置称为状态。
    3、  决策:从某阶段的一个状态演变到下一个阶段某状态的选择。
    4、  状态转移方程:前一阶段的终点就是后一阶段的起点,前一阶段的决策选择导出了后一阶段的状态,这种关系描述了由k阶段到k+1阶段状态的演变规律,称为状态转移方程。
    动态规划法的定义:在求解问题中,对于每一步决策,列出各种可能的局部解,再依据某种判定条件,舍弃那些肯定不能得到最优解的局部解,在每一步都经过筛选,以每一步都是最优解来保证全局是最优解,这种求解方法称为动态规划法。
    一般来说,适合于用动态规划法求解的问题具有以下特点:
    1、可以划分成若干个阶段,问题的求解过程就是对若干个阶段的一系列决策过程。
    2、每个阶段有若干个可能状态
    3、一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态。
    4、在任一个阶段,最佳的决策序列和该阶段以前的决策无关。
    5、各阶段状态之间的转换有明确定义的费用,而且在选择最佳决策时有递推关系(即动态转移方程)。
    动态规划法所处理的问题是一个多阶段最优化决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线。如下图:
     

    动态规划设计都有着一定的模式,一般要经历以下几个步骤:
    1、划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。
    2、确定状态:将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。
    3、确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态,所以如果确定了决策,状态转移方程也就可以写出。
    4、寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。
    5、程序设计实现:动态规划的主要难点在于理论上的设计,一旦设计完成,实现部分就会非常简单。
    根据以上的步骤设计,可以得到动态规划设计的一般模式:
    for k:=阶段最小值to 阶段最大值do {顺推每一个阶段}
      for I:=状态最小值to 状态最大值do {枚举阶段k的每一个状态}
      for j:=决策最小值to 决策最大值do {枚举阶段k中状态i可选择的每一种决策}
    f[ik]:=min(max){f[ik-1]+a[ik-1,jk-1]|ik-1通过决策jk-1可达ik}
     
    有了以上的设计模式,对于简单的动态规划问题,就可以按部就班地进行动态规划设计。
    例1:合唱队形(noip2004tg)
    【问题描述】N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1, 2, …, K,他们的身高分别为T1, T2, …, TK,则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
    【输入文件】输入文件chorus.in的第一行是一个整数N(2 <= N <= 100),表示同学的总数。第一行有n个整数,用空格分隔,第i个整数Ti(130 <= Ti <= 230)是第i位同学的身高(厘米)。
    【输出文件】输出文件chorus.out包括一行,这一行只包含一个整数,就是最少需要几位同学出列。
    【样例输入】8
    186 186 150 200 160 130 197 220
    【样例输出】 4
    算法分析:此题采用动态规划法求解。先分别从左到右求最大上升子序列,从右到左求最大下降子序列,再枚举中间最高的一个人。算法实现起来也很简单,时间复杂度O(N^2)。
    我们先考虑如何求最大上升子序列的长度,设f1(i)为前i个同学的最大上升子序列长度。若要求f1(i),必须先求得f1(1),f1(2),…,f1(i-1),再选择一个最大的f1(j)(j<i),在前j个数中的最大上升序后添加Ti,就可得到前i个数的最大上升子序列f1(i)。这样就得到状态转移方程:
    f1(i)=max{f1(j)+1} (j<i,Tj<Ti)
    边界条件:f1(1)=1;
    设f2(i)为后面N-i+1位排列的最大下降子序列长度,用同样的方法可以得到状态转移方程:f2(i)=max{f2(j)+1} (i<j,Tj<Ti);边界值为f2(N)=1;
    有了状态转移方程,程序实现就非常容易了。
    源程序:
    var
      t,f1,f2:array[1..100]of byte;
      i,j,n,max:integer;
    begin
      assign(input,'chorus.in');
      reset(input);  readln(n);
      for i:=1 to n do begin
    read(t[i]);f1[i]:=1;f2[i]:=1;
    end;{for}
      close(input); max:=0;
      for i:=2 to n do
        for j:=1 to i-1 do begin
          if (t[i]>t[j])and(f1[j]>=f1[i]) then f1[i]:=f1[j]+1; {从左到右求最大上升子序列}
          if (t[n-i+1]>t[n-j+1])and(f2[n-j+1]>=f2[n-i+1]) then f2[n-i+1]:=f2[n-j+1]+1; {从右到左求最大下降子序列}
        end;{for}
      for i:=1 to n do if max<f1[i]+f2[i] then max:=f1[i]+f2[i]; {枚举中间最高的}
      assign(output,'chorus.ans');
    rewrite(output);
      writeln(n-max+1);
    close(output);
    end.
    运用动态规划法求解问题的关键是找出状态转移方程,只要找出了状态转移方程,问题就解决了一半,剩下的事情就是解决如何把状态转移方程用程序实现。
    例2、乘积最大(noip2000tg)
    题目大意:在一个长度为N的数字串中插入r个乘号,将它分成r+1个部分,找出一种分法,使得这r+1个部分的乘积最大。
    算法分析:此题满足动态规划法的求解标准,我们把它按插入的乘号数来划分阶段,若插入K个乘号,可把问题看做是K个阶段的决策问题。设f[i,k]表示在前i位数中插入K个乘号所得的最大值,a[i,j]表示从第i位到第j位所组成的自然数。用f[i,k]存储阶段K的每一个状态,可以得状态转移方程:
    f[i,k]=max{f[j,k-1]*a[j+1,i]}(k<=j<=i)
    边界值:f[j,0]=a[1,j] (1<j<=i)
    根据状态转移方程,我们就很容易写出动态规划程序:
    for k:=1 to r do
      for i:=k+1 to n do
        for j:=k to I do
           if f[i,k]<f[j,k-1]*a[j+1,I] then f[i,k]:=f[j,k-1]*a[j+1,i]
    源程序(略)。
    近年来,涉及动态规划的各种竞赛题越来越多,每一年的NOIP都至少有一道题目需要用动态规划法求解。而应用动态规划法解题是富于技巧性和创造性的,虽然在前面的求解过程中给出了一个解题的基本模式,但由于动态规划题目出现的形式多种多样,并且大部分题目表面上看不出与动态规划的直接联系,只有在充分把握其思想精髓的前提下大胆联想,多做多练才能达到得心应手,灵活运用的境界。
    展开全文
  • 算法设计与分析—— 动态规划法

    千次阅读 2018-09-10 11:48:11
    五大经常使用算法 之 动态规划法 一、基本概念 &amp;nbsp;&amp;nbsp;&amp;nbsp; 动态规划过程是:每次决策依赖于当前状态。又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,...

    原博客地址:
    https://www.cnblogs.com/brucemengbm/p/6875340.html

    五大经常使用算法 之 动态规划法

    一、基本概念

        动态规划过程是:每次决策依赖于当前状态。又随即引起状态的转移。

    一个决策序列就是在变化的状态中产生出来的,所以,这样的多阶段最优化决策解决这个问题的过程就称为动态规划。

        动态规划是运筹学中用于求解决策过程中的最优化数学方法。

    当然。我们在这里关注的是作为一种算法设计技术,作为一种使用多阶段决策过程最优的通用方法。

    它是应用数学中用于解决某类最优化问题的重要工具。

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

        动态规划经常常使用于解决最优化问题,这些问题多表现为多阶段决策。

        关于多阶段决策

        在实际中,人们经常遇到这样一类决策问题:即因为过程的特殊性,能够将决策的全过程根据时间或空间划分若干个联系的阶段。

    而在各阶段中。人们都须要作出方案的选择。我们称之为决策。而且当一个阶段的决策之后,经常影响到下一个阶段的决策,从而影响整个过程的活动。这样,各个阶段所确定的决策就构成一个决策序列,常称之为策略。

    因为各个阶段可供选择的决策往往不止一个。因而就可能有很多决策以供选择,这些 可供选择的策略构成一个集合,我们称之为同意策略集合(简称策略集合)。每一个策略都对应地确定一种活动的效果。我们假定这个效果能够用数量来衡量。

    因为不同的策略经常导致不同的效果,因此,怎样在同意策略集合中选择一个策略,使其在预定的标准下达到最好的效果。经常是人们所关心的问题。我们称这种策略为最优策略,这类问题就称为多阶段决策问题。

        多阶段决策问题举例:机器负荷分配问题

        某种机器能够在高低两种不同的负荷下进行生产。在高负荷下生产时。产品的年产量g和投入生产的机器数量x的关系为g=g(x),这时的年完善率为a,即假设年初完善机器数为x,到年终时完善的机器数为a*x(0<a<1);在低负荷下生产时,产品的年产量h和投入生产的机器数量y的关系为h=h(y)。对应的完善率为b(0<b<0)。且a<b。

        假定開始生产时完善的机器熟练度为s1。

    要制定一个五年计划,确定每年投入高、低两种负荷生产的完善机器数量,使5年内产品的总产量达到最大。

        这是一个多阶段决策问题。

    显然能够将全过程划分为5个阶段(一年一个阶段),每一个阶段開始时要确定投入高、低两种负荷下生产的完善机器数,并且上一个阶段的决策必定影响到下一个阶段的生产状态。决策的目标是使产品的总产量达到最大。这个问题常常使用数学方法建模,结合线性规划等知识来进行解决。


    二、基本思想与策略

        基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了实用的信息。

    在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其它局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

        因为动态规划解决的问题多数有重叠子问题这个特点。为降低反复计算。对每个子问题仅仅解一次,将其不同阶段的不同状态保存在一个二维数组中。

        与分治法最大的区别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)


    三、适用的情况

    能採用动态规划求解的问题的一般要具有3个性质:

    (1)、最优化原理:假设问题的最优解所包括的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

    (2)、无后效性:即某阶段状态一旦确定。就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响曾经的状态。仅仅与当前状态有关;

    (3)、有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到(该性质并非动态规划适用的必要条件,可是假设没有这条性质。动态规划算法同其它算法相比就不具备优势)。


    四、求解的基本步骤

    动态规划所处理的问题是一个多阶段决策问题。一般由初始状态開始。通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列。同一时候确定了完毕整个过程的一条活动路线(一般是求最优的活动路线)。动态规划的设计都有着一定的模式。一般要经历下面几个步骤。

    初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

    (1)划分阶段:依照问题的时间或空间特征。把问题分为若干个阶段。在划分阶段时。注意划分后的阶段一定要是有序的或者是可排序的。否则问题就无法求解。

    (2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。

    当然,状态的选择要满足无后效性。

    (3)确定决策并写出状态转移方程:由于决策和状态转移有着天然的联系,状态转移就是依据上一阶段的状态和决策来导出本阶段的状态。所以假设确定了决策。状态转移方程也就可写出。但其实经常是反过来做。依据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程

    (4)寻找边界条件:给出的状态转移方程是一个递推式。须要一个递推的终止条件或边界条件。

    一般,仅仅要解决这个问题的阶段状态状态转移决策确定了。就能够写出状态转移方程(包含边界条件)。

    实际应用中能够按下面几个简化的步骤进行设计:

    (1)分析最优解的性质。并刻画其结构特征。

    (2)递归的定义最优解。

    (3)以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值。

    (4)依据计算最优值时得到的信息,构造问题的最优解。


    五、算法实现的说明

        动态规划的主要难点在于理论上的设计,也就是上面4个步骤的确定,一旦设计完毕。实现部分就会很easy。

        使用动态规划求解问题,最重要的就是确定动态规划三要素问题的阶段每一个阶段的状态从前一个阶段转化到后一个阶段之间的递推关系

        递推关系必须是从次小的问题開始到较大的问题之间的转化,从这个角度来说,动态规划往往能够用递归程序来实现,只是由于递推能够充分利用前面保存的子问题的解来降低反复计算,所以对于大规模问题来说。有递归不可比拟的优势。这也是动态规划算法的核心之处

        确定了动态规划的这三要素,整个求解过程就能够用一个最优决策表来描写叙述最优决策表是一个二维表,当中行表示决策的阶段,列表示问题状态。表格须要填写的数据一般相应此问题的在某个阶段某个状态下的最优值(如最短路径。最长公共子序列,最大价值等),填表的过程就是依据递推关系,从1行1列開始,以行或者列优先的顺序,依次填写表格。最后依据整个表格的数据通过简单的取舍或者运算求得问题的最优解。


    六、动态规划——几个典型案例

    1、计算二项式系数

    问题描写叙述:

        计算二项式系数

    问题解析:

        在排列组合中,我们有下面公式:

        当n>k>0时。C(n,k) = C(n-1,k-1) + C(n-1,k)

        这个式子将C(n,k)的计算问题简化为(问题描写叙述)C(n-1,k-1)和C(n-1,k)两个较小的交叠子问题。

        初始条件:C(n,n) = C(n,0) = 0;

        我们能够用填矩阵的方式求解C(n,k):

     

        上图即为二项式系数矩阵表。

        那么。我们要计算出任一C(n,k)。我们能够尝试求出全部的二项式系数表格。然后通过查表来进行计算操作。

        这里,我们的构建二项式系数表的函数为(填矩阵):

        int BinoCoef(int n, int k);

    函数及详细程序实现例如以下:

    #include <stdio.h>
    #define MAX 100
    int BinoCoef(int n, int k);
    int main(){
        int n,k,result;
        printf("Please input n and k:\n");
        scanf("%d %d",&amp;n,&amp;k);
        result = BinoCoef(n,k);
        printf("The corrsponding coefficent is %d !\n",result);
    
        return 0; 
    }
    int BinoCoef(int n, int k){
        int data[MAX][MAX];
        int i,j;
        for(i=0;i&lt;=n;i++)
        {
            for(j=0;j&lt;=((i&lt;k)?<p></p><p>i:k);j++)
            {
                if(i == 0||i == j)
                    data[i][j] = 1;
                else
                    data[i][j] = data[i-1][j] + data[i-1][j-1];     
            }
        }
        return data[n][k];
    } 


    这里,我们要注意动态规划时的这样几个关键点:

    (1)、怎么描写叙述问题。要把问题描写叙述为交叠的子问题;

    (2)、交叠子问题的初始条件(边界条件);

    (3)、动态规划在形式上往往表现为填矩阵的形式;

    (4)、递推式的依赖形式决定了填矩阵的顺序。


    2、三角数塔问题:

    问题描写叙述:

        设有一个三角形的数塔。顶点为根结点。每一个结点有一个整数值。从顶点出发,能够向左走或向右走,要求从根结点開始,请找出一条路径,使路径之和最大。仅仅要输出路径的和。如图所看到的:

     

        当然,正确路径为13-8-26-15-24(和为86)。

    问题解析:

        如今,怎样求出该路径?

        首先,我们用数组保存三角形数塔,并设置距离矩阵d[i][j],用于保存节点(i,j)到最底层的最长距离,从而,d[1][1]即为根节点到最底层的最大路径的距离。

    行/列

    1

    2

    3

    4

    5

    1

    13

     

     

     

     

    2

    11

    8

     

     

     

    3

    12

    7

    26

     

     

    4

    6

    14

    15

    8

     

    5

    12

    7

    13

    24

    11

    方法一:递推方式

        相应函数:void fnRecursive(int,int);

        对于递推方式。其基本思想是基于指定位置。逐层求解:

        举例:找寻从点(1,1)開始逐层向下的路径的最长距离。

        思想:自底向上的逐步求解(原因在于,这是一个三角形的矩阵形式,向上收缩,便于求解)。

        首先。在最底层,d[n][j]=a[n][j](将最底层的节点到最底层的最长路径距离设置为节点值)。

        然后。逐层向上进行路径距离处理,这里须要注意距离处理公式:

        d[i-1][j] = min{ (d[i][j] + a[i-1][j]), (d[i][j+1] + a[i-1][j]) }

        最后,递推处理路径距离至根节点就可以,这样就建立了一个完整的路径最长距离矩阵,用来保存三角数塔节点到最底层的最长路径距离。

    方法二:记忆化搜索方式

        相应函数:int fnMemorySearch(int i,int j);

        记忆化搜索方式的核心在于保存前面已经求出的距离值,然后依据这些距离值能够求出后面所需求解的距离值。

    该函数的返回值即为节点(i,j)到最底层的最长路径距离值。

        这里,我们能够去考究这样几个问题:

    (1)在什么时候结束?

    (2)有何限制条件和一般情况处理?

        问题1解析:

        当d[i][j]>0时,则说明节点(i,j)到最底层的最长路径距离已经存在,因此直接返回该值就可以。

        问题2解析:

        限制条件:当节点(i,j)位于最底层时,即i==n时,这时d[i][j]应该初始化为a[i][j];

        一般情况处理:即节点(i,j)的赋值问题。

        这里有两种情况:

        第一种情况,节点(i,j)相应的最长路径的下一层节点为左边节点:

        此时,d[i][j] = a[i][j] + fnMemorySearch(i+1,j);

        另外一种情况,节点(i,j)相应的最长路径的下一层节点为右边节点:

        此时,d[i][j] = a[i][j] + fnMemorySearch(i+1,j+1);

    代码实现:

    #include <stdio.h>
    #include <stdlib.h>
    #define MAXN 101
    
    int n,d[MAXN][MAXN];
    int a[MAXN][MAXN];
    void fnRecursive(int,int);
    //递推方法函数声明
    int fnMemorySearch(int,int);
    //记忆化搜索函数声明
    int main()
    {
        int i,j;
        printf("输入三角形的行数n(n=1-100):\n");
        scanf("%d",&amp;n);
        printf("按行输入数字三角形上的数(1-100):\n");
        for(i=1; i&lt;=n; i++)
            for(j=1; j&lt;=i; j++)
                scanf("%d",&amp;a[i][j]);
        for(i=1; i&lt;=n; i++)
            for(j=1; j&lt;=i; j++)
                d[i][j]=-1;//初始化指标数组
        printf("递推方法:1\n记忆化搜索方法:2\n");
        int select;
        scanf("%d",&amp;select);
        if(select==1)
        {
            fnRecursive(i,j);//调用递推方法
            printf("\n%d\n",d[1][1]);
        }
        else if(select==2)
        {
            printf("\n%d\n",fnMemorySearch(1,1));//调用记忆化搜索方法
        }
        else
            printf("输入错误!");
            return 0;
    }
    void fnRecursive(int i,int j)
    //递推方法实现过程
    {
        for(j=1; j&lt;=n; j++)
            d[n][j]=a[n][j];
        for(i=n-1; i&gt;=1; i--)
            for(j=1; j&lt;=i; j++)
                d[i][j]=a[i][j]+(d[i+1][j]&gt;d[i+1][j+1]?d[i+1][j]:d[i+1][j+1]);
    }
    int fnMemorySearch(int i,int j)
    //记忆化搜索实现过程
    {
        if(d[i][j]&gt;=0) return d[i][j];
        if(i==n) return(d[i][j]=a[i][j]);
        if(fnMemorySearch(i+1,j)&gt;fnMemorySearch(i+1,j+1))
            return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j)));
        else
            return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j+1)));
    }


    3硬币问题

    问题描写叙述:

        有n种硬币,面值分别为V1,V2,…,Vn元,每种有无限多。

    给定非负整数S。能够选用多少硬币,使得面值之和恰好为S元,输出硬币数目的最小值和最大值。(1<=n<=100,0<=S<=10000,1<=Vi<=S)

    问题解析:

        首先证明该问题问题具有最优子结构。如果组合成S元钱有最优解。并且最优解中使用了面值Vi的硬币。同一时候最优解使用了k个硬币。那么,这个最优解包括了对于组合成S-Vi元钱的最优解。

    显然,S-Vi元钱的硬币中使用了k-1个硬币。如果S-Vi元钱另一个解使用了比k-1少的硬币。那么使用这个解能够为找S元钱产生小于k个硬币的解。

    与如果矛盾。

        另外。对于有些情况下,贪心算法可能无法产生最优解。

    比方硬币面值分别为1、10、25。

    组成30元钱。最优解是3*10,而贪心的情况下产生的解是1*5+25。

        对于贪心算法,有一个结论:如果可换的硬币单位是c的幂。也就是c^0、c^1、…、 c^k,当中整数c>1,k>=1。在这样的情况下贪心算法能够产生最优解。

    上面已经证明该问题具有最优子结构,因此能够用动态规划求解该硬币问题。

    ====>>>:

    设min[j]为组合成j元钱所需的最少的硬币数。max[j]为组合成j元钱所需的最多的硬币数。

        从而有,对于最小组合过程。我们尽可能使用大面值的硬币(不是必定,否则成为贪心算法)。其满足以下的递推公式:

    当j=0时,min[0] = 0。//即组合成0元钱的所需硬币数为0。显而易见。

    当j>0时,假设j > Vk且min[j] < 1 + min[j-Vk]。则有min[j] = 1 + min[j-Vk]。对于这一步。其思想是尽可能通过大面值硬币来降低所需硬币数。

        而对于最大组合过程。我们则是尽量使用小面值的硬币(此过程。同贪心算法一样)。其满足以下的递推公式:

    当j = 0时,max[0] = 0。//显而易见。

    当j > 0时。假设j > Vk且max[j] > 1 + max[j - Vk],则有max[j] = 1 + max[j-Vk];

    如此,我们对整个面值构成过程进行了简单的处理,得到了不同面值和情况下所需的硬币数。

        如今,举例来说明此过程:

        就上面所提及的用1、10、25面值硬币来组成30元钱的过程,我们进行相关说明:

        首先,min[0] = max[0] = 0。同一时候初始化min[i] = INF,max[i] = -INF,i!=0。

        然后。我们依据上面的两个递推公式。能够得到min[]和max[]的终于数据。

        其数据终于为:

        min[] = {0,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,2,3,4,5,6,1,2,3,4,5,3};

        max[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,…,28,19,30};

        于是依据min[]max[],我们便能够得到所需硬币数。并通过print_ans函数打印详细组合。

    代码实现:

    #include <stdio.h>
    
    #include <stdlib.h>
    
    #define INF 100000000
    #define MAXNUM 10000
    #define MONEYKIND 100
    
    int n,S;
    int V[MONEYKIND];
    int min[MAXNUM],max[MAXNUM];
    
    void dp(int*,int*);
    //递推方法函数声明
    void print_ans(int*,int);
    //输出函数声明
    
    int main()
    {
        int i;
        printf("输入硬币的种数n(1-100):\n");
        scanf("%d",&amp;n);
        printf("输入要组合的钱数S(0-10000):\n");
        scanf("%d",&amp;S);
        printf("输入硬币种类:\n");
        for(i=1; i&lt;=n; i++)
        {
            scanf("%d",&amp;V[i]);
        }
        dp(min,max);
        printf("最小组合方案:\n");
        print_ans(min,S);
        printf("\n");
        printf("最大组合方案:\n");
        print_ans(max,S);
    
        return 0;
    }
    
    void dp(int *min,int *max)
    //递推过程实现
    {
        int i,j;
        min[0] = max[0] = 0;
        for(i=1; i&lt;=S; i++)//初始化数组
        {
            min[i]=INF;
            max[i]=-INF;
        }
        for(i=1; i&lt;=S; i++)
            for(j=1; j&lt;=n; j++)
                if(i&gt;=V[j])
                {
                    if(min[i-V[j]]+1&lt;min[i]){
                        min[i]=min[i-V[j]]+1;//最小组合过程
                        //printf("%d\n",min[i]);
                    }
                    if(max[i-V[j]]+1&gt;max[i])
                        max[i]=max[i-V[j]]+1;//最大组合过程
                }
    }
    
    void print_ans(int *d,int S)
    //输出函数实现
    {
        int i;
        for(i=1; i&lt;=n; i++)
            if(S&gt;=V[i]&amp;&amp;d[S]==d[S-V[i]]+1)
            {
                printf("%d ",V[i]);
                print_ans(d,S-V[i]);
                break;
            }
    }


       
    对于上面的代码,还须要说明的是print_ans函数的实现过程:

        递归地打印出组合中的硬币(面值由小到大),每次递归时降低已打印出的硬币面值。

    讨论:

    贪心算法的适用性(仅指最小组合)

        对于贪心算法,有一个结论:如果可换的硬币单位是c的幂。也就是c^0、c^1、…、 c^k,当中整数c>1,k>=1。在这样的情况下贪心算法能够产生最优解。

        贪心算法的过程:对硬币面值进行升序排序。先取最大面值(排序序列最后一个元素)进行极大匹配(除法),然后对余数进行类上操作。

    因此,在这里。注意贪心算法与动态规划的差别:

        动态规划和贪心算法都是一种递推算法;

        均由局部最优解来推导全局最优解。

        不同点:

    贪心算法:

        (1)、贪心算法中。作出的每步贪心决策都无法改变,由于贪心策略是由上一步的最优解推导下一步的最优解,而上一部之前的最优解则不作保留。

        (2)、由(1)中的介绍,能够知道贪心法正确的条件是:每一步的最优解一定包括上一步的最优解

    动态规划算法:

        (1)、全局最优解中一定包括某个局部最优解,但不一定包括前一个局部最优解,因此须要记录之前的全部最优解;

        (2)、动态规划的关键是状态转移方程。即怎样由以求出的局部最优解来推导全局最优解。

        (3)、边界条件:即最简单的,能够直接得出的局部最优解。

    展开全文
  •  和分治一样,动态规划(dynamicprogramming)是通过组合子问题而解决整个问题的解。  分治是将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解。动态规划适用于子问题不独立的情况,也...
    关键字:子问题不独立、子问题结果存储、空间换时间

    一、基本概念:
            和分治法一样,动态规划(dynamicprogramming)是通过组合子问题而解决整个问题的解。
            分治法是将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解。动态规划适用于子问题不独立的情况,也就是各子问题包含公共的子问题。此时,分治法会做许多不必要的工作,即重复地求解公共的子问题。动态规划算法对每个子问题只求解一次,将其结果保存起来,从而避免每次遇到各个子问题时重新计算答案。

    二、算法基本思路:
          两种方法:
        1.自顶向下(又称记忆化搜索、备忘录):基本上对应着递归函数实现,从大范围开始计算,要注意不断保存中间结果,避免重复计算
        2.自底向上(递推):从小范围递推计算到大范围
          动态规划的重点:递归方程+边界条件

    三、算法特点:
        1. 动态规划任何一个i+1阶段都仅仅依赖i阶段做出的选择,而与i之前的选择无关。但是动态规划不仅求出了当前状态的最优值,而且同时求出了到中间状态的最优值;
        2. 缺点:空间需求大;

    四、适用问题
          适合适用动态规划的问题必须满足最优化原理、无后效性和重叠性。

          1.最优化原理(最优子结构性质)一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

          2.无后效性  将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。

          3.子问题的重叠性  动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法。
     
    五、算法的实现框架
    for(j=1; j<=m; j=j+1) // 第一个阶段
       xn[j] = 初始值;
     
     for(i=n-1; i>=1; i=i-1)// 其他n-1个阶段
       for(j=1; j>=f(i); j=j+1)//f(i)与i有关的表达式
         xi[j]=j=max(或min){g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};
     
    t = g(x1[j1:j2]); // 由子问题的最优解求解整个问题的最优解的方案
     
    print(x1[j1]);
     
    for(i=2; i<=n-1; i=i+1)
    {  
         t = t-xi-1[ji];
     
         for(j=1; j>=f(i); j=j+1)
            if(t=xi[ji])
                 break;
    }
      
    六、实例分析

        动态规划算法可以求解很多问题,比如矩阵乘法、最长公共子序列、构造最优二叉查找树等,现就著名的最长公共子序列问题,采用动态规划法分析之。

        相关定义

          子序列:若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij.
          公共子序列:给定2个序列XY,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列XY公共子序列.
          最长公共子序列:给定2个序列X={x1,x2,,xm}Y={y1,y2,,yn},找出XY的最长公共子序列.
            如:序列ABCDEF和ADFGH的最长公共子序列为ADF

          注意:最长公共子串(Longest Common Substirng)和最长公共子序列(Longest Common Subsequence,简称LCS)的区别为是最长公共子串的串是一个连续的部分,而最长公共子序列则是从不改变序列的顺序,而从序列中去掉任意的元素而获得新的序列;通俗的说就是子串中字符的位置必须是连续的而子序列则可以不必连续。

       问题描述给定2个序列X={A,B,C,B,D,A,B}Y={B,D,C,A,B,A},找出XY的最长公共子序列.(转载1)(转载2)

       算法分析思路

         1.分析最优子结构性质:

              设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ,则

           (1)若xm=yn,则zk=xm=yn,且z1,z2,…, zk-1是否为x1,x2,…,xm-1和y1,y2,…,yn-1的最长公共子序列.
           (2)若xm≠yn且zk≠xm,则Z是x1,x2,…,xm-1和Y的最长公共子序列.
           (3)若xm≠yn且zk≠yn,则Z是X和y1,y2,…,yn-1的最长公共子序列.

          由此可见,2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列.因此,最长公共子序列问题具有最优子结构性质.当问题具有最优子结构性质和子问题重叠性质时就可以用动态规划算法解决该问题.

         2.由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系.用c[i][j]记录序列和的最长公共子序列的长度.其中,Xi={x1,x2,…,xi},Yj={y1,y2,…,yj}.当i=0或j=0时,空序列是Xi和Yj的最长公共子序列.故此时C[i][j]=0.其它情况下,由最优子结构性质可建立递归关系如下:

       

          回溯输出最长公共子序列过程:

           flow


       算法分析由于每次调用至少向上或向左(或向上向左同时)移动一步,故最多调用(m + n)次就会遇到i = 0或j = 0的情况,此时开始返回。返回时与递归调用时方向相反,步数相同,故算法时间复杂度为Θ(m + n)

       算法实现

    //LCS  最长公共子序列
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX 100
    
    void LCS(char *x, char *y,int x_len, int y_len, int common_len[][MAX], int b[][MAX])
    {
        //common_len[i][j]存储的是x的第i位与有的第j位的公共子序列的长度
        //b[i][j] 记录获得common_len[i][j]的路径:分别为0 -1 1,便于回溯输出公共子串
    
        int i,j;
        
        for (i = 0; i < x_len; i++)
            common_len[i][0] = 0;
        for (j = 0; j < y_len; j++)
            common_len[0][j] =0;
    
        for (i = 1; i <= x_len; i++)
        {
            for (j = 1; j <= y_len; j++)
            {
                if (x[i-1] == y[j-1])  //从零开始存储,所以第i位为x[i-1]
                {
                    common_len[i][j] = common_len[i-1][j-1] + 1;
                    b[i][j] = 0;
                }
                else if (common_len[i-1][j] >= common_len[i][j-1])
                {
                    common_len[i][j] = common_len[i-1][j];
                    b[i][j] = -1;
                }
                else
                {
                    common_len[i][j] = common_len[i][j-1];
                    b[i][j] = 1;
                }
            }
        }
    }
    
    void backtrack(int i, int j,int b[][MAX], char *x)
    {
        if (0 == i || 0 == j) 
            return;
        else if (0 == b[i][j])
        {
            backtrack(i-1,j-1,b,x);
            printf("%c",x[i-1]);
        }
        else if(-1 == b[i][j])
        {
            backtrack(i-1,j,b,x);
        }
        else
        {
            backtrack(i,j-1,b,x);
        }
    }
    
    int main()
    {
        int x_len,y_len;
        char x[MAX] = "ABCBDAB";
        char y[MAX] = "BDCABA";
        int common_len[MAX][MAX];
        int b[MAX][MAX];
    
        x_len = strlen(x);
        y_len = strlen(y);
    
        LCS(x,y,x_len,y_len,common_len,b);
        backtrack(x_len,y_len,b,x);
        
        printf("\n");
        
        
        return 0;
    }
    


    转载请注明出处:http://blog.csdn.net/daijin888888/article/details/53115323
    展开全文
  • 五大算法分治算法动态规划算法回溯分支限界贪心算法 分治算法 1、基本概念 在计算机科学中,分治是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,...

    分治算法

    1、基本概念
    在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……

    任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。

    2、基本思想及策略
    (1)分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
    (2)分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

    如果原问题可分割成k个子问题,1<k≤n,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。

    3、分治法适用的情况
    分治法所能解决的问题一般具有以下几个特征:

    • (1)该问题的规模缩小到一定的程度就可以容易地解决
    • (2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
    • (3) 利用该问题分解出的子问题的解可以合并为该问题的解;
    • (4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

    第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;

    第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;

    第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。

    第四条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

    4、分治法的基本步骤
    分治法在每一层递归上都有三个步骤:

    step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
    step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
    step3 合并:将各个子问题的解合并为原问题的解。

    它的一般的算法设计模式如下:

    Divide-and-Conquer§
    1. if |P|≤n0
    2. then return(ADHOC§)
    3. 将P分解为较小的子问题 P1 ,P2 ,…,Pk
    4. for i←1 to k
    5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
    6. T ← MERGE(y1,y2,…,yk) △ 合并子问题
    7. return(T)

    其中|P|表示问题P的规模;n0为一阈值,表示当问题P的规模不超过n0时,问题已容易直接解出,不必再继续分解。ADHOC§是该分治法中的基本子算法,用于直接解小规模的问题P。因此,当P的规模不超过n0时直接用算法ADHOC§求解。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法,用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。

    5、分治法的复杂性分析
    一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有: T(n)= k T(n/m)+f(n)

    通过迭代法求得方程的解:递归方程及其解只给出n等于m的方幂时T(n)的值,但是如果认为T(n)足够平滑,那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的,从而当 mi≤n<mi+1时,T(mi)≤T(n)<T(mi+1)。

    6、可使用分治法求解的一些经典问题

    • (1)二分搜索
    • (2)大整数乘法
    • (3)Strassen矩阵乘法
    • (4)棋盘覆盖
    • (5)合并排序
    • (6)快速排序
    • (7)线性时间选择
    • (8)最接近点对问题
    • (9)循环赛日程表
    • (10)汉诺塔

    7、依据分治法设计程序时的思维过程

    实际上就是类似于数学归纳法,找到解决本问题的求解方程公式,然后根据方程公式设计递归程序。

    • 1、一定是先找到最小问题规模时的求解方法
    • 2、然后考虑随着问题规模增大时的求解方法
    • 3、找到求解的递归函数式后(各种规模或因子),设计递归程序即可。

    动态规划算法

    1、基本概念
    动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。

    2、基本思想与策略
    基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。
    由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。

    与分治法最大的差别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)。

    3、适用的情况
    能采用动态规划求解的问题的一般要具有3个性质:

    • (1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
    • (2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
    • (3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)

    四、求解的基本步骤

    动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。

    初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

    (1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。

    (2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。

    (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

    (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。

    一般,只要解决问题的阶段、状态和状态转移决策确定了,就可以写出状态转移方程(包括边界条件)。

    实际应用中可以按以下几个简化的步骤进行设计:

    • (1)分析最优解的性质,并刻画其结构特征。
    • (2)递归的定义最优解。
    • (3)以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值
    • (4)根据计算最优值时得到的信息,构造问题的最优解

    5、算法实现的说明

    动态规划的主要难点在于理论上的设计,也就是上面4个步骤的确定,一旦设计完成,实现部分就会非常简单。
    使用动态规划求解问题,最重要的就是确定动态规划三要素:
    (1)问题的阶段 (2)每个阶段的状态
    (3)从前一个阶段转化到后一个阶段之间的递推关系。

    递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处。

    确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述,最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。


    回溯法

    1、概念
    回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。

    回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

    许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。

    2、基本思想
    在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。

    若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。

    而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。

    3、用回溯法解题的一般步骤:
    (1)针对所给问题,确定问题的解空间:
    首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。
    (2)确定结点的扩展搜索规则
    (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。


    分支限界法

    1、基本描述
    类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。

    (1)分支搜索算法
    所谓“分支”就是采用广度优先的策略,依次搜索E-结点的所有分支,也就是所有相邻结点,抛弃不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,继续搜索。

    选择下一个E-结点的方式不同,则会有几种不同的分支搜索方式。

    1)FIFO搜索

    2)LIFO搜索

    3)优先队列式搜索

    (2)分支限界搜索算法
    2、分支限界法的一般过程
    由于求解目标不同,导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。

    分支限界法的搜索策略是:在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解。

    分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树,常见的有子集树和排列树。在搜索问题的解空间树时,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。

    3、回溯法和分支限界法的一些区别
    有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决,但是另外一些则不然。也许我们需要具体一些的分析——到底何时使用分支限界而何时使用回溯呢?

    回溯法和分支限界法的一些区别:

    方法对解空间树的搜索方式

    存储结点的常用数据结构

    结点存储特性常用应用

    回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解

    分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解


    贪心算法

    1、基本概念:

    所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
    贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。
    所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

    2、贪心算法的基本思路:

    • 建立数学模型来描述问题。
    • 把求解的问题分成若干个子问题。
    • 对每一子问题求解,得到子问题的局部最优解。
    • 把子问题的解局部最优解合成原来解问题的一个解。

    3、贪心算法适用的问题
    贪心策略适用的前提是:局部最优策略能导致产生全局最优解。
    实际上,贪心算法适用的情况很少。一般,对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可做出判断。

    4、贪心算法的实现框架

    从问题的某一初始解出发;
    while (能朝给定总目标前进一步)
    {
    利用可行的决策,求出可行解的一个解元素;
    }
    由所有解元素组合成问题的一个可行解;

    5、贪心策略的选择
    因为用贪心算法只能通过解局部最优解的策略来达到全局最优解,因此,一定要注意判断问题是否适合采用贪心算法策略,找到的解是否一定是问题的最优解。


    展开全文
  • 分治基本思想: 将问题分解成多个子问题,并允许不断分解,使规模越来越小,最终可用已知的方法求解足够小的问题。  使用要求: (1) 问题能够按照某种...问题的最优子结构性质是该问题可用动态规划算法或贪心
  • 基本思想与分治类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有
  • 有n节台阶,一次能走1步或者2步,共有多少种走。 思路 一次只能走1步或者2步。且先走1和先走2是两种不同的走。 我们可以发现:不管走1步还是走2步,后面的问题是一样的:走1步还是走2步?又有多少种走? ...
  • 和分治法如何区分:动态对话法基本都会用到一种查表的方式。它会把每一次动态的数据都存到表中。比如在递归实现中,它会存好数组a[2] a[3] a[4]...的值 ...
  • 算法设计与分析之动态规划法

    千次阅读 2020-12-02 14:20:05
    动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),可以人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。
  • 动态规划作为一种工具在应用数学中的价值被大家认同以后,在计算机科学界,动态规划法成为一种通用的算法设计技术来求解多阶段决策最优化问题。 概述 最优化问题 什么是最优化问题 最优化问题:有n个...
  • 0/1背包问题的动态规划法求解,前人之述备矣,这里所做的工作,不过是自己根据理解实现了一遍,主要目的还是锻炼思维和编程能力,同时,也是为了增进对动态规划法机制的理解和掌握。   值得提及的一个问题是,...
  •  优先队列式分枝限界的主要特点是将活结点表组组成一个优先队 列,并 选取优先级最高的活结点成为当前扩展结点。步骤如下: ① 计算起始结点(根结点)的优先级并加入优先队列(与特定问题相关的信息的函数值决定...
  • 算法设计策略-动态规划法 动态规划法 动态规划算法是另一种求解最优化问题的重要算法设计策略。对于一个问题,如果能从较小规模的子问题的最优解求得较大规模同类子问题的最优解,最终得到给定问题的最优解,这...
  • 最近看到使用动态规划法求解矩阵连乘最小乘法次数,网上的一些copy主,只是copy,也不改错。本文已将一些不正确的错误更改。 问题描述: 给定n个矩阵:A1,A2,…,An,其中Ai与Ai+1是可乘的,i=1,2…,n-1。确定计算矩阵...
  • 题目:动态规划特点及其应用 目录 §1动态规划的本质 §1.1多阶段决策问题 §1.2阶段与状态 §1.3决策和策略 §1.4最优化原理与无后效性 §1.5最优指标函数和规划方程 §2动态规划的设计与实现 §2.1动态规划的...
  • 一、0-1背包的题目描述 有n种物品,每种只有1个。第i种物品的体积为Vi,重量为Wi。选一些物品装到一个容量为C的背包中,使得背包内物品在...如果你上网搜索0-1背包的解法,你会发现它其实有四种基本解法,分别是...
  • 动态规划解题

    千次阅读 2013-01-29 18:06:02
    在学习动态规划法之前,我们先来了解动态规划的几个概念 1、 阶段:把问题分成几个相互联系的有顺序的几个环节,这些环节即称为阶段。 2、 状态:某一阶段的出发位置称为状态。 3、 决策:从某阶段的一个状态...
  • 动态规划特点及其应用

    千次阅读 2013-04-25 14:09:23
    动态规划特点及其应用   目 录 (点击进入) 【关键词】 【摘要】 【正文】 §1动态规划的本质 §1.1多阶段决策问题 §1.2阶段与状态 §1.3决策和策略 §1.4最优化原理与无后效性 §...
  • 动态规划

    2019-08-12 18:02:53
    文章目录重温动态规划~什么是动态规划如何设计一个动态规划算法动态规划实例问题一:钢条切割问题带备忘的自顶向下带备忘的自顶向下实现钢条切割问题动态规划实例问题二:矩阵连乘问题什么时候该用动态规划来做...
  • 首先,本博客为原创作品,欢迎指导,随意转载,如果可以请转载时说明出处,附上...动态规划算法的基本思想与分治类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题...
  • 五大常用算法:分治动态规划、贪心、回溯、分支界限。。。
  • 动态规划和回溯的异同

    千次阅读 2017-09-18 20:00:52
    动态规划典型题目有:最长公共子序列问题,还有滑雪路径问题(滑雪路径) 这些都是我做过的几道题,对两种算法有点感悟,所以写出自己的第一个博客。(算是转载吧,自己写一点分析而已) 二:以老鼠走迷宫问题和...
  • 原作者:张辰 动态规划是信息学竞赛中的常见算法,本文的主要内容就是分析它的特点。 文章的第一部分首先探究了动态规划的本质,因为动态规划特点是由它的本质所决定的。第二部分从动态规划的设计和实现这两个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,741
精华内容 12,696
关键字:

动态规划法的基本特点