计算理论与算法分析设计：总复习

计算理论与算法总复习成绩计算方法平时成绩30%上机题目平时作业平时考勤期末成绩70%算法题中，严格按照题目要求给出算法代码、算法思想、测试用例的求解过程。如果题目没有明确要求给出算法代码，那么不需要给出。2考题类型判断题：10分.5个填空题：30分.10个大题：60分.5个左右3CH1算法概述算法的五个特征1）有穷性2）确定性3）输入4）输出5）可行性算法的定义:Informally,analgorithmisanywell-definedcomputationalprocedurethattakessomevalue,orsetofvalues,asinputandproducessomevalue,orsetofvalues,asoutput.Analgorithmisthusasequenceofcomputationalstepsthattransformtheinputintotheoutput.

5O、o、、、第一种理解方法设f和g是定义域为自然数N上的函数f(n)=O(g(n))

渐近上界记号O

若存在正数c和n0使得对一切n

n0

有0f(n)cg(n)f(n)=(g(n))

渐近下界记号

若存在正数c和n0使得对一切n

n0有0cg(n)f(n)f(n)=o(g(n))

非紧上界记号o

若对任意正数c存在n0使得对一切n

n0有0f(n)<cg(n)f(n)=(g(n))

非紧下界记号

若对任意正数c存在n0使得对一切n

n0有0cg(n)<f(n)f(n)=(g(n))

紧渐近界记号

f(n)=O(g(n))且f(n)=(g(n))6渐近分析中函数比较f(n)=O(g(n))

ab;f(n)=

(g(n))

ab;f(n)=

(g(n))

a=b;f(n)=o(g(n))

a<b;f(n)=

(g(n))

a>b.O、o、、、第二种理解方法求复杂性函数阶的极限方法例如，f(n)=n2/4,g(n)=n2,则n2/4=θ(n2)f(n)=logn,g(n)=n,则logn=o(n)8标准复杂性函数的比较O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)多项式时间阶指数时间阶一个算法的时间复杂性如果是O(nk)(k为有理数），则称此算法需要多项式时间。有效算法以多项式时间为限界的算法称为有效算法9标准复杂性函数的比较O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)注意：1）不能划等号2）以下若无特殊声明，log是以2为底的对数3）上式只有在n较大的时候成立O(1)的含义？计算时间由一个常数（零次多项式）来限界多项式时间阶指数时间阶10TimetoFinishInputSize(n)O(nx)O(n)O(1)O(lgn)O(an)O(n

lgn)11例例：算法A1,A2的时间复杂性分别是n,2n,设100μs是一个单位时间，求A1,A2在1s内能处理的问题规模。已知lg2=0.301T(n)=nT(n)*10-4=1即n*10-4=1所以n=

104

12例假设某算法在输入规模为n的时间复杂性为T(n)=3*2n。在某台计算机上实现并完成该算法的时间为t秒。现在另一计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？13例解：设新机器用同一算法内能解输入规模为n1的问题，那么有3*2n=3*2n1/64，解得n1=n+6.14CH2分治法

基本思想：将问题分解成若干个子问题，然后求解子问题，由此得到原问题的解。即“分而治之”

divide-and-conquer

