算法分析与设计-复习提纲课件

算法分析与设计常熟理工学院计算机学院刘在德算法分析与设计常熟理工学院计算机学院1第1章绪论掌握三种渐近符号（O、Ω、Θ）的含义；会用三种渐近符号表示算法的时间复杂度；会用扩展递归技术分析算法时间的复杂性；对于表示算法时间的简单递推式，能够用扩展递归技术求出最终结果。P15：例1.6P18：实验1P22：习题1.7第1章绪论掌握三种渐近符号（O、Ω、Θ）的含义；2三种渐近符号的含义大O符号：若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))

大Ω符号：若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≥c×g(n)，则称T(n)=Ω(g(n))Θ符号：若存在三个正的常数c1、c2和n0，对于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n)，则称T(n)=Θ(f(n))

三种渐近符号的含义大O符号：若存在两个正的常数c和n0，对于3渐近符号表示算法时间复杂度[定理1.1]若T(n)=amnm+am-1nm-1+···a1n+a0(am>0)，则有T(n)=O(nm)，且T(n)=Ω(nm)，从而T(n)=Θ(nm)[例]

T(n)＝5n2＋8n＋1

当n≥1时，5n2＋8n＋1≤5n2＋8n＋n＝5n2＋9n≤5n2＋9n2≤14n2＝O(n2)

当n≥1时，5n2＋8n＋1≥5n2＝Ω(n2)

∴当n≥1时，14n2≥5n2＋8n＋1≥5n2

则：5n2＋8n＋1＝Θ(n2)

渐近符号表示算法时间复杂度[定理1.1]若T(n)=am4用扩展递归技术分析算法时间的复杂性扩展递归技术：将递推关系式中右边项根据递推式进行逐次替换，得到求和表达式[例]

用扩展递归技术分析算法时间的复杂性扩展递归技术：将递推关系式5第2章NP完全理论对于简单的判定问题，会画判定树。判定树（DecisionTrees）是一棵二叉树：它的每一个内部结点对应一个形如x≤y的比较，如果关系成立，则控制转移到该结点的左子树，否则，控制转移到该结点的右子树，它的每一个叶子结点表示问题的一个结果。

第2章NP完全理论对于简单的判定问题，会画判定树。6[例]对三个数进行排序的判定树[例]对三个数进行排序的判定树7第3章蛮力法掌握改进的串匹配算法——KMP算法理解n个元素的生成排列对象理解n个元素组成的集合的生成子集理解0/1背包问题理解TSP问题第3章蛮力法掌握改进的串匹配算法——KMP算法8KMP算法KMP算法思路：如果某趟在Si和Tj匹配失败后，指针i不回溯；模式T向右滑动至某个位置k，使得tk对准si继续进行匹配。怎么求k？模式T=“t1t2…tm”中的每一个字符tj都对应一个k，显然k与S无关。用next[j]表示tj对应的k值，则t1…tk-1既是t1…tj-1的真前缀，又是t1…tj-1的真后缀的最长子串，称k是tj的前缀函数值，它等于最长子串长度加1。KMP算法KMP算法思路：9next数组的定义next数组定义如下：t1t2t3t4t5t6ababac真前缀真后缀∵t1=t5,t1t2t3=t3t4t5∴a和aba都是ababa的真前缀和真后缀，但aba的长度最大∴next[6]=3+1=4，即当t6和si匹配失败后，将t4和si比较一个求k的例子：next数组的定义next数组定义如下：t1t2t3t4t510next数组的求法：已求出next[1],…,next[j]，咋求next[j+1]?设k是t[j]的前缀函数值，从而有

