第3章 动态规划 算法设计与分析电子教案_图文

  • 阅读:6884

    第3章 动态规划
    1

    ? 动态规划算法与分治法类似,其基本思想也是将待求 解问题分解成若干个子问题

    T(n)

    =n

    T(n/2)

    T(n/2)

    T(n/2)

    T(n/2)
    2

    算法总体思想
    ? 动态规划算法与分治法类似,其基本思想也是将待求 解问题分解成若干个子问题

    T(n)

    =n

    T(n/2)

    T(n/2)

    T(n/2)

    T(n/2)
    3

    动态规划基本步骤
    ? 找出最优解的性质,并刻划其结构特征。 ? 递归地定义最优值。 ? 以自底向上的方式计算出最优值。 ? 根据计算最优值时得到的信息,构造最优
    解。
    6

    完全加括号的矩阵连乘积
    完全加括号的矩阵连乘积可递归地定义为: (1)单个矩阵是完全加括号的;
    (2)矩阵连乘积 A是完全加括号的,则 A可 表示为2个完全加括号的矩阵连乘积 B和 C 的乘积并加括号,即 A(BC)
    设有四个矩阵 A,B,C,,它D们的维数分别是:
    A5010B1040C4030D305
    总共有五中完全加括号的方式
    (A((BC)D)) (A(B(CD))) ((AB)(CD)) ((A( B)C)D) ((A(BC))D)
    16000, 10500, 36000, 87500, 34500 7

    矩阵连乘问题
    给定n个矩阵 {A1,A2,.,..A,其n}中 与 是A i 可乘Ai 1
    的, i1,2,..n 。.考,1察这n个矩阵的连乘积
    A1A2...An
    由于矩阵乘法满足结合律,所以计算矩阵的连乘可以 有许多不同的计算次序。这种计算次序可以用加括号 的方式来确定。
    若一个矩阵连乘积的计算次序完全确定,也就是说该 连乘积已完全加括号,则可以依此次序反复调用2个矩 阵相乘的标准算法计算出矩阵连乘积
    8

    矩阵连乘问题

    给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的, i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序,使得 依此次序计算矩阵连乘积需要的数乘次数最少。
    穷举法:列举出所有可能的计算次序,并计算出每一种计 算次序相应需要的数乘次数,从中找出一种数乘次数最少的 计算次序。

    算法复杂度分析:

    对于n个矩阵的连乘积,设其不同的计算次序为P(n)。

    由于每种加括号方式都可以分解为两个子矩阵的加括号问题:

    (A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下:

    P (n ) n 1P (k)1 P (n k) k 1

    n 1 P (n ) (4 n/n 3 /2) n 1

    9

    矩阵连乘问题
    穷举法 动态规划
    将矩阵连乘积 AiAi1...Aj 简记为A[i:j] ,这里i≤j
    考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开,i≤k<j,则其相应完全
    加括号方式为 (A iA i 1..A k .)A (k 1A k2..A .j)
    计算量:A[i:k]的计算量加上A[k+1:j]的计算量,再加上 A[i:k]和A[k+1:j]相乘的计算量
    10

    分析最优解的结构
    ? 特征:计算A[i:j]的最优次序所包含的计算矩 阵子链 A[i:k]和A[k+1:j]的次序也是最优的。
    ? 矩阵连乘计算次序问题的最优解包含着其子问 题的最优解。这种性质称为最优子结构性质。 问题的最优子结构性质是该问题可用动态规划 算法求解的显著特征。
    11

    建立递归关系
    设计算A[i:j],1≤i≤j≤n,所需要的最少数乘次数 m[i,j],则原问题的最优值为m[1,n]
    当i=j时,A[i:j]=Ai,因此,m[i,i]=0,i=1,2,…,n 当i<j时,
    m [ i,j] m [ i,k ] m [ k 1 ,j] p i 1 p k p j
    这里 A i 的维数为 pi1 pi
    可以递归地定义m[i,j]为:
    m [i,j] m i k j{ m i[i,n k] m [k 0 1 ,j]p i 1p kp j}ii jj
    k 的位置只有 j i 种可能
    12

    计算最优值
    对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。 因此,不同子问题的个数最多只有
    n2n (n2)
    由此可见,在递归计算时,许多子问题被重复计算多 次。这也是该问题可用动态规划算法求解的又一显著 特征。
    用动态规划算法解此问题,可依据其递归式以自底向 上的方式进行计算。在计算过程中,保存已解决的子 问题答案。每个子问题只计算一次,而在后面需要时 只要简单查一下,从而避免大量的重复计算,最终得 到多项式时间的算法
    13

    用动态规划法求最优解

    public static void matrixChain(int [] p, int [][] m, int [][] s)

    {

    A1 A2 A3 A4 A5 A6

    int n=p.length-1;

    3035 3515 155 510 1020 2025

    for (int i = 1; i <= n; i++) m[i][i] = 0;

    for (int r = 2; r <= n; r++)

    m [2 ]2 []m [3 ]5 []p 1p2p50253 0 5 0 1 5 2 0 130 m [2 ]5 []m m i[n 2 ]3 []m [4 ]5 []p 1p3p5261 20 53 0 5 0 52 0712

    for (int i = 1; i <= n - r+1; i++) {

    m [2 ]4 []m [5 ]5 []p 1p4p5430 73 5 5 1 0 2 0 113

    int j=i+r-1;

    算法复杂度分析:

    m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; 算法matrixChain的主要计算量取决于算法中对r,

    s[i][j] = i; for (int k = i+1; k < j; k++) {

    i和k的3重循环。循环体内的计算量为O(1),而3重 循环的总次数为O(n3)。因此算法的计算时间上界 为O(n3)。算法所占用的空间显然为O(n2)。

    int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];

    if (t < m[i][j]) {

    m[i][j] = t;

    s[i][j] = k;}

    }

    }

    14

    }

    动态规划算法的基本要素
    一、最优子结构
    ?矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这 种性质称为最优子结构性质。 ?在分析问题的最优子结构性质时,所用的方法具有普遍性:首 先假设由问题的最优解导出的子问题的解不是最优的,然后再 设法说明在这个假设下可构造出比原问题最优解更好的解,从 而导致矛盾。 ?利用问题的最优子结构性质,以自底向上的方式递归地从子问 题的最优解逐步构造出整个问题的最优解。最优子结构是问题 能用动态规划算法求解的前提。
    注意:同一个问题可以有多种方式刻划它的最优子结构,有些 表示方法的求解速度更快(空间占用小,问题的维度低)
    15

    二、重叠子问题
    ?递归算法求解问题时,每次产生的子问题并不总是新问题,有 些子问题被反复计算多次。这种性质称为子问题的重叠性质。 ?动态规划算法,对每一个子问题只解一次,而后将其解保存在 一个表格中,当再次需要解此子问题时,只是简单地用常数时 间查看一下结果。 ?通常不同的子问题个数随问题的大小呈多项式增长。因此用动 态规划算法只需要多项式时间,从而获得较高的解题效率。
    16

    三、备忘录方法

    ?备忘录方法的控制结构与直接递归方法的控制结构相同,区别

    在于备忘录方法为每个解过的子问题建立了备忘录以备需要时

    查看,避免了相同子问题的重复求解。

    m0

    private static int lookupChain(int i, int j)

    {

    if (m[i][j] > 0) return m[i][j];

    if (i == j) return 0;

    int u = lookupChain(i+1,j) + p[i-1]*p[i]*p[j];

    s[i][j] = i;

    for (int k = i+1; k < j; k++) {

    int t = lookupChain(i,k) + lookupChain(k+1,j) + p[i-1]*p[k]*p[j];

    if (t < u) {

    u = t; s[i][j] = k;}

    }

    m[i][j] = u;

    return u;

    17

    }

    最长公共子序列
    ? 若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk}, 是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik} 使D,得B对}是于序所列有Xj==1{A,2,,…B,,k有C:,zBj=,xiDj。,例A如,,B}序的列子Z序=列{B,,C, 相应的递增下标序列为{2,3,5,7}。
    ? 给定2个序列X和Y,当另一序列Z既是X的子序列又是Y 的子序列时,称Z是序列X和Y的公共子序列。
    ? 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X 和Y的最长公共子序列。
    18

    最长公共子序列的结构
    设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为 Z={z1,z2,…,zk} ,则 (1)若xm=yn,则zk=xm=yn,且zk-1是xm-1和yn-1的最长公共子序列。 (2)若xm≠yn且zk≠xm,则Z是xm-1和Y的最长公共子序列。 (3)若xm≠yn且zk≠yn,则Z是X和yn-1的最长公共子序列。
    由此可见,2个序列的最长公共子序列包含了这2个序列的前缀 的最长公共子序列。因此,最长公共子序列问题具有最优子结 构性质。
    19

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



    0

    i0,j0

    c[i][j] c[i1][j1]1

    i,j0;xi yj

    mac[ix ][j{1]c,[i1][j]}i,j0;xi yj

    20

    计算最优值
    由于在所考虑的子问题空间中,总共有θ(mn)个不同的子问题, 因此,用动态规划算法自底向上地计算最优值能提高算法的效率。

    Algorithm lcsLength(x,y,b)

    1: mx.length-1;

    2: ny.length-1;

    3: c[i][0]=0; c[0][i]=0;

    4: for (int i = 1; i <= m; i++)

    5: for (int j = 1; j <= n; j++)

    6: if (x[i]==y[j])

    7:

    c[i][j]=c[i-1][j-1]+1;

    8:

    b[i][j]=1;

    9: else if (c[i-1][j]>=c[i][j-1])

    10:

    c[i][j]=c[i-1][j];

    11:

    b[i][j]=2;

    12: else

    13:

    c[i][j]=c[i][j-1];

    14:

    b[i][j]=3;

    构造最长公共子序列 Algorithm lcs(int i,int j,char [] x,int [][] b)
    { if (i ==0 || j==0) return; if (b[i][j]== 1){ lcs(i-1,j-1,x,b); System.out.print(x[i]); } else if (b[i][j]== 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b);
    }
    21

    算法的改进
    ?在算法lcsLength和lcs中,可进一步将数组b省去。 事实上,数组元素c[i][j]的值仅由c[i-1][j-1],c[i-1][j]和 c[i][j-1]这3个数组元素的值所确定。对于给定的数组 元素c[i][j],可以不借助于数组b而仅借助于c本身在时 间内确定c[i][j]的值是由c[i-1][j-1],c[i-1][j]和c[i][j-1]中 哪一个值所确定的。 ?如果只需要计算最长公共子序列的长度,则算法的空 间需求可大大减少。事实上,在计算c[i][j]时,只用到 数组c的第i行和第i-1行。因此,用2行的数组空间就可 以计算出最长公共子序列的长度。进一步的分析还可 将空间需求减至O(min(m,n))。
    22

    凸多边形最优三角剖分
    ?用多边形顶点的逆时针序列表示凸多边形,即P={v0,v1,…,vn-1} 表示具有n条边的凸多边形。 ?若vi与vj是多边形上不相邻的2个顶点,则线段vivj称为多边形的 一条弦。弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。 ?多边形的三角剖分是将多边形分割成互不相交的三角形的弦的 集合T。 ?给定凸多边形P,以及定义在由多边形的边和弦组成的三角形 上的权函数w。要求确定该凸多边形的三角剖分,使得即该三角 剖分中诸三角形上权之和为最小。
    23

    三角剖分的结构及其相关问题
    ?一个表达式的完全加括号方式相应于一棵完全二叉树,称 为表达式的语法树。例如,完全加括号的矩阵连乘积 ((A1(A2A3))(A4(A5A6)))所相应的语法树如图 (a)所示。 ?凸多边形{v0,v1,…vn-1}的三角剖分也可以用语法树表示。例 如,图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树 表示。 ?矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边 vi-1vi。三角剖分中的一条弦vivj,i<j,对应于矩阵连乘积 A[i+1:j]。
    24

    最优子结构性质
    ?凸多边形的最优三角剖分问题有最优子结构性 质。 ?事实上,若凸(n+1)边形P={v0,v1,…,vn-1}的最 优三角剖分T包含三角形v0vkvn,1≤k≤n-1,则T 的权为3个部分权的和:三角形v0vkvn的权, 子多边形{v0,v1,…,vk}和{vk,vk+1,…,vn}的权之和。 可以断言,由T所确定的这2个子多边形的三角 剖分也是最优的。因为若有{v0,v1,…,vk}或 {vk,vk+1,…,vn}的更小权的三角剖分将导致T不是 最优三角剖分的矛盾。
    25

    最优三角剖分的递归结构
    ?定义t[i][j],1≤i<j≤n为凸子多边形{vi-1,vi,…,vj}的最优三角剖分 所对应的权函数值,即其最优值。为方便起见,设退化的多边 形{vi-1,vi}具有权值0。据此定义,要计算的凸(n+1)边形P的最 优权值为t[1][n]。 ?t[i][j]的值可以利用最优子结构性质递归地计算。当j-i≥1时,凸 子多边形至少有3个顶点。由最优子结构性质,t[i][j]的值应为 t[i][k]的值加上t[k+1][j]的值,再加上三角形vi-1vkvj的权值,其中 i≤k≤j-1。由于在计算时还不知道k的确切位置,而k的所有可能 位置只有j-i个,因此可以在这j-i个位置中选出使t[i][j]值达到最小 的位置。由此,t[i][j]可递归地定义为:
    t[i]j[] m i k j{ t[i]n k [] t[k 0 1 ]j[] w (v i 1 vkvj)} ii jj
    26

    多边形游戏
    多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点 构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一 个运算符“+”或“*”。所有边依次用整数从1到n编号。
    游戏第1步,将一条边删除。 随后n-1步按以下方式操作: (1)选择一条边E以及由E连接着的2个顶点V1和V2; (2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。 将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新 顶点。 最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶 点上的整数值。 问题:对于给定的多边形,计算最高得分。
    27

    最优子结构性质
    ?在所给多边形中,从顶点i(1≤i≤n)开始,长度为j(链中有j个顶点) 的顺时针链p(i,j) 可表示为v[i],op[i+1],…,v[i+j-1]。 ?如果这条链的最后一次合并运算在op[i+s]处发生(1≤s≤j-1),则 可在op[i+s]处将链分割为2个子链p(i,s)和p(i+s,j-s)。 ?设m1是对子链p(i,s)的任意一种合并方式得到的值,而a和b 分别是在所有可能的合并中得到的最小值和最大值。m2是 p(i+s,j-s)的任意一种合并方式得到的值,而c和d分别是在所 有可能的合并中得到的最小值和最大值。依此定义有a≤m1≤b, c≤m2≤d (1)当op[i+s]='+'时,显然有a+c≤m≤b+d (2)当op[i+s]='*'时,有min{ac,ad,bc,bd}≤m≤max{ac,ad, bc,bd} ?换句话说,主链的最大值和最小值可由子链的最大值和最小值 得到。
    28

    图像压缩
    图像的变位压缩存储格式将所给的象素点序列 {p1,p2,…,pn},0≤pi≤255分割成m个连续段S1,S2,…,Sm。第i 个象素段Si中(1≤i≤m),有l[i]个象素,且该段中每个象素都只用
    i 1
    b[i]位表示。设 t[i] l[k则] 第i个象素段Si为 k 1
    设 hi log t[i]1m kt[i]al[ix ]pk1,则hib[i]8。因此需要用3位表示b[i], 如果限制1l[i]255,则需要用8位表示l[i]。因此,第i个象素 段所需的存储空间为l[i]*b[i]+11位。按此格式存储象素序列
    {p1,p2,…,pn},需要m l[i]*b[i]11m位的存储空间。 i1
    图像压缩问题要求确定象素序列{p1,p2,…,pn}的最优分段, 使得依此分段所需的存储空间最少。每个分段的长度不超过 256位。
    29

    图像压缩
    设l[i],b[i],是{p1,p2,…,pn}的最优分段。显而易见,l[1],b[1] 是{p1,…,pl[1]}的最优分段,且l[i],b[i],是{pl[1]+1,…,pn}的最优分 段。即图像压缩问题满足最优子结构性质。 设s[i],1≤i≤n,是象素序列{p1,…,pn}的最优分段所需的存储位 数。由最优子结构性质易知:
    s [ i]m{ s i[ i n k ] k * b m i a k 1 ,x i) } 1 ( 1 1 k m i,2 i} n 5{ 6

    其中 bmi,aj) x l(o m ig kj{ apkx }1

    算法复杂度分析:

    由于算法compress中对k的循环次数不超这256,故对

    每一个确定的i,可在时间O(1)内完成的计算。因此整

    个算法所需的计算时间为O(n)。

    30

    电路布线
    在一块电路板的上、下2端分别有n个接线柱。根据电路设计, 要求用导线(i,π(i))将上端接线柱与下端接线柱相连,如图所示。 其中π(i)是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上 的第i条连线。对于任何1≤i<j≤n,第i条连线和第j条连线相交的 充分且必要的条件是π(i)>π(j)。 电路布线问题要确定将哪些连线安排在第一层上,使得该层上 有尽可能多的连线。换句话说,该问题要求确定导线集 Nets={(i,π(i)),1≤i≤n}的最大不相交子集。
    31

    电路布线

    记 N ( i ,j ) { t|( t ,( t ) ) N ,t e i ,( t ) t j s } 。N(i,j)的最大不相交子

    集为MNS(i,j)。Size(i,j)=|MNS(i,j)|。

    (1)当i=1时,



    j (1 )

    M(1 N ,j) S N (1 ,j) {1 , ((1 ))}j (1 )

    (22.1)当(j1<i)>π当1(i时i)=。1,时此时,S(ii,(1 z,je ()i) )1 0N(i,jjj。) 故((11在)) 这种情况下,

    (N2()i当,j)=i>N1(时i-1,j),从而Size(i,j)=Size(i-1,j)。
    2.2 tj<≥iπ且(iπS ),(t)( (<i ii , ,ππj) (z ( ii))。) ∈m S e 在M( 这i NS i S种1 a z ,(( j ii 情,i ) j)e x 1 况z 。,j下)则S e { M,对N( ii 任S (1 z 意i,,j)( (-i t) {e ,( πi,1 π() t) ()i1 )} ∈)}是Mj j NN(S( ( i-i i() ) i,j)有

    1,π(i)-1)的最大不相交子集。
    2.3 若 (i,(i) )N(i,j),则对任意(t,π(t)) ∈MNS(i,j)有

    t<i。从而 M(i,N j) S N (i 1 ,j。)因此,Size(i,j)≤Size(i-1,j)。

    另一方面 M(iN 1 ,j)S N (i,j),故又有Size(i,j)≥Size(i-1,j),

    从而Size(i,j)=Size(i-1,j)。

    32

    流水作业调度

    n个作业{1,2,…,n}要在由2台机器M1和M2组成的流水线上 完成加工。每个作业加工的顺序都是先在M1上加工,然后在 M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。 流水作业调度问题要求确定这n个作业的最优加工顺序,使得从
    第一个作业在机器M1上开始加工,到最后一个作业在机器M2上
    加工完成所需的时间最少。

    分析:

    ?直观上,一个最优调度应使机器M1没有空闲时间,且机器

    M2的空闲时间最少。在一般情况下,机器M2上会有机器空闲

    和作业积压2种情况。

    ?设全部作业的集合为N={1,2,…,n}。SN是N的作业子

    集。在一般情况下,机器M1开始加工S中作业时,机器M2还

    在加工其他作业,要等时间t后才可利用。将这种情况下完成

    S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最

    优值为T(N,0)。

    33

    流水作业调度
    设是所给n个流水作业的一个最优调度,它所需的加工时间为 a(1)+T’。其中T’是在机器M2的等待时间为b(1)时,安排作业 (2),…,(n)所需的时间。 记S=N-{(1)},则有T’=T(S,b(1))。 证明:事实上,由T的定义知T’T(S,b(1))。若T’>T(S,b(1)), 设’是作业集S在机器M2的等待时间为b(1)情况下的一个最优 调度。则(1), ’(2),…, ’(n)是N的一个调度,且该调度 所需的时间为a(1)+T(S,b(1))<a(1)+T’。这与是N的最优调度 矛盾。故T’T(S,b(1))。从而T’=T(S,b(1))。这就证明了流水作 业调度问题具有最优子结构的性质。
    由流水作业调度问题的最优子结构性质可知,
    T (N ,0 ) m 1 i n { a ii n T (N { i}b i,)}
    T ( S ,t) m i S { a i iT n ( S { i} b i ,m t a a i,0 } x) {}34

    Johnson不等式
    对递归式的深入分析表明,算法可进一步得到简化。 设是作业集S在机器M2的等待时间为t时的任一最优调度。若 (1)=i, (2)=j。则由动态规划递归式可得: T其(S中,t,)=tiaj i+bTj(S-m {i}a,bxib+i{mamx{at-xat{i,0a}i),0=}ai+aajj,+0}T(S-{i,j},tij)
    bj bi aj max{mtaxai{,0},aj bi} bj bi aj maxt{ai,aj bi,0} bj bi aj ai maxt,{ai aj bi,ai}
    如果作业i和j满足min{bi,aj}≥min{bj,ai},则称作业i和j满 足Johnson不等式。
    35

    流水作业调度的Johnson法则
    ti jb j b i a j a i m t,a a i a x j b i,{ a i}
    交换作业i和作业j的加工顺序,得到作业集S的另一调度,它所 需的加工时间为T’(S,t)=ai+aj+T(S-{i,j},tji) 其中,tji b j b i a j a i m t,a i a a j x b j,{ a j} 当作业i和j满足Johnson不等式时,有
    max{bi,aj}max{bj,ai}
    ai aj max{bi,aj}ai aj max{bj,ai}
    maxai{aj bi,ai}maxa{i aj bj,aj}
    maxt,{ai aj bi,ai}maxt,{ai aj bj,aj}
    由此可见当作业i和作业j不满足Johnson不等式时,交换它们的 加工顺序后,不增加加工时间。对于流水作业调度问题,必存 在最优调度 ,使得作业(i)和(i+1)满足Johnson不等式。进一 步还可以证明,调度满足Johnson法则当且仅当对任意i<j有
    mb i(i)n ,a ({ j)} mb i(j) n ,a ({ i)}
    由此可知,所有满足Johnson法则的调度均为最优调度。 36

    算法描述
    流水作业调度问题的Johnson算法 (1)令 N 1 { i|a i b i}N 2 , { i|a i b i}; (2)将N1中作业依ai的非减序排序;将N2中作 业依bi的非增序排序; (3)N1中作业接N2中作业构成满足Johnson法 则的最优调度。
    算法复杂度分析: 算法的主要计算时间花在对作业集的排序。因此,在最坏情 况下算法所需的计算时间为O(nlogn)。所需的空间为O(n)。
    37

    0-1背包问题

    给定n种物品和一背包。物品i的重量是wi,其价值为vi,背 包的容量为C。问应如何选择装入背包的物品,使得装入背 包中物品的总价值最大?
    0-1背包问题是一个特殊的整数规划问题。

    n
    max vi xi i 1




    n
    wi xi C
    i1

    xi {0,1},1 i n

    38

    0-1背包问题

    设所给0-1背包问题的子问题

    n
    max vk xk k i





    算法复杂度分析:

    xk

    n
    wk xk
    k i
    {0,1},i

    j k

    n

    从m(i,j)的递归式容易看出,算法需要O(nc)计算时

    的最间优。值当为背m包(容i,量j),c很即大m时(i,,j算)是法背需包要容的量计为算j,时可间选较择多物。品为i,

    i+1例,如…,,当n时c>02-n1时背,包算问法题需的要最Ω优(n值2n。)计由算0-时1背间包。问题的最优子

    结构性质,可以建立计算m(i,j)的递归式如下。

    m ( i,j) m m ( a i 1 ,x m j) ( i m { ,( 1 i, j1 ) ,j w i) v i}0 j j w iw i

    m(n,j)v0n

    jwn 0jwn

    39

    算法改进
    由m(i,j)的递归式容易证明,在一般情况下,对每一个确定的 i(1≤i≤n),函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃 点是这一类函数的描述特征。在一般情况下,函数m(i,j)由其全 部跳跃点惟一确定。如图所示。
    对每一个确定的i(1≤i≤n),用一个表p[i]存储函数m(i,j)的全部 跳跃点。表p[i]可依计算m(i,j)的递归式递归地由表p[i+1]计算, 初始时p[n+1]={(0,0)}。
    40

    典型例子(一)

    n=3,c=6,w={4,3,2},v={5,2,1}。

    m(4,x)

    m(4,x-2)+1

    (0,0)

    (2,1)

    x

    x

    m(3,x)
    (0,0) (2,1)
    x

    m(2,x)

    m(3,x) (0,0) (2,1)

    x

    m(3,x-3)+2(5,3)
    (3,2) (0,0)
    x

    (3,2) (5,3) (2,1)
    x

    m(2,x)
    (3,2) (5,3) (0,0) (2,1)
    x

    m(2,x-4)+5 (7,7) (9,8) m(1,x)

    (7,7) (9,8)

    (6,6) (4,5)

    (4,5)(6,6)

    (0,

    0)

    (2,

    (3,2) 1)

    (5,3)

    x
    41
    x

    算法改进
    ?函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi作max运算得 到的。因此,函数m(i,j)的全部跳跃点包含于函数m(i+1,j)的跳 跃点集p[i+1]与函数m(i+1,j-wi)+vi的跳跃点集q[i+1]的并集中。 易知,(s,t)q[i+1]当且仅当wisc且(s-wi,t-vi)p[i+1]。因此, 容易由p[i+1]确定跳跃点集q[i+1]如下 q[i+1]=p[i+1](wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))p[i+1]} ?另一方面,设(a,b)和(c,d)是p[i+1]q[i+1]中的2个跳跃点, 则当ca且d<b时,(c,d)受控于(a,b),从而(c,d)不是p[i]中 的跳跃点。除受控跳跃点外,p[i+1]q[i+1]中的其他跳跃点均 为p[i]中的跳跃点。 ?由此可见,在递归地由表p[i+1]计算表p[i]时,可先由p[i+1]计 算出q[i+1],然后合并表p[i+1]和表q[i+1],并清除其中的受控 跳跃点得到表p[i]。
    42

    典型例子(二)
    n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}。
    初始时p[6]={(0,0)},(w5,v5)=(4,6)。因此, q[6]=p[6](w5,v5)={(4,6)}。 p[5]={(0,0),(4,6)}。 q[5]=p[5](w4,v4)={(5,4),(9,10)}。从跳跃点集p[5]与q[5]的并集 p[5]q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点(5,4)受控于跳 跃点(4,6)。将受控跳跃点(5,4)清除后,得到 p[4]={(0,0),(4,6),(9,10)} q[4]=p[4](6,5)={(6,5),(10,11)} p[3]={(0,0),(4,6),(9,10),(10,11)} q[3]=p[3](2,3)={(2,3),(6,9)} p[2]={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)} q[2]=p[2](2,6)={(2,6),(4,9),(6,12),(8,15)} p[1]={(0,0),(2,6),(4,9),(6,12),(8,15)} p[1]的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=1435。

    算法复杂度分析
    上述算法的主要计算量在于计算跳跃点集 p[i](1≤i≤n)。由于q[i+1]=p[i+1](wi,vi),故计算 q[i+1]需要O(|p[i+1]|)计算时间。合并p[i+1]和 q[i+1]并清除受控跳跃点也需要O(|p[i+1]|)计算时 间。从跳跃点集p[i]的定义可以看出,p[i]中的跳 跃点相应于xi,…,xn的0/1赋值。因此,p[i]中跳跃 点个数不超过2n-i+1。由此可见,算法计算跳跃点 集p[i]所花费的计算时间为 O n|p[i1]| O n2ni O2n 从而,改进后算法的计算时 间i2复杂性为i2O(2n)。当 所给物品的重量wi(1≤i≤n)是整数时,|p[i]|≤c+1, (1≤i≤n)。在这种情况下,改进后算法的计算时间 复杂性为O(min{nc,2n})。
    44

    最优二叉搜索树

    ? 什么是二叉搜索树?

    45

    12

    53

    3
    (1)若它的左子树不空,则左子树上所有 节点的值均小于它的根节点的值;
    (2)若它的右子树不空,则右子树上所有 节点的值均大于它的根节点的值;
    (3 它的左、右子树也分别为二叉排序树

    37 24

    100
    61 90
    78

    在随机的情况下,二叉查找树的平均查找长度 和log n是等数量级的

    45

    二叉查找树的期望耗费

    k2

    ? 查找成功与不成功的概率

    n

    n

    pi qi 1

    i1

    i0

    k1 d 0 d1

    k5

    k4

    d5

    ? 二查找树的期望耗费

    k3

    d4

    E(searcchositnT)

    d2

    d3

    n

    n

    (deptTh(ki)1) pi (deptTh(di)1)qi

    i1

    i0

    n

    n

    1 deptTh(ki) pi deptTh(di)qi

    i1

    i0

    ? 有 n个节点的二叉树的个数为:(4n /n3/2)

    ? 穷举搜索法的时间复杂度为指数级

    46

    二叉查找树的期望耗费示例

    node

    depth probabilit y contributi on

    k1

    1

    0.15

    k2

    0

    0.10

    k2

    k3

    2

    0.05

    k1

    k4

    k4

    1

    0.10

    k5

    2

    0.20

    d 0 d1

    k3

    k5

    d0

    2

    0.05

    d1

    2

    0.10

    d2

    d3

    d4

    d5

    d2

    3

    0.05

    d3

    3

    0.05

    d4

    3

    0.05

    d5

    3

    0.10

    Total

    0.30 0.10 0.15 0.20 0.60 0.15 0.30 0.20 0.20 0.20 0.40 2.80
    47

    最优二叉搜索树

    最优二叉搜索树Tij的平均路长为pij,则所求的最优值为p1,n。 由最优二叉搜索树问题的最优子结构性质可建立计算pij的递 归式如下
    w i,jp i,j w i,j m i k j{ w i,k i 1 p n i,k 1 w k 1 ,jp k 1 ,j}

    记wi,jpi,j为m(i,j),则m(1,n)=w1,np1,n=p1,n为所求的最优值。计 算m(i,j)的递归式为
    m (i,j)w i,j m i kj{ m i(in ,k 1 ) m (k 1 ,j)}i ,j
    m (i,i 1 ) 0 , 1 in

    注意到,

    m { m ( i , k i 1 ) n m ( k 1 ,j ) } m { m ( i i , k n 1 ) m ( k 1 ,j )}

    i k j

    s [ i ] j 1 [ ] k s [ i 1 ] j ] [

    可以得到O(n2)的算法
    48