把输入分成与原问题类型相同的多个子问题16分治法是一个递归地求解问题的过程分治法在每一层递归上有三个步骤分解:通过某种方法,将原问题分解成若干个规模较小,相互独立,与原问题形式相同的子问题解决:若子问题规模小到可以直接解决(称为基本问题),则直接解决,否则把子问题进一步分解，递归求解合并:通过某种方法,将子问题的解合并为原问题的解17分治法的抽象过程divide-and-conquer(S){if(small(S))return(adhoc(S));divideSintosmallersubsetS1,S2,…,Si,…Sk;for(i=1;i<=k;i++)yi

←divide-and-conquer(Si);returnmerge(y1,y2,…,yi,…,yk);}18例1用分治法求n个元素集合S中的最大、最小元素。假设n=2m。要求每次平分成2个子集。voidmaxmin(intA[],int&e_max,int&e_min,intlow,inthigh)2.{3.intmid,x1,y1,x2,y2;4.if((high-low<=1)){5.if(A[high]>A[low]){6.e_max=A[high];7.e_min=A[low];8.}9.else{10.e_max=A[low];11.e_min=A[high];12.}13.}1914.else{15.mid=(low+high)/2;16.maxmin(A,&x1,&y1,low,mid);17.maxmin(A,&x2,&y2,mid+1,high);18.e_max=max(x1,x2);19.e_min=min(y1,y2);20.}21.}T(n)=1n=2n>22T(n/2)+220T(n)=2T(n/2)+2=2[2T(n/22)+2]+2=22T(n/22)+2(1+2)=23T(n/23)+2(1+2+22)=…=2m-1T(2)+2(1+2+…n=2m+2m-2)=2m-1+2[1(1-2m-1)/(1-2)]=2m-1+2m-2=3n/2-221

用分治法求n个元素集合S中的最大、最小元素。写出算法，并分析时间复杂性（比较次数）。假设n=3m。要求每次平分成3个子集。T(n)=n=3n>33T(n/3)+43T(n)=5n/3-2平分成2个子集T(n)

=3n/2-222归并排序（MergeSort)voidMergeSort(intA[],B[],intl,intr){ if(l==r) return; intm=(l+r)/2; MergeSort(A,l,m); MergeSort(A,m+1,r); Merge(A,B,l,m,r);//合并到数组B Copy(A,B);//复制回数组A}T(n)=n=2n>22T(n/2)+cn123主定理简化版T(n)=n=2n>2aT(n/c)+bnxdT(n)=a<cx

(nxlogn)

(nx)a=cxa>cxT(n)=n=2n>22T(n/2)+cn1归并排序

(nlogn)24T(n)=1n=2n>22T(n/2)+2?快排序（QuickSort)快排序—算法思想取序列的一个元素作为轴，利用这个轴把序列分成三段：左段，中段(轴),和右段,使左段中各元素都小于等于轴，右段中各元素都大于等于轴。(这个过程称做对序列的划分)左段和右段的元素可以独立排序,将排好序的三段合并到一起即可上面的过程可以递归地执行，直到每段的长度为125快排序---划分过程

3865977613274949lowhighpivot=49

01234567high38659776134927low27389776134965high27389776654913low27381376654997high49=low26大整数乘法(1962年)由X=A2n/2+B,Y=C2n/2+D则

XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+BC)2n/2+BD=AC2n+((A-B)(D-C)+AC+BD)2n/2+BD计算成本：3次n/2位乘法，6次不超过n位加减法，2次移位，所有加法和移位共计O(n)次运算。由此可得，T(n)=O(nlog3)=O(n1.59)这种思想同样可以用于十进制数的乘法中。1n=13T(n/2)+cnn>1T(n)=27求第k小的元素longSelect(k,S){if(|S|≤38){将S中的元素排成非递减序；

return(S中的第k小元素);}else

{

将S中的元素划分成长度等于5的

|S|/5

个子序列；28

由各子序列的中值元素组成非递减序列M；

m←Select(

|M|/2

，M);

按m将S中的元素划分成小于m、等于

m和大于m的三个子序列S1，S2和S3;if(|S1|>k)return(Select(k,S1));elseif(|S1|+|S2|≥k)return(m);elsereturn(Select(k-|S1|-|S2|,S3));}}29求第k个小的元素（选择问题）m中值序列M

