算法设计与分析20141108剖析.pptx

武汉大学研究生专业课程 算法设计与分析教学内容n概述n基本数据结构n分治法n贪心法n动态规划n回溯法第1章 概述n算法的定义与特性n算法的学习内容 n算法的评价与分析n算法分析举例算法的定义与特性n定义 一组有穷的规则，它规定了解决某一特定问题的一系列运算。n特性n每一种运算有确切的定义n每一种运算都是基本运算n有0个或多个输入n有1个或多个输出n在执行了有穷步运算后终止算法的学习内容n如何设计算法n如何表示算法n如何确认算法n如何分析算法n如何测试程序算法的评价与分析n算法的评价标准n影响算法执行时间的因素n算法执行时间的渐近表示n三个重要定理n常见的时间复杂度算法的评价标准对体现算法的程序的结构进行评价对算法的运行时间和所占空间进行评价影响算法执行时间的因素n解决问题的策略n算法执行哪些运算n算法赖以工作的数据集n编译的目标代码质量n计算机本身的性能算法执行时间的渐近表示n算法的执行时间等于算法中各语句执行时间的总和，而某个语句的执行时间等于该语句执行一次所需时间与执行次数的乘积。n算法的执行时间通常表示成数量级的形式：T(n)=O(f(n)其含义为：当问题规模n足够大时，算法的执行时间T(n)和函数f(n)成正比。或者说，存在正常数c和n0，当nn0时，有|T(n)|c|f(n)|。n如果算法的执行时间T(n)与问题规模n无关，则记作 T(n)=O(1)。n用数量级形式表示的算法的执行时间，通常称为算法的时间复杂度。三个重要定理n定理1 若T(n)=amnm+am1nm1+a1n+a0是一个m次多项式,则 T(n)=O(nm)n定理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)|)n定理3 若T1(n)、T2(n)分别是算法P1、P2的执行时间，并且 T1(n)=O(f(n)T2(n)=k(n)T1(n)则 T2(n)=O(k(n)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;n1次nn次nn1次n最多n1次 n 语句总的执行次数是2n3n1次，程序段执行时间是O(n)。算法分析举例(2)假设A1An中存放了n个整数，其中n100。下面程序段的功能是求其中前100个整数的平均值。请分析程序段中每个语句的执行次数，并用数量级形式表示这个程序段的执行时间。s=0.0;for(i=1;i=100;i+)s=s+Ai;couts/100;n1次n101次n100次n1次n 语句的执行次数和n无关，程序段的执行时间是O(1)。算法分析举例(3)下面程序段的功能是从n阶整型矩阵中找出两个值最小的整数。请分析其时间复杂度。m1=32767;m2=m1;for(i=0;in;i+)for(j=0;jn;j+)if(Aijm1)m2=m1;m1=Aij;else if(Aij0)if(v%2=1)y=y*u;u=u*u;v=v/2;cout0)hanoi(n1,a,c,b);couta0时，执行了一个输出语句和两个递归调用语句，所需时间为O(1)+2T(n1)。n 算法的执行时间是n T(n)=2T(n1)+O(1)n =.n =O(2n)第2章 基本数据结构n 二叉树（二元树）n 堆n 二叉排序树（二分检索树）n 图n 线性表n 栈n 队列n 树线性表n线性表 是一个元素序列，第一个元素没有前驱，最后一个元素没有后继，其余元素都有唯一的前驱和唯一的后继。n顺序表 是一种用顺序方法存储的线性表。n单向链表 是一种用链接方法存储的线性表。例:线性表,顺序表,单向链表cbaV(c,b,a)线性表顺序表单向链表 1 2 3 4 n L=3栈n定义 是一种特殊的线性表，规定所有的插入操作和删除操作都限定在表的同一端进行。n逻辑特性 后进先出。n用途 暂存待处理的元素。栈的存储结构abcS顺序栈链接栈 1 2 3 4 nt=3栈的基本操作n创建一个空栈n往栈顶插入一个新元素n删除栈顶元素n读取栈顶元素算法(创建与插入)/创建一个空栈procedure INITSTACK(S,t)t0end INITSTACK;/往栈顶插入一个新元素procedure PUSH(n,S,t,x)if t=n then STACKFULL endif;tt+1;Stxend PUSH;算法(删除与读取)/删除栈顶元素 procedure POP(S,t)if t=0 then STACKEMPTY endif;tt-1end POP;/读取栈顶元素procedure GETTOP(S,t,x)if t=0 then STACKEMPTY endif;xStend GETTOP;队列n定义 是一种特殊的线性表，所有的插入操作限定在表的一端进行，所有的删除操作限定在表的另一端进行。n逻辑特性 先进先出。n用途 暂存待处理的元素。队列的存储结构cbaQ顺序队列链接队列 0 1 2 3 nfront=0rear=3rear队列的基本操作n创建一个空队列n往队尾插入一个新元素n删除队首元素n读取队首元素算法(创建与插入)/创建一个空队列procedure INITQUEUE(Q,front,rear)front0;rear0end INITQUEUE;/往队尾插入一个新元素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,rear,x)if front=rear then QUEUEEMPTY endif;xQfrontend GETHEAD;树n定义 是一种典型的树型结构，每个结点最多只有一个前驱（父结点），但可以有多个后继（子结点）。n常用术语 根，树叶，父结点，子结点，子树，层数，高度n存储方法 二叉链表（左孩子右兄弟链表）存储表示。例：树和二叉链表存储表示abcdefgabcdefg二叉树n定义 是一种典型的树型结构，每个结点的前驱（父结点）最多只有一个，后继（子结点）最多有两个，并且有左右之分。n存储方法 二叉链表存储表示；顺序存储表示。例：二叉树和二叉链表存储表示abcdefabcedf 满二叉树和完全二叉树n 满二叉树 每一层上的结点个数都达到最大值，即第1层1个,第2层2个,第3层4个,.,第h层2h-1个。高度为h的满二叉树中有2h1个结点。n 完全二叉树 除了最底层之外，其余各层上结点个数都达到最大值，而且最底层上的结点都集中在该层最左边的若干连续的位置上。满二叉树是完全二叉树的特例。例:满二叉树,完全二叉树,普通二叉树 满二叉树 完全二叉树 普通二叉树例:完全二叉树的顺序存储表示dckjihgfeab1 2 3 4 5 6 7 8 9 10 11 R a b c d e f g h i j k 堆n定义 是一棵用顺序方法存储的完全二叉树，有两种形式：每个结点的值都不比其子结点的值小（称为大堆）；每个结点的值都不比其子结点的值大（称为小堆）。n应用场合 要求快速地从元素表中找出最大(最小)值；对这个元素表经常要进行插入删除操作。例：大堆9776854976382927 1 2 3 4 5 6 7 897 76 85 49 76 38 27 29R算法(往堆中插入一个元素)procedure ADD(n,R,x)integer s,f;nn+1;sn;fs/2;while f0 and xRf do RsRf;sf;fs/2;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 endwhileend DEL二叉排序树n定义 二叉排序树是一种二叉树，每个结点的关键字比其左子树中所有结点的关键字都大，比其右子树中所有结点的关键字都小。n应用场合 结点数很多，经常要进行插入/删除操作，希望得到较快的查找速度。例:二叉排序树 二叉排序树 普通的二叉树图n定义 是一种比树更复杂的非线性结构，每个结点都可以有多个前驱和多个后继。n分类 有向图，无向图，有向网络，无向网络n存储方法 邻接矩阵有向图和无向图 有向图 无向图 有向网络和无向网络 有向网络 无向网络 邻接矩阵n邻接矩阵是一种表示结点之间相邻关系的矩阵。n对于具有n个结点的图，它的邻接矩阵定义为：n对于具有n个结点的网络，它的邻接矩阵定义为：其中，wij表示边或(vi,vj)上的权值。例：图的邻接矩阵例：网络的邻接矩阵第3章 分治法n基本思想n例1 二分检索n例2 快速分类基本思想n将一个输入规模为n的问题，分解成规模较小的若干子问题，分别求解这些子问题，然后用适当的方法将这些子问题的解结合起来，得到原问题的解。n算法通常用递归的形式给出。例1 二分检索n问题描述n分治策略n算法n时间复杂度问题描述n对于一个按递增有序排列的元素表 (a1,a2,an)要求判定元素x是否在表中出现。n原问题可描述为 Q=(n,a1,a2,an,x)若x在表中，则将其序号赋值给j分治策略n选取一个下标k，将原问题分解成三个子问题：Q1=(k-1,a1,ak-1,x)Q2=(1,ak,x)Q3=(n-k,ak+1,an,x)n对于Q2，若ak=x，则j=k，结束；否则，对Q1和Q3继续进行分解，每次分解时选取的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);endcaseend 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 BINSRCH 1327384956768597V1 2 3 4 5 6 7 8下界L=1上界H=8中间位置K=(1+8)/2=4例1：查找561327384956768597V1 2 3 4 5 6 7 8下界L=5上界H=8中间位置K=(5+8)/2=6例1：查找561327384956768597V1 2 3 4 5 6 7 8下界L=5上界H=5中间位置K=(5+5)/2=5例1：查找561327384956768597V1 2 3 4 5 6 7 8下界L=1上界H=8中间位置K=(1+8)/2=4例2：查找141327384956768597V1 2 3 4 5 6 7 8下界L=1上界H=3中间位置K=(1+3)/2=2例2：查找141327384956768597V1 2 3 4 5 6 7 8下界L=1上界H=1中间位置K=(1+1)/2=1例2：查找141327384956768597V1 2 3 4 5 6 7 8下界L=2上界H=1 例2：查找14时间复杂度n在二分检索过程中，元素间每比较一次检索范围就缩小一半。每次比较可能涉及的元素个数如下:比较次数 1 2 3 4 j 可能涉及的元素个数 1 2 4 8 2j1 n若元素个数n正好为则二分检索过程中元素间比较次数最大值为 j=log2(n+1)n假设检索每个元素的概率相等，则平均比较次数为所以,二分检索算法的执行时间是O(log2n)。n 在所有基于比较的检索方法中，二分检索的速度是最快的。例2 快速分类n问题描述n分治策略n算法n时间复杂度问题描述n对长度为n的元素表 A=(a1,a2,an)按元素值非降顺序重新排列。分治策略n选择A中的某个元素t作为标准元素,把元素表A分成左右两个子表,左子表中的元素值都不大于t,右子表中的元素值都不小于t；n对每个子表重复执行这种划分操作。n为了简化算法，可选表中第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例 一次划分过程v49769727381385 0 1 2 3 4 5 6 7 865例v49769727381385 0 1 2 3 4 5 6 7 865 i j例v49769727381385 0 1 2 3 4 5 6 7 865 i j例v49769727381385 0 1 2 3 4 5 6 7 865 i j例v49769727381385 0 1 2 3 4 5 6 7 865 i j例v49769727381385 0 1 2 3 4 5 6 7 865 i j例v49769727381385 0 1 2 3 4 5 6 7 865 i j例v49769727381385 0 1 2 3 4 5 6 7 865 i j例v49769727381385 0 1 2 3 4 5 6 7 865 i j例v49769727381385 0 1 2 3 4 5 6 7 865 i j算法(快速分类)procedure QUICKSORT(p,q)/对对Ap:q进行快速分类进行快速分类 integer k;if p0 wi0 1in实例nM=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 量度标准n（标准1）放种类尽可能多的物品，即按wi非减顺序考察每种物品。n（标准2）放效益尽可能大的物品，即按pi非增顺序考察每种物品。n（标准3）使每次选取的物品具有最大的单位容量效益值，即按pi/wi非增顺序考察每种物品。评价l标准1的缺点是效益增长慢；l标准2的缺点是容量消耗快；l标准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 then exit endif;Xi 1;v v-Wi endfor;if in then Xi v/Wi endif;end KNAPSACK如何证明贪心解是最优解?n逐个比较贪心解 X=(x1,x2,x3,.,xn)和某个最优解 Y=(y1,y2,y3,yn)中每个元素，找出第一个不同的元素xi和yi；n用贪心解中的xi替换最优解中的yi；n证明在作了这种替换后，最优解y的总效益值没有损失（仍是最优的）；n反复进行这种比较和替换，直到贪心解x和最优解y成为同一个解。证明n设X=(x1,x2,.,xn)是贪心解。n若所有的xi都是1，则X显然是最优解。n设j是使xj1的最小下标。有算法可知，对于1ij，xi=1；对于jin，xi=0；对于i=j，0 xi 1。n若X不是最优解，设Y=(y1,y2,.,yn)是最优解，即n设k是使ykxk的最小下标,即 x1=y1,x2=y2,x3=y3,xkyk,下面先来证明ykxk。nkj的情况 此时，xk=1。由于ykxk，所以yk 1，即ykj，有xi=0。若ykxk，由于 即则 (矛盾)所以，当k=j时，也有ykj的情况 此时，xk=0,由于ykxk，则有yk0。于是 (矛盾)说明kj是不可能的情况。现在，把yk增加到xk，即第k种物品的重量增加(xk-yk)wk，而从(yk+1,yk+2,.,yn)中减去同样多的量，使总重量保持为M。于是产生一个新的解Z=(z1,z2,.,zn)，其中 z1=x1,z2=x2,.,zk=xk,并且Z的总效益为由于当ki时，pk/wk pi/wi所以 因为Y是最优解，所以Z也是最优解。如果ZX，则重复上述替换步骤，每次得到的新解都是最优解。经有限步替换后，得到Z=X，证明X是最优解。例2 带期限的作业排序问题n问题描述n目标函数与约束条件n实例n量度标准n贪心解n证明贪心解是最优解n贪心算法问题描述 在一台机器上处理n个作业，每个作业可在单位时间内完成。每个作业i有截止期限di，当且仅当作业i在截止期限di内完成，可获得效益pi。为了获得最大效益值，应该选择哪些作业，并按怎样的顺序进行处理？目标函数与约束条件n目标函数 n约束条件 J中每个作业在各自截止期限内完成。实例n作业数 n=4n效益值 P=（100，10，15，20）n截止期限 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量度标准n用目标函数作量度标准。n使用这一标准，每次加入J中的作业一定在满足约束的条件下，使得获得最大增加量。n这就要求按pi非增次序来考虑每个作业。贪心解J1;for i 2 to n do if J i可行 then J J i endifendfor;由此得到的解称为贪心解。在这个解中，集合J包含了所有能在各自截止期限之内完成的作业。至于这些作业应该按怎样的顺序处理，暂且不管它。证明贪心解是最优解n设J是贪心解,I是最优解，JI。因为I是最优解，可排斥 ；由贪心工作方式，可排斥 。所以存在作业a和作业b，。n设a是使得 的一个具有最大效益值的作业。由贪心方法可得出结论：对任何满足条件 的作业b，都有papb。这是因为若papb，贪心方法会先于作业a考虑作业b，并把作业b放入贪心解J中。证明贪心解是最优解（续）n设SJ、SI是J、I的可行调度表，c是J和I中共有的作业，在SJ中c在时刻tj被调度，在SI中c在时刻ti被调度。SJ：c.SI:c 或则 SJ：c.SI：c 证明贪心解是最优解（续）n对于tjti的情况，在SI中作类似的处理。n如此反复进行，使两个调度表中相同的作业在相同的时刻调度。n把在SI中调度的每一个作业b（）换成在同一时刻在SJ中调度的作业a。n由于papb，于是最优解I在不损失效益值的情况下变成了贪心解J。因此，J也是最优解。如何判断作业集合J可行？n（结论）如果J是一个包含k个作业的可行解，则J中的这k个作业一定可以按期限值从小到大的顺序处理。n（意义）如果发现J中作业不能按期限值从小到大的顺序处理，则可断定J不是可行解。n（证明）如果J是可行解，则必然存在一个调度序列 V=v1v2.vk (vj 是第j个被调度的作业的编号)使得dvjj (1jk)。这个调度序列未必和满足条件 du1 du2.duk 的调度序列 U=u1u2.uk 相同。下面将证明V可以转换成U。结论的证明n设VU。令a是使得vaua的最小下标。U=u1u2.ua.uc.uk (满足条件 du1 du2.duk)V=v1v2.va.vb.vkn设uc=va，vb=ua，则必有ba，ca。因为 dva=ducdua=dvb 即dvadvb，所以可将序列V中的va和vb交换。交换后的V仍是一个可行的调度序列，而且与U更接近。反复进行这样的交换，就可以将V转换成U。例：例：已知有6个作业，各作业的截止期限和效益值如表所示。为了获得最大效益值，应该从中选择哪些作业，并按怎样的顺序处理？作业编号 截止期限 效益值 115239347433522614分析：分析：l 按效益值从大到小的顺序，依次考虑下列作业：2、3、1、6、4、5l 只能处理下列作业：1、2、3、4l 必须按下列顺序处理：1、2、4、3或 1、4、2、3 算法(带期限的作业排序问题)procedure JS(D,J,n,k)/*n个作业已按效益值从大到小的顺序编号个作业已按效益值从大到小的顺序编号;D1:n存放存放n个作业的期限值个作业的期限值;J1:k存放可行调度表存放可行调度表;从从n个作业中选出个作业中选出k个作业个作业,第第i个被调度的作业编号个被调度的作业编号是是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;endforend JS第5章 动态规划n问题特征n最优性原理n局限性n关键步骤n例1 多段图问题n例2 资源分配问题问题特征n是个求最优解的问题。n问题的求解过程可以分为若干个阶段；每个阶段要作出一个决策；在作每个决策时，不能孤立地考虑本阶段决策效果如何，而必须各阶段联系起来考虑，使之形成一个最优决策序列。n适合用动态规划方法求解的问题必须满足最优性原理（也称为问题的无后效性特征）最优性原理 假设问题的求解过程分为k个阶段，并且 d1,d2,.,di 是最优决策序列中的前i个决策。在作后续决策时，不必考虑前i个决策是如何作出的，只需考虑在作出决策di后的状态，只要后续决策相对于作出决策di后的状态是最优的，则它们相对于问题的初始状态也是最优的，即 d1,d2,.,di,.,dk是问题的一个最优决策序列。例n求a到f路径上边的权值之和最小的路径.适合用动态规划求解.n求a到f路径上边的权值之和除以4所的余数最小的路径.不适合用动态规划求解.afbdce2133231关键步骤n问：一个多阶段决策问题满足最优性原理，对解决该问题有什么用处？n答：减轻计算工作量。n关键步骤：列出递推关系式（动态规划方程）例1 多段图问题 143287611109125ts V1 V2 V3 V4 V5注:每条边有正的权值,图中没有标出.分析n设P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径，cost(i,j)是这条路径的成本。由最优性原理可以得出递推关系式：cost(i,j)=minc(j,L)+cost(i+1,L)LVi+1 E其中c(j,L)是有向边的权值。n用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+costLcj,L+costL取最小值的取最小值的L值值 cost j c j,r+costr;D j r /D j是是j的最优后继结点的最优后继结点 endfor;P1=1;Pk=n;/P j存放路径上第存放路径上第j个结点的序号个结点的序号 for j 2 to k-1 do P j DP j-1 endforend FGRAPH例2 资源分配问题n已知把数量为x的资源分配给项目i可获得利润Gi,x。现有n个资源，m个项目，应如何分配才能获得最大利润？n实例（资源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分别投资300,100,300万元,可获得最大利润68万元。分析nGi,j 第i个项目分得j个资源后可获得的利润；nFi,j 按最优方案将j个资源分配给前i个项目所获得的利润；nXi,j 按最优方案将j个资源分配给前i个项目后第i个项目分得的资源数。n显然，当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 n依次考虑给一个项目分配资源，给两个项目分配资源，给m个项目分配资源，分配资源数从1增加到n，最后得到利润最大值Fm,n。n最优分配方案可通过倒推的方法得到：第m个项目分得资源数 Xm,n;第m-1个项目分得资源数 Xm-1,n1,其中,n1=n-Xm,n;第m-2个项目分得资源数 Xm-2,n2,其中,n2=n1-Xm-1,n1;.121520212430362224262830333418222628303436121520212430361234567 1 2 3 4 5 6 7 (百万元)GFX123123123给第一个项目分配资源给第一个项目分配资源12152021243036222426283033341822262830343612152021243036 22 34374244464812345671111212 1 2 3 4 5 6 7 (百万元)GFX123123123给前两个项目分配资源给前两个项目分配资源计算过程12152021243036222426283033341822262830343612152021243036 22 34374244464818405256606468123456711112121112123 1 2 3 4 5 6 7 (百万元)GFX123123123给所有项目分配资源给所有项目分配资源计算过程 通过倒推的方法得到最优分配方案：第3个项目分得资源数 X3,7=3(百万元);第2个项目分得资源数 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 endforend BUDGET算法(输出最优分配方案)procedure PRINT(m,n)if m1 then PRINT(m-1,n-Xm,n)endif;write Xm,nend PRINT第6章 回溯法n问题特征n启发式搜索n约束条件n解答树n算法框架n例1 n后问题n例2 图着色问题问题特征 这是一种用于求问题最优解或全体解的方法。问题的解可以表示成一个n元组 (x1,x2,.,xn)，它满足某种约束条件，并且通常使某个规范函数 P(x1,x2,.,xn)取极值。启发式搜索n盲目搜索法 假设xi的取值有mi种，构造 m1m2.mn 个元组（它们都可能是解），逐一测试。n启发式搜索法 不断地用修改过的规范函数（限界函数）Pi(x1,x2,.,xi)去测试正在构造中的n元组的部分向量 (x1,x2,.,xi)，看其是否可能导致问题的解，如果判定(x1,x2,.,xi)不可能导致解，就不再进一步测试(xi+1,xi+2,.,xn)约束条件n构成问题解的元组必须满足一组综合的约束条件。约束条件有两种类型。n显式约束 限定每个xi只能从一个给定的集合上取值。满足显式约束条件的所有元组构成问题的一个可能解的集合。n隐式约束 描述各个xi之间的相互关系。满足隐式约束条件的元组是真正要求的解。解答树 这是一种用来表示问题求解过程的树：根结点下面的边表示x1的取值，第二层结点下面的边表示x2的取值，从根结点到底层每个树叶结点的路径构成一个n元组(x1,x2,.,xn)，它可能是一个解。树叶结点称为可能的答案结点。用于描述4后问题求解过程的解答树X=(2,4,1,3)X=(3,1,4,2)解答树中的三种结点n活结点 已生成的一个结点，它的子结点尚未全部生成。nE结点 当前正在扩展（正在生成子结点）的活结点。n死结点 不再进一步扩展的结点。两种扩展结点的方法n方法1 当前的E结点R一旦生成一个子结点C，C就变成新的E结点；当检测了以C为根的子树之后，R再次成为E结点。n方法2 一个E结点一直保持到变成死结点为止。n回溯法 使用限界函数,并用第一种方法扩展结点.n分枝限界法 使用限界函数,并用第二种方法扩展结点.算法框架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);endforend BACKTRACK;调用方式调用方式:BACKTRACK(1)例1 n后问题n在一个nn的国际象棋棋盘上放置n个皇后，找出使它们不能互相攻击的所有方案。n解的表示形式 (x1,x2,.,xn)，其中xi表示把第i个皇后放在第i行的xi列上。n显式约束条件 xi1,2,.,n n隐式约束条件 没有两个xi可以相同；没有两个皇后可以在同一条斜线上。n限界函数 隐式约束条件。如何判断两个皇后是否在同一条斜线上?n如果两个皇后在同一条”斜线上，则它们的（行下标值-列下标值）相同；n如果两个皇后在同一条”/”斜线上，则它们的（行下标值+列下标值）相同。n当ik时，xi和xk在同一条斜线上的条件是 i-xi=k-xk 或则 i+xi=k+xk即|i-k|=|xi-xk|算法procedure PLACE(k)/假设假设X1:k-1已赋值已赋值.PLACE(k)判断第判断第k个皇后是否可以放在个皇后是否可以放在/第第k行的第行的第Xk列上列上.integer X1:n,i;i1;while ik do if Xi=Xk 或则或则|Xi-Xk|=|i-k|then return(FALSE)endif;ii+1 endwhile;return(TRUE)endPLACEprocedure NQUEENS(k)/试放第试放第k个皇后个皇后 if kn then Xk0;while Xkn do XkXk+1;if PLACE(k)=TRUE then if k=n then print(X)else NQUEENS(k+1)endif endif endwhile endifend NQUEENS例2 图着色问题 平面地图由n个封闭区域构成。要求用尽可能少的颜色对地图着色，相邻的区域用不同的颜色。分析n用无向图表示平面地图:结点表示封闭区域,边表示相邻关系。n用邻接矩阵表示无向图。3241562536140 1 1 1 0 0 1 0 1 0 1 01 1 0 1 1 11 0 1 0 0 10 1 1 0 0 00 0 1 1 0 0平面地图无向图邻接矩阵分析（续）n解的形式 (x1,x2,.,xn)其中整数值xi表示结点i所用颜色编号。n显式约束条件 xi1,2,.,mn隐式约束条件 若(k,i)是一条边（即区域k和区域i是相邻区域），则 xkxin限界函数 隐式约束条件。n给每个结点着色时，都尽量给编号值较小的颜色。与示例对应的解答树(局部)x6=1 4 1 4 1 2 1 2 1 3 1 3 1 2 1 2 x5=1 4 1 4 1 3 1 3 x4=2 4 2 3x3=3 4 x2=2 3 4 x1=1 2 3 4 每个树叶都是答案结点.算法procedure MCOLORING(k)/对结点对结点k着色着色 loop NEXTVALUE(k);if Xk=0 then exit endif;if k=n then print(X)else MCOLORING(k+1)endif endloopend MCOLORING调用方式调用方式 MCOLORING(1)。procedure NEXTVALUE(k)/在X1:k-1已赋值的情况下,给Xk分配一个不同于X1:k-1的最小值,如果做不到,则给Xk赋值0 loop Xk(Xk+1)%(m+1)/试下一种颜色 if Xk=0 then return endif;/全部颜色用完 for i1 to k-1 do if Gk,i=1并且Xk=Xi then exit endif endfor;if i=k then return endif;/找到一种颜色 endloop /试着找下一种颜色endNEXTVALUE 谢谢各位!结束