算法设计与分析-PPT(20141108)剖析.ppt

1、武汉大学研究生专业课程,算法设计与分析,教学内容,概述 基本数据结构 分治法 贪心法 动态规划 回溯法,第1章 概述,算法的定义与特性 算法的学习内容 算法的评价与分析 算法分析举例,算法的定义与特性,定义 一组有穷的规则，它规定了解决某一特定问题的一系列运算。 特性 每一种运算有确切的定义 每一种运算都是基本运算 有0个或多个输入 有1个或多个输出 在执行了有穷步运算后终止,算法的学习内容,如何设计算法 如何表示算法 如何确认算法 如何分析算法 如何测试程序,算法的评价与分析,算法的评价标准 影响算法执行时间的因素 算法执行时间的渐近表示 三个重要定理 常见的时间复杂度,算法的评价标准,对体

2、现算法的程序的结构进行评价 对算法的运行时间和所占空间进行评价,影响算法执行时间的因素,解决问题的策略 算法执行哪些运算 算法赖以工作的数据集 编译的目标代码质量 计算机本身的性能,算法执行时间的渐近表示,算法的执行时间等于算法中各语句执行时间的总和，而某个 语句的执行时间等于该语句执行一次所需时间与执行次数的乘 积。 算法的执行时间通常表示成数量级的形式： T(n)=O(f(n) 其含义为：当问题规模n足够大时，算法的执行时间T(n)和函数 f(n)成正比。或者说，存在正常数c和n0，当nn0时，有 |T(n)|c|f(n)|。 如果算法的执行时间T(n)与问题规模n无关，则记作 T(n)=

3、O(1)。 用数量级形式表示的算法的执行时间，通常称为算法的时间复杂度。,三个重要定理,定理1 若T(n)=amnm+am1nm1+a1n+a0是一个m次多项式,则 T(n)=O(nm) 定理2 若T1(n)、T2(n)分别是算法P1、P2的执行时间，并且 T1(n) = O (f(n) T2(n) = O (g(n) 则依次执行算法P1和P2，总的执行时间 T(n) = O (max (|f (n)|，|g(n)|) 定理3 若T1(n)、T2(n)分别是算法P1、P2的执行时间，并且 T1(n) = O(f (n) T2(n) = k(n) T1(n) 则 T2(n) = O (k (n)

4、f(n),常见的时间复杂度,用数量级形式O(f(n)表示算法执行时间T(n)的时候， 函数f(n)通常取较简单的形式，例如 1、log2n、n、nlog2n、n2、n3、2n 在n较大的情况下，常见的时间复杂度之间存在下 列关系： O(1) O (log2n) O (n) O (nlog2n) O (n2) O (n3) O (2n),算法分析举例 (1),假设A1An中存放了n个整数，下面程序段 的功能是确定其中值最大的整数在数组中的下标i。 请分析程序段中每个语句的执行次数，并用数 量级形式表示这个程序段的执行时间。 i=1; for(j=2;jAi) i=j;,1次 n次 n1次 最多n

5、1次,语句总的执行次数是2n3n1次，程序段执行时间是O(n)。,算法分析举例 (2),假设A1An中存放了n个整数，其中n100。 下面程序段的功能是求其中前100个整数的平均值。 请分析程序段中每个语句的执行次数，并用数量 级形式表示这个程序段的执行时间。 s=0.0; for(i=1;i=100;i+) s=s+Ai; couts/100;,1次 101次 100次 1次,语句的执行次数和n无关，程序段的执行时间是O(1)。,算法分析举例 (3),下面程序段的功能是从n阶整型矩阵中找出两个 值最小的整数。请分析其时间复杂度。 m1=32767; m2=m1; for(i=0;in;i+)

6、 for(j=0;jn;j+) if(Aijm1) m2=m1;m1=Aij; else if(Aijm2) m2=Aij;,执行第1行赋值语句所需时间是O(1), 执行一遍内循环体所需时间也是O(1), 由于内循环体总共执行了n2次,因此, 程序段的执行时间为O(n2)。,算法分析举例 (4),下面的程序段可用于求xn。 请分析其时间复杂度。 y=1;u=x;v=n; while(v0) if (v%2=1) y=y*u; u=u*u;v=v/2; couty;,执行时间主要用在while循环上。 由于v的初始值是n，每循环一遍，v值被减半，因此，循环次数不超过log2n次。 执行一遍循环体

7、所需时间是O(1)。 程序段的执行时间为 T(n)= (log2n)O(1) = O (log 2 n),算法分析举例 (5),下面的算法是用来求解著名 的汉诺塔问题的。 请分析算法的时间复杂度。 void hanoi(int n, char a,char b,char c) if (n0) hanoi(n1,a,c,b); coutc; hanoi(n1,b,a,c); ,当n=0时，所需时间为T(n)=O(1)； 当n0时，执行了一个输出语句和两个递归调用语句，所需时间为O(1)+2T(n1)。 算法的执行时间是 T(n)=2T(n1)+ O(1) =. = O(2n),第2章 基本数据结

8、构,二叉树（二元树） 堆 二叉排序树（二分检索树） 图,线性表 栈 队列 树,线性表,线性表 是一个元素序列，第一个元素没有前驱，最后 一个元素没有后继，其余元素都有唯一的前驱和唯 一的后继。 顺序表 是一种用顺序方法存储的线性表。 单向链表 是一种用链接方法存储的线性表。,例:线性表,顺序表,单向链表,c,b,a,V,( c , b , a ),线性表,顺序表,单向链表,1 2 3 4 n,L=3,栈,定义 是一种特殊的线性表，规定所有的插入操 作和删除操作都限定在表的同一端进行。 逻辑特性 后进先出。 用途 暂存待处理的元素。,栈的存储结构,a,b,c,S,顺序栈,链接栈,1 2 3 4

9、n,t=3,栈的基本操作,创建一个空栈 往栈顶插入一个新元素 删除栈顶元素 读取栈顶元素,算法(创建与插入),/创建一个空栈 procedure INITSTACK(S,t) t0 end INITSTACK; /往栈顶插入一个新元素 procedure PUSH(n,S,t,x) if t=n then STACKFULL endif; tt+1; Stx end PUSH;,算法(删除与读取),/ 删除栈顶元素 procedure POP(S,t) if t=0 then STACKEMPTY endif; tt-1 end POP; /读取栈顶元素 procedure GETTOP(S,

10、t,x) if t=0 then STACKEMPTY endif; xSt end GETTOP;,队列,定义 是一种特殊的线性表，所有的插入操作限定在 表的一端进行，所有的删除操作限定在表的另一端 进行。 逻辑特性 先进先出。 用途 暂存待处理的元素。,队列的存储结构,c,b,a,Q,顺序队列,链接队列,0 1 2 3 n,front=0 rear=3,rear,队列的基本操作,创建一个空队列 往队尾插入一个新元素 删除队首元素 读取队首元素,算法(创建与插入),/创建一个空队列 procedure INITQUEUE(Q,front,rear) front0; rear0 end INI

11、TQUEUE; /往队尾插入一个新元素 procedure ENQUEUE(n,Q,front,rear,x) if (rear+1)%(n+1)=front then QUEUEFULL endif; Qrearx; rear(rear+1)%(n+1) end ENQUEUE;,算法(删除与读取),/ 删除队首元素 procedure DEQUEUE(Q,front,rear) if front=rear then QUEUEEMPTY endif; front(front+1)%(n+1) end DEQUEUE; /读取队首元素 procedure GETHEAD(Q,front,re

12、ar,x) if front=rear then QUEUEEMPTY endif; xQfront end GETHEAD;,树,定义 是一种典型的树型结构，每个结点最多只有一 个前驱（父结点），但可以有多个后继（子结点）。 常用术语 根，树叶，父结点，子结点，子树，层数，高度 存储方法 二叉链表（左孩子右兄弟链表）存储表示。,例：树和二叉链表存储表示,a,b,c,d,e,f,g,a,b,c,d,e,f,g,二叉树,定义 是一种典型的树型结构，每个结点的前驱 （父结点）最多只有一个，后继（子结点）最多有两个，并且有左右之分。 存储方法 二叉链表存储表示；顺序存储表示。,例：二叉树和二叉链表存

13、储表示,a,b,c,d,e,f,a,b,c,e,d,f,满二叉树和完全二叉树,满二叉树 每一层上的结点个数都达到最大值，即第1层1个,第2层2个,第3层4个,.,第h层2h-1个。 高度为h的满二叉树中有2h1个结点。 完全二叉树 除了最底层之外，其余各层上结点个数都达到最大值，而且最底层上的结点都集中在该层最左边的若干连续的位置上。 满二叉树是完全二叉树的特例。,例: 满二叉树,完全二叉树,普通二叉树,满二叉树 完全二叉树 普通二叉树,例:完全二叉树的顺序存储表示,d,c,k,j,i,h,g,f,e,a,b,1 2 3 4 5 6 7 8 9 10 11,R a b c d e f g h

14、i j k,堆,定义 是一棵用顺序方法存储的完全二叉树，有两种形 式： 每个结点的值都不比其子结点的值小（称为大堆）； 每个结点的值都不比其子结点的值大（称为小堆）。 应用场合 要求快速地从元素表中找出最大(最小)值；对这个元 素表经常要进行插入删除操作。,例：大堆,97,76,85,49,76,38,29,27,1 2 3 4 5 6 7 8,97 76 85 49 76 38 27 29,R,算法(往堆中插入一个元素),procedure ADD(n,R,x) integer s,f; nn+1; sn; fs/2; while f0 and xRf do RsRf; sf; fs/2;

15、endwhile Rsx; end ADD,算法(取走堆顶元素),procedure DEL(n,R,x) integer s,f; xR1; R1Rn; nn-1; f1; s2; while sn do if sn并且RsRs+1 then ss+1 endif; if RfRs then 交换Rf和Rs; fs; s2*f; else exit endif endwhile end DEL,二叉排序树,定义 二叉排序树是一种二叉树，每个结点的关键字比 其左子树中所有结点的关键字都大，比其右子树中所 有结点的关键字都小。 应用场合 结点数很多，经常要进行插入/删除操作，希望得 到较快的查找

16、速度。,例: 二叉排序树,二叉排序树 普通的二叉树,图,定义 是一种比树更复杂的非线性结构，每个结点都 可以有多个前驱和多个后继。 分类 有向图，无向图，有向网络，无向网络 存储方法 邻接矩阵,有向图和无向图,有向图 无向图,有向网络和无向网络,有向网络 无向网络,邻接矩阵,邻接矩阵是一种表示结点之间相邻关系的矩阵。 对于具有n个结点的图，它的邻接矩阵定义为： 对于具有n个结点的网络，它的邻接矩阵定义为： 其中，wij表示边或(vi ,vj )上的权值。,例： 图的邻接矩阵,例： 网络的邻接矩阵,第3章 分治法,基本思想 例1 二分检索 例2 快速分类,基本思想,将一个输入规模为n的问题，分解

17、成规模较小 的若干子问题，分别求解这些子问题，然后用 适当的方法将这些子问题的解结合起来，得到 原问题的解。 算法通常用递归的形式给出。,例1 二分检索,问题描述 分治策略 算法 时间复杂度,问题描述,对于一个按递增有序排列的元素表 (a1,a2,an) 要求判定元素x是否在表中出现。 原问题可描述为 Q=(n,a1,a2,an,x) 若x在表中，则将其序号赋值给j,分治策略,选取一个下标k，将原问题分解成三个子问题： Q1=(k-1,a1,ak-1,x) Q2=(1,ak,x) Q3=(n-k,ak+1,an,x) 对于Q2，若ak=x，则j=k，结束；否则，对Q1和Q3继续进行分解，每次分

18、解时选取的k正好是元素表中间元素的下标。,递归算法（二分检索）,procedure BINSRCH(A,L,H,x,j) integer k; if LH then j 0;return endif; K=(L+H)/2; case :xAK: BINSRCH(A,K+1,H,x,j); endcase end BINSRCH,非递归算法（二分检索）,procedure BINSRCH(A,n,x,j) integer L,H,K; L 1;H n; while LH do K (L+H)/2; case :xAK: L K+1; endcase endwhile j 0; /没找到 end

19、BINSRCH,13,27,38,49,56,76,85,97,V,1 2 3 4 5 6 7 8,下界L=1 上界H=8 中间位置K=(1+8) / 2=4,例1：查找56,13,27,38,49,56,76,85,97,V,1 2 3 4 5 6 7 8,下界L=5 上界H=8 中间位置K=(5+8) / 2=6,例1：查找56,13,27,38,49,56,76,85,97,V,1 2 3 4 5 6 7 8,下界L=5 上界H=5 中间位置K=(5+5) / 2=5,例1：查找56,13,27,38,49,56,76,85,97,V,1 2 3 4 5 6 7 8,下界L=1 上界H=

20、8 中间位置K=(1+8) / 2=4,例2：查找14,13,27,38,49,56,76,85,97,V,1 2 3 4 5 6 7 8,下界L=1 上界H=3 中间位置K=(1+3) / 2=2,例2：查找14,13,27,38,49,56,76,85,97,V,1 2 3 4 5 6 7 8,下界L=1 上界H=1 中间位置K=(1+1) / 2=1,例2：查找14,13,27,38,49,56,76,85,97,V,1 2 3 4 5 6 7 8,下界L=2 上界H=1,例2：查找14,时间复杂度,在二分检索过程中，元素间每比较一次检索范围就缩 小一半。每次比较可能涉及的元素个数如下:

21、 比较次数 1 2 3 4 j 可能涉及的元素个数 1 2 4 8 2j1 若元素个数n正好为 则二分检索过程中元素间比较次数最大值为 j=log2(n+1),假设检索每个元素的概率相等，则平均比较次数为 所以,二分检索算法的执行时间是O(log2n)。 在所有基于比较的检索方法中，二分检索的速度是最快的。,例2 快速分类,问题描述 分治策略 算法 时间复杂度,问题描述,对长度为n的元素表 A=(a1,a2,an) 按元素值非降顺序重新排列。,分治策略,选择A中的某个元素t作为标准元素,把元素表A分成左右两个子表,左子表中的元素值都不大于t,右子表中的元素值都不小于t； 对每个子表重复执行这种

22、划分操作。 为了简化算法，可选表中第1个元素作为每次划分的标准元素。,算法（一次划分）,procedure PARTITION(m,p,k) /以Am为标准元素对Am:p进行划分,标准元素最后放入Ak中 t Am； while mp do while mp并且Ap t do p p-1 endwhile; if mp then Am Ap; m m+1 endif; while mp并且Am t do m m+1 endwhile; if mp then Ap Am; p p-1 endif; endwhile; k m; Ak t; end PARTITION,例 一次划分过程,v,49,7

23、6,97,27,38,13,85,0 1 2 3 4 5 6 7 8,65,例,v,49,76,97,27,38,13,85,0 1 2 3 4 5 6 7 8,65,i j,例,v,49,76,97,27,38,13,85,0 1 2 3 4 5 6 7 8,65,i j,例,v,49,76,97,27,38,13,85,0 1 2 3 4 5 6 7 8,65,i j,例,v,49,76,97,27,38,13,85,0 1 2 3 4 5 6 7 8,65,i j,例,v,49,76,97,27,38,13,85,0 1 2 3 4 5 6 7 8,65,i j,例,v,49,76,97

24、,27,38,13,85,0 1 2 3 4 5 6 7 8,65,i j,例,v,49,76,97,27,38,13,85,0 1 2 3 4 5 6 7 8,65,i j,例,v,49,76,97,27,38,13,85,0 1 2 3 4 5 6 7 8,65,i j,例,v,49,76,97,27,38,13,85,0 1 2 3 4 5 6 7 8,65,i j,算法(快速分类),procedure QUICKSORT(p,q) /对Ap:q进行快速分类 integer k; if pq then PARTITION(p,q,k); QUICKSORT(p,k-1); QUICKSO

25、RT(k+1,q); endif; end QUICKSORT 首次调用:QUICKSORT(1,n),时间复杂度,设P(n)是对A1:n进行快速分类所需要的元素平均比较次数。由于第一 次分组后，标准元素A1有可能被交换到Ak中，其中，k=1, 2, , n，假设 k取1到n之间任何一值的概率相同，则有,（一）,用n1代换式(一)中的n，得,（二）,由式(一)减式(二)，得,因为,所以 P(n)2(n+1)ln(n+1)=O(nlog2n),第4章 贪心法,问题特征 解题过程 关键步骤 例1 背包问题 例2 带期限的作业排序问题,问题特征,有n个输入，问题的解由这n个输入的某个子集组成。 这个

26、子集必须满足某个事先约定的条件（约束条 件），满足约束条件的子集（可行解）可能有多个。 为了衡量可行解的优劣，事先要给出一个标准（目标 函数）。 使目标函数取极值的可行解就是要求的最优解。,解题过程,确定一种量度标准，将n个输入排列成这种量度标准所要求的顺序； 按这种顺序每次考察一个输入量，如果这个输入量和当前已构成的部分最优解加在一起不能产生一个可行解，则舍弃这个输入量； 最终结果在考察了n个输入量以后得到。,关键步骤,对于一个给定的问题，可能存在多种量 度标准。为了得到最优解，必须保证所选择 的量度标准是最优量度标准。,例1 背包问题,问题描述 目标函数与约束条件 实例 量度标准 贪心算法

27、 证明贪心解是最优解,问题描述,M-背包可容纳物品的总重量； n- 物品种类数； wi-第i种物品的重量； pixi-数量为xi的第i种物品放入背包可产生的 效益值。 如何装包，才能使放入背包的物品的总效益值 最大？ 只讨论 的情况。,目标函数与约束条件,目标函数 约束条件 0 xi1 pi0 wi0 1in,实例,M=20, n=3, W=(18,15,10), P=(25,24,15) 有许多可行解,例如: x1 x2 x3 0 2/3 1 20 31 1 2/15 0 20 28.2 0 1 1/2 20 31.5 1/2 1/3 1/4 16.5 24.25,量度标准,（标准1） 放种

28、类尽可能多的物品，即按wi非减顺序考察每种物品。 （标准2） 放效益尽可能大的物品，即按pi非增顺序考察每种物品。 （标准3） 使每次选取的物品具有最大的单位容量效益值，即按pi/wi非增顺序考察每种物品。 评价 标准1的缺点是效益增长慢； 标准2的缺点是容量消耗快； 标准3是最优量度标准。,算法(背包问题),procedure KNAPSACK(P,W,M,X,n) /假设n种物品的效益值和重量值已按pi/wi非增顺序分别存入P数组和W数组中；X数组用于存放最优解(贪心解)。 integer i; real v; X1:n 0; v M; for i 1 to n do if Wiv the

29、n exit endif; Xi 1; v v-Wi endfor; if in then Xi v/Wi endif; end KNAPSACK,如何证明贪心解是最优解?,逐个比较贪心解 X=(x1, x2, x3,., xn) 和某个最优解 Y =(y1, y2, y3, yn) 中每个元素，找出第一个不同的元素xi和yi ； 用贪心解中的xi替换最优解中的yi ； 证明在作了这种替换后，最优解y的总效益值没有损失（仍是最优的）； 反复进行这种比较和替换，直到贪心解x和最优解y成为同一个解。,证明,设X=(x1,x2,.,xn)是贪心解。 若所有的xi都是1，则X显然是最优解。 设j是使x

30、j1的最小下标。有算法可知，对于1ij， xi =1；对于jin，xi =0；对于i=j，0 xi 1。 若X不是最优解，设Y =(y1,y2,.,yn)是最优解，即 设k是使ykxk的最小下标,即 x1=y1, x2=y2, x3=y3, , xkyk, 下面先来证明ykxk。,kj，有xi=0。若ykxk ，由于 即 则 (矛盾) 所以，当k=j时，也有ykj的情况 此时，xk=0,由于ykxk，则有yk0。于是 (矛盾) 说明kj是不可能的情况。,现在，把yk增加到xk，即第k种物品的重量增加(xk-yk)wk，而从(yk+1,yk+2,.,yn)中 减去同样多的量，使总重量保持为M。

31、于是产生一个新的解Z=(z1,z2,.,zn)，其中 z1=x1,z2=x2, .,zk=xk, 并且 Z的总效益为 由于当ki时，pk/wk pi/wi所以 因为Y是最优解，所以Z也是最优解。 如果ZX，则重复上述替换步骤，每次得到的新解都是最优解。 经有限步替换后，得到Z=X，证明X是最优解。,例2 带期限的作业排序问题,问题描述 目标函数与约束条件 实例 量度标准 贪心解 证明贪心解是最优解 贪心算法,问题描述,在一台机器上处理n个作业，每个作业可在单位时间内完成。每个作业i有截止期限di，当且仅当作业i在截止期限di内完成，可获得效益pi。为了获得最大效益值，应该选择哪些作业，并按怎样

32、的顺序进行处理？,目标函数与约束条件,目标函数 约束条件 J中每个作业在各自截止期限内完成。,实例,作业数 n=4 效益值 P=（100，10，15，20） 截止期限 D=（ 2， 1， 2， 1）,实例的所有可行解,选择作业 处理顺序 效益值 1 1 100 2 2 10 3 3 15 4 4 20 1，2 2，1 110 1，3 1，3 或 3，1 115 1，4 4，1 120 2，3 2，3 25 3，4 4，3 35,量度标准,用目标函数作量度标准。 使用这一标准，每次加入J中的作业一定在满 足约束的条件下，使得 获得最大增加量。 这就要求按pi非增次序来考虑每个作业。,贪心解,J1

33、; for i 2 to n do if J i可行 then J J i endif endfor; 由此得到的解称为贪心解。在这个解中，集合J包 含了所有能在各自截止期限之内完成的作业。至于这 些作业应该按怎样的顺序处理，暂且不管它。,证明贪心解是最优解,设J是贪心解,I是最优解，JI。因为I是最优解，可排斥 ；由贪心工作方式，可排斥 。所以存在作业a和作业b， 。 设a是使得 的一个具有最大效益值的作业。由贪心方法可得出结论：对任何满足条件 的作业b，都有papb。这是因为若papb，贪心方法会先于作业a考虑作业b，并把作业b放入贪心解J中。,证明贪心解是最优解（续）,设SJ、SI是J、

34、I的可行调度表，c是J和I中共有的作业，在SJ中c在时刻tj被调度，在SI中c在时刻ti被调度。 SJ： c . SI: c 或则 SJ： c . SI： c ,证明贪心解是最优解（续）,对于tjti的情况，在SI中作类似的处理。 如此反复进行，使两个调度表中相同的作业在相同的时刻调度。 把在SI中调度的每一个作业b（ ）换成在同一时刻在SJ中调度的作业a。 由于papb，于是最优解I在不损失效益值的情况下变成了贪心解J。因此，J也是最优解。,如何判断作业集合J可行？,（结论）如果J是一个包含k个作业的可行解，则J中的这k个作业一定可以按期限值从小到大的顺序处理。 （意义）如果发现J中作业不能

35、按期限值从小到大的顺序处理，则可断定J不是可行解。 （证明）如果J是可行解，则必然存在一个调度序列 V=v1v2.vk ( vj 是第j个被调度的作业的编号) 使得dvjj (1jk)。这个调度序列未必和满足条件 du1 du2.duk 的调度序列 U=u1u2.uk 相同。下面将证明V可以转换成U。,结论的证明,设VU。令a是使得vaua的最小下标。 U=u1u2.ua.uc.uk (满足条件 du1 du2.duk) V=v1v2.va.vb.vk 设uc=va， vb=ua，则必有ba，ca。因为 dva=ducdua=dvb 即dvadvb，所以可将序列V中的va和vb交换。交换后的V

36、仍是一个可行的调度序列，而且与U更接近。反复进行这样的交换，就可以将V转换成U。,例：已知有6个作业，各作业的截止期限和效益值如表所示。为了获得最大效益值，应该从中选择哪些作业，并按怎样的顺序处理？,分析： 按效益值从大到小的顺序， 依次考虑下列作业： 2、3、1、6、4、5 只能处理下列作业： 1、2、3、4 必须按下列顺序处理： 1、2、4、3 或 1、4、2、3,算法(带期限的作业排序问题),procedure JS(D,J,n,k) /* n个作业已按效益值从大到小的顺序编号; D1:n存放n个作业的期限值; J1:k存放可行调度表; 从n个作业中选出k个作业,第i个被调度的作业编号

37、是Ji,它的截止期限是DJi。 */ integer u,v,w; D0 0; J0 0; /为简化算法,引入虚构的作业,k 1; Jk 1; /在可行调度表中放入第1个作业 for u 2 to n do /在可行调度表J1:k中为作业u找可能的插入位置 v k; while DJvDu且DJvv do v v-1 endwhile; /可能的插入位置是v+1 if DJv Du且Duv then / 如果可以插入 for w k downto v+1 do Jw+1 Jw endfor; Jv+1 u; k k+1; endif; endfor end JS,第5章 动态规划,问题特征 最

38、优性原理 局限性 关键步骤 例1 多段图问题 例2 资源分配问题,问题特征,是个求最优解的问题。 问题的求解过程可以分为若干个阶段；每个阶段要 作出一个决策；在作每个决策时，不能孤立地考虑本 阶段决策效果如何，而必须各阶段联系起来考虑，使 之形成一个最优决策序列。 适合用动态规划方法求解的问题必须满足最优性原 理（也称为问题的无后效性特征）,最优性原理,假设问题的求解过程分为k个阶段，并且 d1,d2,.,di 是最优决策序列中的前i个决策。在作后续决策时，不必 考虑前i个决策是如何作出的，只需考虑在作出决策di后的 状态，只要后续决策相对于作出决策di后的状态是最优的， 则它们相对于问题的初

39、始状态也是最优的，即 d1,d2,.,di ,.,dk 是问题的一个最优决策序列。,例,求a到f路径上边的权值之和最小的路径. 适合用动态规划求解. 求a到f路径上边的权值之和除以4所的余数最小的路径. 不适合用动态规划求解.,a,f,b,d,c,e,2,1,3,3,2,3,1,关键步骤,问：一个多阶段决策问题满足最优性原理，对解决该问题有什么用处？ 答：减轻计算工作量。 关键步骤：列出递推关系式（动态规划方程）,例1 多段图问题,1,4,3,2,8,7,6,11,10,9,12,5,t,s,V1 V2 V3 V4 V5,注:每条边有正的权值,图中没有标出.,分析,设P(i,j)是一条从Vi中

40、的结点j到汇点t的最小成本路径，cost(i,j)是这条路径的成本。由最优性原理可以得出递推关系式： cost(i,j)=minc(j,L)+cost(i+1,L) LVi+1 E 其中c(j,L)是有向边的权值。 用D(i,j)记录使c(j,L)+cost(i+1,L)取最小值的L值。,算法(多段图问题),procedure FGRAPH(E,k,P,n) / real cost1:n; integer D1:n, P1:k; costn 0; for j n-1 downto 1 do r 满足条件 E 且使cj,L+costL取最小值的L值 cost j c j,r+costr; D j

41、 r / D j是j的最优后继结点 endfor; P1=1;Pk=n; / P j存放路径上第j个结点的序号 for j 2 to k-1 do P j DP j-1 endfor end FGRAPH,例2 资源分配问题,已知把数量为x的资源分配给项目i可获得利润Gi,x。现有n个资源，m个项目，应如何分配才能获得最大利润？ 实例（资源n=700万元，项目A，B，C三个） 100 200 300 400 500 600 700 A 12 15 20 21 24 30 36 B 22 24 26 28 30 33 34 C 18 22 26 28 30 34 36 向项目A,B,C分别投资3

42、00,100,300万元,可获得最大 利润68万元。,分析,Gi,j 第i个项目分得j个资源后可获得的利润； Fi,j 按最优方案将j个资源分配给前i个项目所获得的利润； Xi,j 按最优方案将j个资源分配给前i个项目后第i个项目分得的资源数。 显然，当j=0时，Fi,j=Gi,j=0； 当j0，i=1时，Fi,j=Gi,j； 当j0，i1时，Fi,j= max Gi,k+Fi-1,j-k 0kj,依次考虑给一个项目分配资源，给两个项目分配资源， 给m个项目分配资源，分配资源数从1增加到n，最后得到利润 最大值Fm,n。 最优分配方案可通过倒推的方法得到： 第m个项目分得资源数 Xm,n; 第

43、m-1个项目分得资源数 Xm-1,n1, 其中, n1=n-Xm,n; 第m-2个项目分得资源数 Xm-2,n2, 其中, n2=n1-Xm-1,n1; .,1 2 3 4 5 6 7 (百万元),G F X,1 2 3,1 2 3,1 2 3,给第一个项目分配资源,1 2 3 4 5 6 7 (百万元),G F X,1 2 3,1 2 3,1 2 3,给前两个项目分配资源,计算过程,1 2 3 4 5 6 7 (百万元),G F X,1 2 3,1 2 3,1 2 3,给所有项目分配资源,计算过程,通过倒推的方法得到最优分配方案： 第3个项目分得资源数 X3,7=3(百万元); 第2个项目分

44、得资源数 X2,4=1 (百万元); 第1个项目分得资源数 X1,3=3 (百万元).,算法(找最优分配方案),procedure BUDGET(C,R,W,n) / for j 0 to n do F1,j G1,j; X1,j j endfor; for i 2 to m do for j 1 to n do k 0 ; for s 1 to j do if Gi,s+Fi-1,j-sGi,k+Fi-1,j-k then k s endif; endfor; Fi,j Gi,k+Fi-1,j-k ; Xi,j k endfor endfor end BUDGET,算法(输出最优分配方案),

45、procedure PRINT(m,n) if m1 then PRINT(m-1,n-Xm,n) endif; write Xm,n end PRINT,第6章 回溯法,问题特征 启发式搜索 约束条件 解答树 算法框架 例1 n后问题 例2 图着色问题,问题特征,这是一种用于求问题最优解或全体解的方法。问题的 解可以表示成一个n元组 (x1,x2,.,xn)， 它满足某种约束条件，并且通常使某个规范函数 P(x1,x2,.,xn) 取极值。,启发式搜索,盲目搜索法 假设xi的取值有mi种，构造 m1m2.mn 个元组（它们都可能 是解），逐一测试。 启发式搜索法 不断地用修改过的规范函数（限

46、界函数）Pi(x1,x2,.,xi) 去测 试正在构造中的n元组的部分向量 (x1,x2,.,xi)，看其是否可能 导致问题的解，如果判定 (x1,x2,.,xi) 不可能导致解，就不再进 一步测试 (xi+1,xi+2,.,xn),约束条件,构成问题解的元组必须满足一组综合的约束条件。 约束条件有两种类型。 显式约束 限定每个xi只能从一个给定的集合上取值。满足显式 约束条件的所有元组构成问题的一个可能解的集合。 隐式约束 描述各个xi之间的相互关系。满足隐式约束条件的元 组是真正要求的解。,解答树,这是一种用来表示问题求解过程的树：根结点下 面的边表示x1的取值，第二层结点下面的边表示x2

47、的取 值，从根结点到底层每个树叶结点的路径构成一个n 元组(x1,x2,.,xn) ，它可能是一个解。树叶结点称为可 能的答案结点。,用于描述4后问题求解过程的解答树,X=(2,4,1,3),X=(3,1,4,2),解答树中的三种结点,活结点 已生成的一个结点，它的子结点尚未全部生成。 E结点 当前正在扩展（正在生成子结点）的活结点。 死结点 不再进一步扩展的结点。,两种扩展结点的方法,方法1 当前的E结点R一旦生成一个子结点C，C就变成新的E 结点；当检测了以C为根的子树之后，R再次成为E结点。 方法2 一个E结点一直保持到变成死结点为止。 回溯法 使用限界函数,并用第一种方法扩展结点. 分枝限界法 使用限界函数,并用第二种方法扩展结点.,算法框架,procedure BACKTRACK(k) /设(x1,x2,.,xk-1)是解答树中从根到某个结点的路径 for 满足条件(x1,x2,.,xk-1,xk)是一条路径, 并且(x1,x2,.,xk-1,xk)可能延伸到一个答案结点的每个xk do if xk已抵达一个答案结点 then 输出X数组 endif; BACKTRACK(k+1); endfor end BACKTRACK; 调用方式 : BAC