从小到大已知小于或者等于m的元素已知大于或者等于m的元素按m将S中的元素划分成小于m、等于m和大于m的三个子序列S1，S2和S3;从小到大30线性时间选择问题:定理：算法Select在O(n)时间内找出n个元素序列中的第k小的元素。cn≤38T(

n/5

)+T(

3n/4

)+cnn>38T(n)≤T(n)=20cn用线性时间从n个元素中选择出第k个小的元素31线性时间选择:中位数应用中位数原理X轴上有n个点，由左至右依次排列为找一个点xp(不一定是n个点之一)，使xp到各点距离和最小，解为：x1x2xpxnx即解为中位数或中位数的平均值。32棋盘覆盖将2k×2k棋盘分割为4个2k-1×2k-1子棋盘将3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题递归地使用这种分割，直至棋盘简化为棋盘1×1。问题分解过程：以k=2时的问题为例，用二分法进行分解，得到如下图，用双线划分的四个k=1的棋盘。①号②号③号④号34循环赛日程表设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。35循环赛日程表加4加2(a)2k(k=1)个选手比赛122112213443344312211234214334124321567865877856876556786587785687651234214334124321(b)2k(k=2)个选手比赛(c)2k(k=3)个选手比赛36循环赛日程表的推广设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)n为偶数时，循环赛一共进行n-1天。

n为奇数时，循环赛一共进行n天。37CH3动归

方法概述:基本思想动态规划的思想实质是分治思想和解决冗余。与分治法类似的是，将原问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，经分解的子问题往往不是互相独立的。若用分治法来解，有些共同部分（子问题或子子问题）被重复计算了很多次。如果能够保存已解决的子问题的答案，在需要时再查找，这样就可以避免重复计算、节省时间。动态规划法用一个表来记录所有已解的子问题的答案。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表方式。39方法概述:适用条件

动态规划法的有效性依赖于问题本身所具有的两个重要性质最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。40多段图的最短路问题123456789101112s97324212711118654356425V1V2V3V4V5t41多段图的最短路问题假设s,v2,v3,···,vk-1,t是一条从s到t的最短路径，则由v2到t的最短路径是v2,v3,···,vk-1,t，否则设v2,q3,···,qk-1,t是一条由v2到t的更短路径，则s,v2,q3,···,qk-1,t是一条比路径s,v2,v3,···,vk-1,t更短的由s到t的路径，与假设矛盾，故最优化原理成立。42cost(i,j)=min{C(j,r)+cost(i+1,r)}

r∈Vi+1<j,r>∈EjrtViVi+1最短最短向前处理法：设P(i,j)是从Vi中的点j到t的一条最短路，cost(i,j)是这条路线的耗费。由后向前推算，得到43矩阵链乘法矩阵链乘问题满足最优性原理记A[i:j]为AiAi+1…Aj链乘的一个最优括号方案，设A[i:j]的最优次序中含有二个子链A[i:k]和A[k+1:n]，则A[i:k]和A[k+1:n]也是最优的。（反证可得）44递归求解最优解的值记m[i][j]为计算A[i:j]的最少乘法数，则原问题的最优值为

m[1][n](AiAi+1…Ak)pi-1×pk×(Ak+1Ak+2…Aj)pk×pj45货物储运问题在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。5,3,4,1,3,2,3,4设合并a[i:j]，1≤i≤j≤n，所需的最少费用为m[i,j]，则原问题的最优值为m[1，n]。由最优子结构性质可知，462024/9/29470-1背包问题:递归关系换一种视角递归式如下：不取物品i取物品i包含从1到i号物品的最优选择2024/9/29480-1背包问题00000pi–1(j–wi)pi–1(j)0pi(j)0目标

0i–1in0j–wi

jM最长公共子序列的结构设序列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的最长公共子序列49子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：50CH4贪心法贪心算法顾名思义，贪心算法总是作出在当前看来最好的选择贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解：如单源最短路径问题，最小生成树问题等在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。524.2贪心算法的基本要素对于一个具体的问题是否可用贪心算法解此问题？能否得到问题的最优解呢?从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质最优子结构性质534.2贪心算法的基本要素贪心选择性质所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到贪心算法可行的第一个基本要素与动态规划算法的主要区别动态规划算法通常以自底向上的方式解各子问题贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题544.2贪心算法的基本要素最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征55部分(或者小数)背包问题