t1…t2tk-1=tj-k+1tj-k+2…tj-1比较tk和tj，得2种情况：(1)tk=tj：说明t1…tk-1tk=tj-k+1…tj-1tj，则next[j+1]=k+1；(2)tk≠tj：此时要找出t1…tj-1的后缀中第2大真前缀next[next[j]]=next[k],t1…tnext[k]-1=tj-next[k]+1…tj-1，再比较tnext[k]和tj，又会出现2种情况：next数组的求法：已求出next[1],…,next[j11next数组的求法：当tnext[k]=tj时，与(1)类似，next[j+1]=next[k]+1；当不等时，找第3大真前缀，重复(2)的过程，直至找到t1…tj-1后缀中的最大真前缀，或确定t1…tj-1的后缀中没有最大真前缀，此时next[j+1]=1。next数组的求法：当tnext[k]=tj时，与(1)类似12算法3.4KMP算法中求next数组voidGetNext(charT[],intnext[])

{//下标从1开始next[1]=0;j=1;k=0;while(j<=m)If((k==0)||(T[j]==T[k])){j++;k++;next[j]=k;}elsek=next[k]}算法3.4KMP算法中求next数组voidGetNe13算法3.5KMP算法1.在串S和T中分别设定比较的起始下标i和j；2.循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕2.1如S[i]=T[j]，则继续比较S和T的下一字符；否则2.2将j向右滑动到next[j]位置，即j=next[j]；2.3如果j=0，则将i和j分别加1，准备下一趟比较；3.如果T中所有字符均比较完毕，则返回匹配的起始下标，否则返回0。算法3.5KMP算法1.在串S和T中分别设定比较的起始14生成排列对象思路：假定已生成了{1,2,…,n-1}的所有(n-1)!个排列，可以把n插入到n-1个元素的每一种排列的n个位置中去，得到问题规模为n的所有排列。这时排列总数为n(n-1)!=n!。时间复杂性：O(n!)算法3.9生成排列对象（伪代码）1.生成初始排列{1}；2.for(i=2;i<=n;i++)for(j=1;j<=(i-1)!;j++)for(k=i;k>=1;k--)

将i插入到第j个排列中的第k个位置；生成排列对象思路：假定已生成了{1,2,…,n-1}的所有(15生成子集思路：n个元素组成的集合A={a1,a2,…,an}的所有2n个子集与长度为n的所有2n个比特串之间存在一一对应关系。建立这种关系的方法是为每个子集指定一个比特串b1b2…bn，如果ai属于该子集，则bi=1，否则bi=0(1≤i≤n)。如3个元素组成的集合，比特串110表示{a1a2}，比特串000表示Φ。生成子集思路：n个元素组成的集合A={a1,a2,…,an}16算法3.10生成子集1.初始化一个长度为n的比特串s=00…0，并将对应的子集输出；2.for(i=1;i<2n;i++)2.1s++;2.2将s对应的子集输出；时间复杂性：O(2n)。算法3.10生成子集1.初始化一个长度为n的比特串s170/1背包问题0/1背包问题：给定n个重量为{w1,w2,…wn}、价值为{v1,v2,…,vn}的物品和1个容量为C的背包，求这些物品中的一个最有价值的子集，并能够装到背包中。思路：考虑给定n个物品集合的所有子集，找出所有可能的子集(总重量不超过背包容量的子集)，计算每个子集的价值，从中找出价值最大子集。0/1背包问题0/1背包问题：给定n个重量为{w1,w2,…18TSP问题TSP问题：旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所经过的路程最短。思路：1)找出所有的Hamilton回路，并计算每个回路的路径长度；2)从中选择路径长度最短的回路。TSP问题TSP问题：旅行家要旅行n个城市然后回到出发城市，19TSP问题时间复杂性：(n-1)!/2(出发城市固定，实际旅游了n-1个城市)。例子：abdca11acdba11TSP问题时间复杂性：(n-1)!/2(出发城市固定，实际20第4/5章分/减治法理解分治法的基本思路及在典型问题中的应用掌握递归方法在算法设计中的应用。掌握减治法在经典问题中的应用习题4.3习题4.4习题5.2第4/5章分/减治法理解分治法的基本思路及在典型问题中21分治法的求解过程

一般来说，分治法的求解过程由以下三个阶段组成：（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。分治法的求解过程一般来说，分治法的求解过程由以22子问题的规模是n/2子问题的解原问题的解原问题的规模是n减治法的设计思想子问题子问题的解23递归递归（Recursion）就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。递归有两个基本要素：⑴边界条件：确定递归到何时终止；⑵递归模式：大问题是如何分解为小问题的。递归递归（Recursion）就是子程序（或函数24一个递归和减治法混合应用例子----俄式乘法习题5的第2题intrmul(intn,intm)/*方法1：递归法*/{inthalfn,bm,product;if(n==0)return0;if(n==1)returnm;一个递归和减治法混合应用例子----俄式乘法习题5的第2题25if(n%2==0){halfn=n>>1;bm=m<<1;product=rmul(halfn,bm);}if(n%2==1){halfn=n>>1;bm=m<<1;product=rmul(halfn,bm)+m;}returnproduct;}if(n%2==0)26intrmul(intn,intm)/*方法2：非递归法*/

{intresult=0;while(n!=0){if(n%2==0)m=m<<1;else{result=result+m;m=m<<1;}n=n>>1;}returnresult;}intrmul(intn,intm)/*方27第6章动态规划法掌握动态规划法的设计思想掌握动态规划法在TSP问题和0/1背包问题中的应用。给出一个TSP或者0/1背包问题的实例，能够写出它的动态规划过程。P134：实验6第6章动态规划法掌握动态规划法的设计思想28动态规划法的设计思想

动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。动态规划法的设计思想动态规划法将待求解问题分解成若29原问题的解原问题……填表子问题1子问题2子问题n动态规划法的求解过程原问题的解原问题……填表子问题1子30n=5时分治法计算斐波那契数的过程。

F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例：计算斐波那契数：n=5时分治法计算斐波那契数的过程。F(5)F(4)F(33101234567890112358132134动态规划法求解斐波那契数F(9)的填表过程：注意到，计算F(n)是以计算它的两个重叠子问题

F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。

01234567890112358132134动态规划法求解32TSP问题

TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。各个城市间的距离可以用代价矩阵来表示。C=∞3675∞2364∞2375∞带权图的代价矩阵TSP问题TSP问题是指旅行家要旅行n个城市，要求33假设从顶点i出发，令d(i,V')表示从顶点i出发经过V'中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，V'＝V－{i}，于是，TSP问题的动态规划函数为：d(i,V')=min{cik+d(k,V－{k})}(k∈V')（式6.5）d(k,{})=cki(k≠i)（式6.6）假设从顶点i出发，令d(i,V')表示从顶点i出发经过V'34这是最后一个阶段的决策，而：

d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}这一阶段的决策又依赖于下面的计算结果：d(1,{2})=c12+d(2,{})d(2,{3})=c23+d(3,{})d(3,{2})=c32+d(2,{})d(1,{3})=c13+d(3,{})d(2,{1})=c21+d(1,{})d(3,{1})=c31+d(1,{})

从城市0出发经城市1、2、3然后回到城市0的最短路径长度是：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}而下式可以直接获得（括号中是该决策引起的状态转移）：d(1,{})=c10=5(1→0)d(2,{})=c20=6(2→0)d(3,{})=c30=3(3→0)这是最后一个阶段的决策，而：从城市0出发经城市1、2、3然35再向前倒推，有：d(1,{2})=c12+d(2,{})=2+6=8(1→2)d(1,{3})=c13+d(3,{})=3+3=6(1→3)d(2,{3})=c23+d(3,{})=2+3=5(2→3)d(2,{1})=c21+d(1,{})=4+5=9(2→1)d(3,{1})=c31+d(1,{})=7+5=12(3→1)d(3,{2})=c32+d(2,{})=5+6=11(3→2)再向前倒退，有：d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}=min{2+5,3+11}=7(1→2)d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}=min{4+6,2+12}=10(2→1)d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}=min{7+8,5+9}=14(3→2)最后有：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}=min{3+7,6+10,7+14}=10(0→1)所以，从顶点0出发的TSP问题的最短路径长度为10，路径是0→1→2→3→0。

再向前倒推，有：d(3,{1,2})=min{c31+d36算法6.1——TSP问题1．for(i=1;i<n;i++)//初始化第0列d[i][0]=c[i][0];2．for(j=1;j<2n-1-1;j++)for(i=1;i<n;i++)//依次进行第i次迭代if(子集V[j]中不包含i)对V[j]中的每个元素k，计算d[i][j]=min(c[i][k]+d[k][j-1]);3．对V[2n-1-1]中的每一个元素k，计算d[0][2n-1-1]=min(c[0][k]+d[k][2n-1-2]);4．输出最短路径长度d[0][2n-1-1];伪代码设顶点之间的代价存放在数组c[n][n]中，动态规划法求解TSP问题的算法如下：

算法6.1——TSP问题伪代码设顶点之间的代价存放在370/1背包问题

在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：

（式6.9）（式6.10）于是，问题归结为寻找一个满足约束条件式6.9，并使目标函数式6.10达到最大的解向量X=(x1,x2,…,xn)。0/1背包问题在0/1背包问题中，物品i或者38

0/1背包问题可以看作是决策一个序列(x1,x2,…,xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1,…,xi-1)，在决策xi时，问题处于下列两种状态之一：（1）背包容量不足以装入物品i，则xi=0，背包不增加价值；（2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi。这两种情况下背包价值的最大者应该是对xi决策后的背包价值。令V(i,j)表示在前i(1≤i≤n)个物品中能够装入容量为j（1≤j≤C）的背包中的物品的最大值，则可以得到如下动态规划函数：V(i,0)=V(0,j)=0（式6.11）（式6.12）0/1背包问题可以看作是决策一个序列(x1,x2,39式6.11表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。式6.12的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：（1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；（2）如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。

式6.11表明：把前面i个物品装入容量为0的背包和把40根据动态规划函数，用一个(n+1)×(C+1)的二维表V，V[i][j]表示把前i个物品装入容量为j的背包中获得的最大价值。

0例如，有5个物品，其重量分别是{2,2,6,5,4}，价值分别为{6,3,5,4,6}，背包的容量为10。x5=1x4=0x3=0x2=1x1=1

012345678910

00000000000w1=2v1=6100666666666w2=2v2=3200669999999w3=6v3=5300669999111114w4=5v4=44006699910111314w5=5v5=6500669912121515150根据动态规划函数，用一个(n+1)×(C+1)的二维表41按下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。为了确定装入背包的具体物品，从V(n,C)的值向前推，如果V(n,C)>V(n-1,C)，表明第n个物品被装入背包，前n-1个物品被装入容量为C-wn的背包中；否则，第n个物品没有被装入背包，前n-1个物品被装入容量为C的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。由此，得到如下函数：

（式6.13）

按下述方法来划分阶段：第一阶段，只装入前1个物品，确42

设n个物品的重量存储在数组w[n]中，价值存储在数组v[n]中，背包容量为C，数组V[n+1][C+1]存放迭代结果，其中V[i][j]表示前i个物品装入容量为j的背包中获得的最大价值，数组x[n]存储装入背包的物品，动态规划法求解0/1背包问题的算法如下：

算法6.3——0/1背包问题

intKnapSack(intn,intw[],intv[]){for(i=0;i<=n;i++)//初始化第0列V[i][0]=0;for(j=0;j<=C;j++)//初始化第0行V[0][j]=0;for(i=1;i<=n;i++)//计算第i行，进行第i次迭代for(j=1;j<=C;j++)if(j<w[i])C++描述设n个物品的重量存储在数组w[n]中，价值存43算法6.3——0/1背包问题V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);j=C;//求装入背包的物品for(i=n;i>0;i--){if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}returnV[n][C];//返回背包取得的最大价值}C++描述算法6.3——0/1背包问题C++描述44第7章贪心法掌握贪心法的设计思想掌握贪心法在TSP问题中的应用掌握贪心法在背包问题中的应用P155：实验7第7章贪心法掌握贪心法的设计思想45贪心法的求解过程

用贪心法求解问题应该考虑如下几个方面：（1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。贪心法的求解过程用贪心法求解问题应该考虑如下几个46

（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。

（4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。（5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。

（3）解决函数solution：检查解集合S是否构成问题47贪心法的一般过程Greedy(C)//C是问题的输入集合即候选集合{S={};//初始解集合为空集while(notsolution(S))//集合S没有构成问题的一个解{x=select(C);//在候选集合C中做贪心选择iffeasible(S,x)//判断集合S中加入x后的解是否可行S=S+{x};C=C-{x};}returnS;}贪心法的一般过程48TSP问题

最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。TSP问题最近邻点策略：从任意城市出发，每次在没有到过的城49(d)城市3→城市5(e)城市5→城市2(f)城市2→城市1最近邻点贪心策略求解TSP问题的过程25221543225221543232522154327363215432233215432C=∞33263∞73237∞25232∞36253∞(a)5城市的代价矩阵(b)城市1→城市4(c)城市4→城市3(d)城市3→城市5(e)城市5→城市50背包问题

给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?

背包问题给定n种物品和一个容量为C的背包，51

于是，背包问题归结为寻找一个满足约束条件式7.1，并使目标函数式7.2达到最大的解向量X=(x1,x2,…,xn)。设xi表示物品i装入背包的情况，根据问题的要求，有如下约束条件和目标函数：（式7.1）（式7.2）于是，背包问题归结为寻找一个满足约束条件式752三种看似合理的贪心策略：（1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。（2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。（3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。三种看似合理的贪心策略：5312050背包180190200(a)三个物品及背包(b)贪心策略1(c)贪心策略2(d)贪心策略350301020203020/30201010/203010例如，有3个物品，其重量分别是{20,30,10}，价值分别为{60,120,50}，背包的容量为50，应用三种贪心策略装入背包的物品和获得的价值如图所示。12050背包54第8章回溯法掌握回溯法的设计思想针对某一特定实例，会写出动态搜索过程，并画出搜索空间树，从而找到最优解0/1背包问题TSP问题第8章回溯法掌握回溯法的设计思想55

对于任何一个问题，可能解的表示方式和它相应的解释隐含了解空间及其大小。例如，对于有n个物品的0/1背包问题，其可能解的表示方式可以有以下两种：（1）可能解由一个不等长向量组成，当物品i(1≤i≤n)装入背包时，解向量中包含分量i，否则，解向量中不包含分量i，当n=3时，其解空间是：{(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)}（2）可能解由一个等长向量{x1,x2,…,xn}组成，其中xi=1(1≤i≤n)表示物品i装入背包，xi=0表示物品i没有装入背包，当n=3时，其解空间是：{(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}对于任何一个问题，可能解的表示方式和它相应的56为了用回溯法求解一个具有n个输入的问题，一般情况下，将其可能解表示为满足某个约束条件的等长向量X=(x1,x2,…,xn)，其中分量xi(1≤i≤n)的取值范围是某个有限集合Si={ai1,ai2,…,airi}，所有可能的解向量构成了问题的解空间。

为了用回溯法求解一个具有n个输入的问题，一般57问题的解空间一般用解空间树（SolutionSpaceTrees,也称状态空间树）的方式组织，树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，第1层到第2层的边上标出对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解。问题的解空间一般用解空间树（Solution58对于n=3的0/1背包问题，其解空间树如图8.2所示，树中的8个叶子结点分别代表该问题的8个可能解。

对物品1的选择对物品3的选择对物品2的选择1111110000000112345781112141531069对于n=3的0/1背包问题，其解空间树如图8.2所示，树中的59对于n=4的TSP问题，其解空间树如图8.3所示，树中的24个叶子结点分别代表该问题的24个可能解，例如结点5代表一个可能解，路径为1→2→3→4→1，长度为各边代价之和。

243422343413142412123312134131312321214241434322434123124134图8.3n=4的TSP问题的解空间树5710121517212326283133373942444749525457596264469111416202225273032363841434648515356586163381319242935404550556021834241123434对于n=4的TSP问题，其解空间树如图8.3所示，树60解空间树的动态搜索

回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。解空间树的动态搜索回溯法从根结点出发，按照深61例如，对于n=3的0/1背包问题，三个物品的重量为{20,15,10}，价值为{20,30,25}，背包容量为25，从图8.2所示的解空间树的根结点开始搜索，搜索过程如下：1不可行解价值=20价值=55价值=30价值=25价值=01111000000112811121415131069不可行解例如，对于n=3的0/1背包问题，三个物品的重量为{20,62再如，对于n=4的TSP问题，其代价矩阵如图8.5所示，

C=∞36712∞2886∞2376∞图8.5TSP问题的代价矩阵再如，对于n=4的TSP问题，其代价矩阵如图8.5所632344221231341313123212142414322434123124134图8.6TSP问题的搜索空间547544112746485153583813242935404550556021834241234123442212313413131232121424143264回溯法的求解过程

由于问题的解向量X=(x1,x2,…,xn)中的每个分量xi(1≤i≤n)都属于一个有限集合Si={ai1,ai2,…,airi}，因此，回溯法可以按某种顺序（例如字典序）依次考察笛卡儿积S1×S2×…×Sn中的元素。初始时，令解向量X为空，然后，从根结点出发，选择S1的第一个元素作为解向量X的第一个分量，即x1=a11，如果X=(x1)是问题的部分解，则继续扩展解向量X，选择S2的第一个元素作为解向量X的第2个分量，否则，选择S1的下一个元素作为解向量X的第一个分量，即x1=a12。依此类推，一般情况下，如果X=(x1,x2,…,xi)是问题的部分解，则选择Si+1的第一个元素作为解向量X的第i+1个分量时，有下面三种情况：回溯法的求解过程由于问题的解向量X=(x165（1）如果X=(x1,x2,…,xi＋1)是问题的最终解，则输出这个解。如果问题只希望得到一个解，则结束搜索，否则继续搜索其他解；（2）如果X=(x1,x2,…,xi＋1)是问题的部分解，则继续构造解向量的下一个分量；（3）如果X=(x1,x2,…,xi＋1)既不是问题的部分解也不是问题的最终解，则存在下面两种情况：①如果xi+1=ai＋1k不是集合Si＋1的最后一个元素，则令xi+1=ai＋1k＋1，即选择Si+1的下一个元素作为解向量X的第i+1个分量；②如果xi+1=ai＋1k是集合Si＋1的最后一个元素，就回溯到X=(x1,x2,…,xi)，选择Si的下一个元素作为解向量X的第i个分量，假设xi=aik，如果aik不是集合Si的最后一个元素，则令xi=aik＋1；否则，就继续回溯到X=(x1,x2,…,xi－1)；（1）如果X=(x1,x2,…,xi＋1)是问题的最终66回溯法的一般框架——迭代形式1．X={};2．flag=false;3．k=1;4．while(k>=1)4.1当(Sk没有被穷举)循环执行下列操作4.1.1xk=Sk中的下一个元素;4.1.2将xk加入X;4.1.3if(X为最终解)flag=true;转步骤5;4.1.4elseif(X为部分解)k=k+1;转步骤4;4.2重置Sk，使得下一个元素排在第1位;4.3k=k-1;//回溯5．ifflag输出解X;else输出“无解”;回溯算法的非递归迭代形式的一般框架如下：回溯法的一般框架——迭代形式回溯算法的非递归迭代形式67第9章分支限界法掌握分支限界法的设计思想针对某一特定实例，会写出动态搜索过程，并画出搜索空间树，从而找到最优解0/1背包问题TSP问题第9章分支限界法掌握分支限界法的设计思想68分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down,up]。然后，按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（以下简称表PT）中。依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。解空间树的动态搜索（2）分支限界法首先确定一个合理的限界函数，并根据69随着这个遍历过程的不断深入，表PT中所估算的目标函数的界越来越接近问题的最优解。当搜索到一个叶子结点时，如果该结点的目标函数值是表PT中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表PT中的结点，将超出目标函数界的结点丢弃，然后从表PT中选取使目标函数取得极值的结点继续进行扩展。随着这个遍历过程的不断深入，表PT中所估算的70例：0/1背包问题。假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序，结果如下：物品重量(w)价值(v)价值/重量(v/w)144010274263525543124例：0/1背包问题。假设有4个物品，其重量分别71

应用贪心法求得近似解为(1,0,0,0)，获得的价值为40，这可以作为0/1背包问题的下界。如何求得0/1背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第1个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：ub=W×(v1/w1)=10×10=100。于是，得到了目标函数的界[40,100]。

限界函数为：

应用贪心法求得近似解为(1,0,0,0)，获得72×w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11无效解w=4,v=40ub=70w=9,v=65ub=69w=4,v=40ub=64w=12无效解w=9,v=65ub=6523456789×1分支限界法求解0/1背包问题×w=0,v=0w=4,v=40w=0,v=0w=1173分支限界法求解0/1背包问题，其搜索空间如图9.1所示，具体的搜索过程如下：（1）在根结点1，没有将任何物品装入背包，因此，背包的重量和获得的价值均为0，根据限界函数计算结点1的目标函数值为10×10=100；（2）在结点2，将物品1装入背包，因此，背包的重量为4，获得的价值为40，目标函数值为40+(10-4)×6=76，将结点2加入待处理结点表PT中；在结点3，没有将物品1装入背包，因此，背包的重量和获得的价值仍为0，目标函数值为10×6＝60，将结点3加入表PT中；（3）在表PT中选取目标函数值取得极大的结点2优先进行搜索；

分支限界法求解0/1背包问题，其搜索空间如图74（4）在结点4，将物品2装入背包，因此，背包的重量为11，不满足约束条件，将结点4丢弃；在结点5，没有将物品2装入背包，因此，背包的重量和获得的价值与结点2相同，目标函数值为40+(10-4)×5=70，将结点5加入表PT中；（5）在表PT中选取目标函数值取得极大的结点5优先进行搜索；（6）在结点6，将物品3装入背包，因此，背包的重量为9，获得的价值为65，目标函数值为65+(10-9)×4=69，将结点6加入表PT中；在结点7，没有将物品3装入背包，因此，背包的重量和获得的价值与结点5相同，目标函数值为40+(10-4)×4＝64，将结点6加入表PT中；（4）在结点4，将物品2装入背包，因此，背包的重量为11，不75（7）在表PT中选取目标函数值取得极大的结点6优先进行搜索；（8）在结点8，将物品4装入背包，因此，背包的重量为12，不满足约束条件，将结点8丢弃；在结点9，没有将物品4装入背包，因此，背包的重量和获得的价值与结点6相同，目标函数值为65；（9）由于结点9是叶子结点，同时结点9的目标函数值是表PT中的极大值，所以，结点9对应的解即是问题的最优解，搜索结束。（7）在表PT中选取目标函数值取得极大的结点6优先进行搜索；76分支限界法的设计思想

假设求解最大化问题，解向量为X=(x1,x2,…,xn)，其中，xi的取值范围为某个有穷集合Si，|Si|=ri（1≤i≤n）。在使用分支限界法搜索问题的解空间树时，首先根据限界函数估算目标函数的界[down,up]，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。对这r1个孩子结点分别估算可能取得的目标函数值bound(x1)，其含义是以该孩子结点为根的子树所可能取得的目标函数值不大于bound(x1)，也就是部分解应满足：bound(x1)≥bound(x1,x2)≥…≥bound(x1,

x2,…,xk)≥…≥bound(x1,x2,…,xn)分支限界法的设计思想假设求解最大化问题，解77若某孩子结点的目标函数值超出目标函数的界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT中。从表PT中选取使目标函数取得极大值的结点作为下一次扩展的根结点，重复上述过程，当到达一个叶子结点时，就得到了一个可行解X=(x1,x2,…,xn)及其目标函数值bound(x1,x2,…,xn)。如果bound(x1,x2,…,xn)是表PT中目标函数值最大的结点，则bound(x1,x2,…,xn)就是所求问题的最大值，(x1,x2,…,xn)就是问题的最优解；如果bound(x1,x2,…,xn)不是表PT中目标函数值最大的结点，说明还存在某个部分解对应的结点，其上界大于bound(x1,x2,…,xn)。于是，用bound(x1,x2,…,xn)调整目标函数的下界，即令down=bound(x1,x2,…,xn)，并将表PT中超出目标函数下界down的结点删除，然后选取目标函数值取得极大值的结点作为下一次扩展的根结点，继续搜索，直到某个叶子结点的目标函数值在表PT中最大。若某孩子结点的目标函数值超出目标函数的界，则将该孩子78分支限界法求解最大化问题的一般过程分支限界法的一般过程1．根据限界函数确定目标函数的界[down,up]；2．将待处理结点表PT初始化为空；3．对根结点的每个孩子结点x执行下列操作3.1估算结点x的目标函数值value;3.2若(value>=down)，则将结点x加入表PT中；4．循环直到某个叶子结点的目标函数值在表PT中最大4.1i=表PT中值最大的结点；4.2对结点i的每个孩子结点x执行下列操作4.2.1估算结点x的目标函数值value;4.2.2若(value>=down)，则将结点x加入表PT中；4.2.3若(结点x是叶子结点且结点x的value值在表PT中最大)，则将结点x对应的解输出，算法结束；4.2.4若(结点x是叶子结点但结点x的value值在表PT中不是最大)，则令down=value，并且将表PT中所有小于value的结点删除；分支限界法求解最大化问题的一般过程分支限界法的一般过程79算法分析与设计常熟理工学院计算机学院刘在德算法分析与设计常熟理工学院计算机学院80第1章绪论掌握三种渐近符号（O、Ω、Θ）的含义；会用三种渐近符号表示算法的时间复杂度；会用扩展递归技术分析算法时间的复杂性；对于表示算法时间的简单递推式，能够用扩展递归技术求出最终结果。P15：例1.6P18：实验1P22：习题1.7第1章绪论掌握三种渐近符号（O、Ω、Θ）的含义；81三种渐近符号的含义大O符号：若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))

大Ω符号：若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≥c×g(n)，则称T(n)=Ω(g(n))Θ符号：若存在三个正的常数c1、c2和n0，对于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n)，则称T(n)=Θ(f(n))

三种渐近符号的含义大O符号：若存在两个正的常数c和n0，对于82渐近符号表示算法时间复杂度[定理1.1]若T(n)=amnm+am-1nm-1+···a1n+a0(am>0)，则有T(n)=O(nm)，且T(n)=Ω(nm)，从而T(n)=Θ(nm)[例]

T(n)＝5n2＋8n＋1

当n≥1时，5n2＋8n＋1≤5n2＋8n＋n＝5n2＋9n≤5n2＋9n2≤14n2＝O(n2)

当n≥1时，5n2＋8n＋1≥5n2＝Ω(n2)

∴当n≥1时，14n2≥5n2＋8n＋1≥5n2

则：5n2＋8n＋1＝Θ(n2)

渐近符号表示算法时间复杂度[定理1.1]若T(n)=am83用扩展递归技术分析算法时间的复杂性扩展递归技术：将递推关系式中右边项根据递推式进行逐次替换，得到求和表达式[例]

用扩展递归技术分析算法时间的复杂性扩展递归技术：将递推关系式84第2章NP完全理论对于简单的判定问题，会画判定树。判定树（DecisionTrees）是一棵二叉树：它的每一个内部结点对应一个形如x≤y的比较，如果关系成立，则控制转移到该结点的左子树，否则，控制转移到该结点的右子树，它的每一个叶子结点表示问题的一个结果。

第2章NP完全理论对于简单的判定问题，会画判定树。85[例]对三个数进行排序的判定树[例]对三个数进行排序的判定树86第3章蛮力法掌握改进的串匹配算法——KMP算法理解n个元素的生成排列对象理解n个元素组成的集合的生成子集理解0/1背包问题理解TSP问题第3章蛮力法掌握改进的串匹配算法——KMP算法87KMP算法KMP算法思路：如果某趟在Si和Tj匹配失败后，指针i不回溯；模式T向右滑动至某个位置k，使得tk对准si继续进行匹配。怎么求k？模式T=“t1t2…tm”中的每一个字符tj都对应一个k，显然k与S无关。用next[j]表示tj对应的k值，则t1…tk-1既是t1…tj-1的真前缀，又是t1…tj-1的真后缀的最长子串，称k是tj的前缀函数值，它等于最长子串长度加1。KMP算法KMP算法思路：88next数组的定义next数组定义如下：t1t2t3t4t5t6ababac真前缀真后缀∵t1=t5,t1t2t3=t3t4t5∴a和aba都是ababa的真前缀和真后缀，但aba的长度最大∴next[6]=3+1=4，即当t6和si匹配失败后，将t4和si比较一个求k的例子：next数组的定义next数组定义如下：t1t2t3t4t589next数组的求法：已求出next[1],…,next[j]，咋求next[j+1]?设k是t[j]的前缀函数值，从而有

t1…t2tk-1=tj-k+1tj-k+2…tj-1比较tk和tj，得2种情况：(1)tk=tj：说明t1…tk-1tk=tj-k+1…tj-1tj，则next[j+1]=k+1；(2)tk≠tj：此时要找出t1…tj-1的后缀中第2大真前缀next[next[j]]=next[k],t1…tnext[k]-1=tj-next[k]+1…tj-1，再比较tnext[k]和tj，又会出现2种情况：next数组的求法：已求出next[1],…,next[j90next数组的求法：当tnext[k]=tj时，与(1)类似，next[j+1]=next[k]+1；当不等时，找第3大真前缀，重复(2)的过程，直至找到t1…tj-1后缀中的最大真前缀，或确定t1…tj-1的后缀中没有最大真前缀，此时next[j+1]=1。next数组的求法：当tnext[k]=tj时，与(1)类似91算法3.4KMP算法中求next数组voidGetNext(charT[],intnext[])

{//下标从1开始next[1]=0;j=1;k=0;while(j<=m)If((k==0)||(T[j]==T[k])){j++;k++;next[j]=k;}elsek=next[k]}算法3.4KMP算法中求next数组voidGetNe92算法3.5KMP算法1.在串S和T中分别设定比较的起始下标i和j；2.循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕2.1如S[i]=T[j]，则继续比较S和T的下一字符；否则2.2将j向右滑动到next[j]位置，即j=next[j]；2.3如果j=0，则将i和j分别加1，准备下一趟比较；3.如果T中所有字符均比较完毕，则返回匹配的起始下标，否则返回0。算法3.5KMP算法1.在串S和T中分别设定比较的起始93生成排列对象思路：假定已生成了{1,2,…,n-1}的所有(n-1)!个排列，可以把n插入到n-1个元素的每一种排列的n个位置中去，得到问题规模为n的所有排列。这时排列总数为n(n-1)!=n!。时间复杂性：O(n!)算法3.9生成排列对象（伪代码）1.生成初始排列{1}；2.for(i=2;i<=n;i++)for(j=1;j<=(i-1)!;j++)for(k=i;k>=1;k--)

将i插入到第j个排列中的第k个位置；生成排列对象思路：假定已生成了{1,2,…,n-1}的所有(94生成子集思路：n个元素组成的集合A={a1,a2,…,an}的所有2n个子集与长度为n的所有2n个比特串之间存在一一对应关系。建立这种关系的方法是为每个子集指定一个比特串b1b2…bn，如果ai属于该子集，则bi=1，否则bi=0(1≤i≤n)。如3个元素组成的集合，比特串110表示{a1a2}，比特串000表示Φ。生成子集思路：n个元素组成的集合A={a1,a2,…,an}95算法3.10生成子集1.初始化一个长度为n的比特串s=00…0，并将对应的子集输出；2.for(i=1;i<2n;i++)2.1s++;2.2将s对应的子集输出；时间复杂性：O(2n)。算法3.10生成子集1.初始化一个长度为n的比特串s960/1背包问题0/1背包问题：给定n个重量为{w1,w2,…wn}、价值为{v1,v2,…,vn}的物品和1个容量为C的背包，求这些物品中的一个最有价值的子集，并能够装到背包中。思路：考虑给定n个物品集合的所有子集，找出所有可能的子集(总重量不超过背包容量的子集)，计算每个子集的价值，从中找出价值最大子集。0/1背包问题0/1背包问题：给定n个重量为{w1,w2,…97TSP问题TSP问题：旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所经过的路程最短。思路：1)找出所有的Hamilton回路，并计算每个回路的路径长度；2)从中选择路径长度最短的回路。TSP问题TSP问题：旅行家要旅行n个城市然后回到出发城市，98TSP问题时间复杂性：(n-1)!/2(出发城市固定，实际旅游了n-1个城市)。例子：abdca11acdba11TSP问题时间复杂性：(n-1)!/2(出发城市固定，实际99第4/5章分/减治法理解分治法的基本思路及在典型问题中的应用掌握递归方法在算法设计中的应用。掌握减治法在经典问题中的应用习题4.3习题4.4习题5.2第4/5章分/减治法理解分治法的基本思路及在典型问题中100分治法的求解过程

一般来说，分治法的求解过程由以下三个阶段组成：（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。分治法的求解过程一般来说，分治法的求解过程由以101子问题的规模是n/2子问题的解原问题的解原问题的规模是n减治法的设计思想子问题子问题的解102递归递归（Recursion）就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。递归有两个基本要素：⑴边界条件：确定递归到何时终止；⑵递归模式：大问题是如何分解为小问题的。递归递归（Recursion）就是子程序（或函数103一个递归和减治法混合应用例子----俄式乘法习题5的第2题intrmul(intn,intm)/*方法1：递归法*/{inthalfn,bm,product;if(n==0)return0;if(n==1)returnm;一个递归和减治法混合应用例子----俄式乘法习题5的第2题104if(n%2==0){halfn=n>>1;bm=m<<1;product=rmul(halfn,bm);}if(n%2==1){halfn=n>>1;bm=m<<1;product=rmul(halfn,bm)+m;}returnproduct;}if(n%2==0)105intrmul(intn,intm)/*方法2：非递归法*/

{intresult=0;while(n!=0)