已知一个容量大小为M重量的背包和n种物品，物品i的重量为wi,假定物品i的一部分xi放入背包会得到vixi这么大的收益，这里，0≤xi≤1，vi>0。采用怎样的装包方法才会使装入背包的物品总效益最大？例：考虑以下情况下的背包问题

n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)56n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)

按vi/wi的非增次序将物品依次放入背包

(x1,x2,x3)ΣwixiΣvixi

(0,1,1/2)2031.557活动安排:问题描述有n个活动集E={1,2,…,n}使用同一资源，而同一时间内同一资源只能由一个活动使用。每个活动的使用时间为[si,fi)i=1,…,n，si为开始时间，fi为结束时间，若[si,fi)与[sj,fj)不相交称活动i和活动j是相容的。问题：选出最大的相容活动子集合。58贪心策略将各活动按结束时间排序f1≤f2≤…≤fn，先选出活动1，然后按活动编好从小到大的次序依次选择与当前活动相容的活动。59注：这种策略使剩余的可安排时间极大化，以便于安排尽可能多的相容活动。

活动安排:计算示例11个活动已按结束时间排序，用贪心算法求解：

i1234567891011start_timei130535688212finish_timei456789101112131401234567891011121314timea1a2a3a4a5a6a7a8a9a10a11相容活动：{a3,a9,a11},{a1,a4,a8,a11},{a2,a4,a9,a11}01234567891011121314timea1a2a3a4a5a6a7a8a9a10a1160有限期的任务安排问题用贪心法求解有限期的任务安排问题：假设只能在同一台机器上加工n个任务，每个任务i完成时间均是一个单位时间。又设每个任务i都有一个完成期限di>0,当且仅当任务i在它的期限截止以前被完成时，任务i才能获得pi的效益，每个任务的期限从整个工序的开工开始计时，问应如何安排加工顺序，才能获得最大效益？n=6,(p1,p2,p3,p4,p5,p6)=(5,25,20,30,10,15),(d1,d2,d3,d4,d5,d6)=(1,5,2,3,3,2)61有限期的任务安排问题

首先按效益非增次序进行排序，然后按照

期限依次对此次序进行调整，排在后面的

或提前或排除。算法的粗略描述

voidGreedy-Job(D,J,n)

/*任务按p1≥p2≥···

≥pn

的次序输入，它们的期限值D[i]≥1,1≤i≤n,n≥1,J是可以在它们的期限截止前完成的任务的集合*/{

J←{1};

for(i=2;i<=n;i++)

if（J∪{i}

的所有任务都能在它

们的截止期限前完成）

J←J∪{i};

}定理：算法Greedy-Job对于有期限的任务

安排问题得到一个最优解。

以上过程反复进行到对第n个任务处理完毕。所得到的贪心解就是一个最优解。

任务0123456

pi030252015105

di0352231J(1)=3J(2)=4J(3)=1J(4)=2

总效益：9064最优装载654.3最优装载

从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪婪策略，首先选择最轻的货箱，然后选次轻的货箱，如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。

假设n=8,[w1,...,w8]=[100,200,50,90,150,50,20,80],c=400。

从剩下的货箱中，选择重量最小的货箱。67利用贪婪算法时，所考察货箱的顺序为7,3,6,8,4,1,5,2。货箱7,3,6,8,4,1的总重量为390个单位且已被装载，剩下的装载能力为10个单位，小于剩下的任何一个货箱。在这种贪婪解决算法中得到[x1,...,x8]=[1,0,1,1,0,1,1,1]且∑xi=6。排序之车间作业计划模型一台机器、n个零件的排序

目的：使得各加工零件在车间里停留的平均

时间最短。零件加工时间11.822.030.540.951.361.5最短：3,4,5,6,1,2(0.5+1.4+2.7+4.2+6+8)/6=3.868若按此顺序：(1.8+3.8+4.3+5.2+6.5+8)/6=4.9CH5回溯法

69回溯法既带有系统性又带有跳跃性的搜索算法。在包含问题所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树(系统性)

算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含问题的解(跳跃性)如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。

这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。70问题的解空间71问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。显约束：对分量xi的取值限定。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。n=3时的0-1背包问题用完全二叉树表示的解空间算法的基本步骤1）针对问题，定义问题的解空间（对解进行编码）；2）确定易于搜索的解空间组织结构（按树或图组织解）；3）以深度优先方式搜索解空间，搜索过程中裁减掉死结点的子树提高搜索效率。72常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。二类常见的解空间树①子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树叶结点数2n，总结点数2n+1，遍历时间为Ω(2n)如0-1背包②排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树叶结点数n!，遍历时间为Ω(n!)如TSP问题方法概述73回溯算法的一般框架子集树回溯算法

voidBacktrack(intt)//搜索到树的第t层

{//由第t层向第t+1层扩展，确定x[t]的值if(t>n)output(x);//叶结点是可行解，输出解

elsewhile(allXt){//Xt为当前扩展结点的所有可能取值集合，例如0和1

x[t]=Xt中第i个值;if(Constraint(t)&&Bound(t))Backtrack(t+1);}}执行时：Backtrack(1)//从1扩展并回溯74节点可行，则探索下一深度当前节点取遍所有可能，即探索树下一深度回溯算法的一般框架（续）排列树回溯算法

voidBacktrack(intt)//搜索到树的第t层

{//由第t层向第t+1层扩展，确定x[t]的值if(t>n)output(x);//叶结点是可行解，输出解

else//已经探索到第t个元素，需要调整后面至n的元素排序fori=tton{//对后续节点，每个试一次swap(x[t],x[i]);if(Constraint(t)&&Bound(t))Backtrack(t+1);swap(x[t],x[i]);}}75恢复到初始排序，便于回溯针对第t个节点，依次将它与后继所有节点进行置换，即遍历新次序是有价值的4后问题设有一4*4的棋盘，把4个皇后放在棋盘上，要求满足下列两个条件：1）任意两个皇后不在同一行上和同一列上；2）任意两个皇后不在同一条对角线上；问有多少种放法？76设第i行放置第i个皇后，xi表示皇后i所处的列数，这样4后问题的全部解向量可以写成(x1,x2,x3,x4)的形式。12347568109x1=1x2=23424233BBBBB111213141516x1=2BB1341377装载问题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。最优装载方案:(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。78问题分析将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近C1。由此可知，装载问题等价于以下特殊的0-1背包问题。79解空间：子集树对于当前扩展节点Z，对于箱子i，有x[i]=1：左子树，代表选中x[i]=0：右子树，代表不选可行性约束函数(选择当前元素)：记当前载重量为cw若cw+w[i]<=c1，左子树可选择右子树总是可以选，因为不增加重量80限界函数：用于剪去不含最优解的子树，从而提高算法在平均情况下的运行效率。设Z是解空间树第i层上的当前扩展结点，cw是当前载重量，R是剩余集装箱的重量，besetW是当前最优载重量，则当

cw+R≤bestW时，剪去Z的右子树81装载问题算法描述voidbacktrack(inti){//搜索第i层结点

if(i>n)//到达叶结点更新最优解bestx,bestw;return;r-=w[i];

if(cw+w[i]<=c)//搜索左子树

{x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}

if(cw+r>bestw){x[i]=0;//搜索右子树

backtrack(i+1);}r+=w[i];}82最大团问题给定无向图G=(V，E)。如果U

V，且对任意u，v

U有(u，v)

E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。如果U

V且对任意u，v

U有(u，v)

E，则称U是G的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集是G中所含顶点数最多的独立集。对于任一无向图G=(V，E)其补图G=(V1，E1)定义为：V1=V，且(u，v)

E1当且仅当(u，v)

E。U是G的最大团当且仅当U是G的最大独立集。124531245383问题分析解空间：子集树可行性约束函数：顶点i到已选入的顶点集中每一个顶点都有边相连。限界函数：有足够多的可选择顶点使得算法有可能找到更大的团。84voidClique::Backtrack(inti)//计算最大团{if(i>n){//到达叶结点

for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn;return;}intOK=1;//检查顶点i与当前团的连接

for(intj=1;j<i;j++)if(x[j]&&a[i][j]==0){//i与j不相连

OK=0;break;}if(OK){//选中后仍满足团定义，进入左子树

x[i]=1;cn++;Backtrack(i+1);x[i]=0;cn--;}if(cn+n-i>bestn){//不选仍有可能获得更优解，进入右子树

x[i]=0;Backtrack(i+1);}}a[][]：记录G中边的邻接矩阵x[]：当前解cn：当前团中顶点数bestx[]：当前最优解bestn：当前最优团顶点数85子集和问题问题给定由n个不同正数组成的集合W={wi}，和正数M，求W中所有和等于M的子集的集合；例如n=6,M=30,

W={10,13,5,18,12,15}

86子集和问题按照回溯法思想，从状态树的根结点出发，做深度优先搜索；当在某一状态A下，依次尝试加入和不加入正数wi，若∑A+wi>M，则可停止对该结点的搜索；若∑A+∑(wi…wn)<M，则也可停止对该结点的搜索；87背包问题求最大价值解空间：子集树1走左子树，0走右子树可行性约束函数当前载重cw，价值cpcw+w[i]<=c，左子树可选择右子树总是可以选，因为不增加重量限界函数：假设物品可拆分，利用贪心思想，求剩余空间装满对应的最大价值按单位重量价值从大到小排序进行选择880-1背包问题Bound(inti){//计算价值的上界，故效率更高

intcleft=c-cw;//剩余容量

intb=cp;//以物品单位重量价值递减序装入物品

while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//装满背包，假设物品可拆分

if(i<=n)b+=p[i]/w[i]*cleft;returnb;}89voidbacktrack(inti){//搜索第i层结点

if(i>n)//到达叶结点更新最优解bestx,bestp;return;if(cw+w[i]<=c){//搜索左子树

x[i]=1;cw+=w[i];cp+=p[i]

backtrack(i+1);cw-=w[i];cp-=p[i];}

if(bound(i+1)>bestp){x[i]=0;//搜索右子树

backtrack(i+1);}}90有载重量M＝50的背包，物体重量分别为5,15,25,27,30，物体价值分别为12,30,44,46,50。求最优装入背包的物体及价值。91回溯过程的效率用回溯法去处理一实例所要生成的结点数，一般是采用在状态空间树中生成一条随机路径的方法估计。92CH6分支限界法

93方法概述:与回溯法的区别求解目标不同：一般而言，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解；搜索方法不同：回溯算法使用深度优先方法搜索，而分枝限界一般用宽度优先或最小耗费方法来搜索；

94方法概述:与回溯法的区别对扩展结点的扩展方式不同：分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点；存储空间的要求不同：相对而言，分枝限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大；

方法概述:

两种常见的活结点扩展方式先进先出队列（FIFO）:即从活结点表中取出结点的顺序与加入结点的顺序相同；优先队列:每个结点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，下一个扩展结点就是具有最小耗费的活结点；如果希望搜索一个具有最大收益的解，下一个扩展结点是具有最大收益的活结点。96方法概述:示例1示例1（FIFO队列分枝限界法）问题：0-1背包问题:物品数n=3,重量w=(20,15,15),价值v=(40,25,25),背包容量c=30,试装入最大价值之和的物品?求解：①解空间:{(0,0,0),(0,0,1),…,(1,1,1)}②解空间树:DBHAIEJKFCLMGNO1111111000000097方法概述:示例1③BFS搜索（FIFO队列）扩展结点活结点队列(可行结点)可行解(叶结点)解值

AB,CBCBD,E(D死结点)CECF,GEFGEJ,K(J死结点)FGK40FL,MGL,M50,25GN,OφN,O25,0

∴最优解为L,即(0,1,1);解值为50DBHAIEJKFCLMGNO11111110000000w=(20,15,15),v=(40,25,25),c=3098方法概述:示例2示例2（优先队列分枝限界法）问题：0-1背包问题:物品数n=3,重量w=(20,15,15),价值v=(40,25,25),背包容量c=30,试装入最大价值之和的物品?求解：①解空间:{(0,0,0),(0,0,1),…,(1,1,1)}②解空间树:DBHAIEJKFCLMGNO1111111000000099方法概述:示例2BFS搜索（优先队列：按价值率优先）扩展结点活结点堆(可行结点)可行解(叶结点)解值

AB,CBD,E(D死结点)EJ,K(J死结点)K40CF,G

FL,ML

50(最优)GN,OφBCECFGCGDBHAIEJKFCLMGNO11111110000000w=(20,15,15),v=(40,25,25),c=30100分配问题分配问题：设有n个人，每个人都可以完成n种不同的任务，但所需时间不同。如果只需一人去完成每一项工作，则应如何分配n个人并使完成所有n项工作的总时间为最小。101人1234

A21097

B154148

C13141611

D41513922A做1B做1C做1D做1274133243624342831A做2B做2C做2A做3C做3283739B做2C做2D做2A→3,B→2,C→4,D→1,总时间为28例1：用分支限界法求解分配问题102单源最短路径问题问题描述单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。

103单源最短路径问题

下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。1046.2 单源最短路径问题剪枝策略在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则剪去以该结点为根的子树利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长大的路径所对应的树中结点为根的子树剪去105路径(a,e,q)与(c,h)到达同一节点分别对应的费用为5和6。称搜索树中节点A控制了B。因此可将B节点的子树剪去ABCH7随机

106定义：在算法中引入随机因素,即通过随机数选择算法的下一步操作。特点：简单、快速一种平衡：随机算法可以理解为在时间、空间和随机三大计算资源中的平衡1071、数值概率算法：用于数值问题的求解2、Sherwood算法一定能得到问题的正确解常见的四类随机算法：1083、LasVegas算法或者得到正确的解，或者得不到解。4、MonteCarlo算法一定能得到解，但是得到的解可能不正确，然而这种概率是小的且有界的。常见的四类随机算法：109网络流

流,流量,最大流sv1v3v2v4t11/168/13101/412/1215/204/47/74/911/14称f:V

V

R为流,若f满足：(1)容量限制,f(u,v)

c(u,v)(2)反对称性,f(u,v)=-f(v,u)(3)流守恒性,任意u

V\{s,t},

v

Vf(u,v)=0流量|f|=

v

Vf(s,v).

最大流:给定流网络G,s,t,c,求

max{|f|:f是G的流}111流网络的割割(S,T):(1)T=V-S(2)sS,t

T.f(S,T)=

u

S,v

Tf(u,v):f穿过割(S,T)的净流c(S,T)=

u

S,v

Tc(u,v):割(S,T)的容量sv1v3v2v4t11/168/13101/412/1215/204/47/74/911/14←ST→例.下图中的割(S,T),S={s,v1,v2},T={v3,v4,t}.

f(S,T)=19,

c(S,T)=26.最大流最小割定理f(S,T)=|f|,|f|

min{c(S,T)|割(S,T)}.

定理(最大流最小割)下列条件等价

(1)f是G的一个最大流;

(2)G不包含增广路径;

(3)存在割(S,T)使得|f|=c(S,T).

最大流算法基本思想:

找从s到t的增广路径,增大流,无则停止,得最大流113计算理论

CH1集合、关系与语言

数学归纳法鸽巢原理对角化原理1.5三个基本的证明技术116字