复习提纲Word下载.docx
《复习提纲Word下载.docx》由会员分享，可在线阅读，更多相关《复习提纲Word下载.docx（26页珍藏版）》请在冰点文库上搜索。
若区间[si,fi）与区间[sj,fj）不相交，则称活动i与活动j是相容的。
也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。
下面给出解活动安排问题的贪心算法GreedySelector:
由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。
直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。
也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
算法greedySelector的效率极高。
当输入的活动已按结束时间的非减序排列，算法只需O（n）的时间安排n个活动，使最多的活动能相容地使用公共资源。
如果所给出的活动未按非减序排列，可以用O（nlogn）的时间重排。
例：
设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：
i
1
2
3
4
5
6
7
8
9
10
11
S[i]
12
F[i]
13
14
若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。
贪心算法并不总能求得问题的整体最优解。
但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。
这个结论可以用数学归纳法证明。
单源最短路径问题：
给定带权有向图G=（V,E），其中每条边的权是非负实数。
另外，还给定V中的一个顶点，称为源。
现在要计算从源到所有其它各顶点的最短路长度。
这里路的长度是指路上各边权之和。
这个问题通常称为单源最短路径问题。
1、算法基本思想
Dijkstra算法是解单源最短路径问题的贪心算法。
基本思想:
设置顶点集合S并不断地作贪心选择来扩充这个集合。
一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。
初始时，S中仅含有源。
设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。
Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。
一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。
输入带权有向图G=（V，E），V={1，2，…，n}，顶点V1是源
C[i][j]表示边（i,j）的权
dist[i]表示从源到顶点v1的最短特殊路径长度
prev[i]表示从源到顶点i的最短路径上i的前一个顶点。
输入参数：
n,v1,c[i][j]
输出参数：
dist[i],prev[i]
算法描述：
基本思想：
S[i]—源点到i顶点的最短路径是否找到
初始化：
for（i=1;
i<
=n;
i++）
{s[i]=0;
dist[i]=c[v1][i];
}
S[v1]=1,dist[v1]=0;
每次从V-S中取出具有最短特殊路长度的顶点u，并将u添加到S中
for（num=2;
num<
num++）
{从dist[2]到dist[n]选取一顶点u且满足s[u]=0,使dist[u]=min{dist[2],dist[3],…,dist[n]};
s[u]=1;
}
Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中后，同时对数组dist作必要的修改。
for（j=1;
j<
j++）
{
if（s[j]==0&
&
c[u][j]<
maxint）
{newdist=dist[u]+c[u][j];
if（newdist<
dist[j]）
{dist[j]=newdist;
prev[j]=u;
}
整个过程执行n-1次
2、算法的正确性和计算复杂性
（1）贪心选择性质
（2）最优子结构性质
（3）计算复杂性
对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要时间。
这个循环需要执行n-1次，所以完成循环需要时间。
算法的其余部分所需要时间不超过。
第三章
1．递归与分治的基本思想
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治法解决一个问题可以分为“分”和“治”两个阶段，而且整个过程使用的是递归的思想。
因此，通常都是利用递归方式进行描述。
2．递归的优缺点分析
优点：
结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
缺点：
递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
3．分治的基本步骤
divide-and-conquer（P）
{
if（|P|<
=n0）adhoc（P）;
//解决小规模的问题
dividePintosmallersubinstancesP1,P2,...,Pk；
//分解问题
for（i=1,i<
=k,i++）
yi=divide-and-conquer（Pi）;
//递归的解各子问题
returnmerge（y1,...,yk）;
//将各子问题的解合并为原问题的解
4．阶乘、二分搜索、快速排序
二分搜索问题：
给定已按升序排好序的n个元素a[0:
n-1]，现要在这n个元素中找出一特定元素x。
分析：
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题;
分解出的子问题的解可以合并为原问题的解；
分解出的各个子问题是相互独立的。
intBinarySearch（Typea[],intx,intl,intr）
while（r>
=l）{
intm=（l+r）/2;
if（x==a[m]）returnm;
if（x<
a[m]）r=m-1;
elsel=m+1;
return-1;
算法复杂度分析：
每执行一次算法的while循环，待搜索数组的大小减少一半。
因此，在最坏情况下，while循环被执行了O（logn）次。
循环体内运算需要O
（1）时间，因此整个算法在最坏情况下的计算时间复杂性为O（logn）。
快速排序问题：
在快速排序中，记录的比较和交换是从两端向中间进行的,关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。
voidQuickSort（Typea[],intp,intr）
if（p<
r）{
intq=Partition（a,p,r）;
QuickSort（a,p,q-1）;
//对左半段排序
QuickSort（a,q+1,r）;
//对右半段排序
快速排序算法的性能取决于划分的对称性。
通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。
在快速排序算法的每一步中，当数组还没有被划分时，可以在a[p:
r]中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。
template<
classType>
intRandomizedPartition（Typea[],intp,intr）
inti=Random（p,r）;
Swap（a[i],a[p]）;
returnPartition（a,p,r）;
最坏时间复杂度：
O（n2）
平均时间复杂度：
O（nlogn）
辅助空间：
O（n）或O（logn）
快速排序算法分析：
Partition（a,p,r）计算时间为O（r-p+1）,即f（n）=n
最好情况，每次q=（p+r）/2
O
（1）n=1
T（n）=2T（n/2）+nn>
解方程得：
T（n）=n+nlog2n=O（nlog2n）
最坏情况，每次q=p或q=r
T（n）=T（n-1）+nn>
T（n）=O（n2）
第四章
1．动态规划的基本思想、基本步骤
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。
基本步骤：
找出最优解的性质，并刻划其结构特征。
递归地定义最优值。
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息，构造最优解。
2．
投资问题、矩阵连乘问题
给定n个矩阵，其中与是可乘的，。
考察这n个矩阵的连乘积
由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。
这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积
完全加括号的矩阵连乘积可递归地定义为：
（1）单个矩阵是完全加括号的；
（2）矩阵连乘积A是完全加括号的，则A可
表示为2个完全加括号的矩阵连乘积B和C
的乘积并加括号，即A=（BC）
举例：
假设有四个矩阵A,B,C,D
思考：
计算次序和数乘次数？
16000,10500,36000,87500,34500
矩阵连乘问题
给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。
如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
◆穷举法：
列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。
对于n个矩阵的连乘积，设其不同的计算次序为P（n）。
由于每种加括号方式都可以分解为两个子矩阵的加括号问题：
（A1...Ak）（Ak+1…An）可以得到关于P（n）的递推式如下：
◆动态规划
将矩阵连乘积
简记为A[i:
j]，这里i≤j
考察计算A[1:
n]的最优计算次序。
设这个计算次序在矩阵
Ak和Ak+1之间将矩阵链断开，1≤k<
n，则其相应完全
加括号方式为
计算量：
A[1:
k]的计算量加上A[k+1:
n]的计算量，再加上
k]和A[k+1:
n]相乘的计算量
1、分析最优解的结构
特征：
计算A[1:
n]的最优次序所包含的计算矩阵子链A[1:
n]的次序也是最优的。
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。
这种性质称为最优子结构性质。
问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。
2、建立递归关系
设计算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]为：
k的位置只有
种可能
3、计算最优值
对于1≤i≤j≤n不同的有序对（i,j）对应于不同的子问题。
因此，不同子问题的个数最多只有
由此可见，在递归计算时，许多子问题被重复计算多次。
这也是该问题可用动态规划算法求解的又一显著特征。
用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。
在计算过程中，保存已解决的子问题答案。
每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法
用动态规划法求子问题最优解
算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。
循环体内的计算量为O
（1），而3重循环的总次数为O（n3）。
因此算法的计算时间上界为O（n3）。
算法所占用的空间显然为O（n2）。
4、构造最优解
VoidTraceback（inti,intj,int*s）
if（i=j）printf（“a%d”,i）
else
printf（“（”）;
traceback（i,s[i][j],*s）;
traceback（s[i][j]+1,j,*s）;
printf（“）”）;
}
投资问题：
设总投资额为m，共有n个项目，Gi（x）为向第i项工程投资费用为x时的收益，如何分配资源才能获得最大利润？
X
G1（x）
15
40
80
90
95
98
100
G2（x）
60
70
73
74
75
G3（x）
26
45
50
51
53
动态规划策略解题步骤：
1、分析投资问题的最优解结构特征
2、用递归式描述最优值结构
3、用算法求最优值
一．分析投资问题的最优解结构特征
设总投资额为m，共有n个项目,Fn（m）为向n个项目投资m所获最大收益，Gi（xi）为向第i项工程投资xi时的收益，则有
Fn（m）=G1（x1）+G2（x2）+…..+Gn-1（xn-1）+Gn（xn）
⏹最优解（x1、x2、…..、xn-1、xn）
⏹约束条件：
x1+x2+…..+xn-1+xn=m
⏹xi<
=m
二．用递归式描述最优值结构
⏹首先，向第n项工程投资xn，所获收益为Gn（xn）
⏹则向剩余n-1项投资额为m-xn，所获最大收益为Fn-1（m-xn）
⏹该投资问题的最大收益为Fn（m）=Fn-1（m-xn）+Gn（xn）
⏹该投资问题的最大收益为Fn（m）=max｛Fn-1（m-x）+Gn（x）｝x<
⏹更一般化的形式Fk（m）=max{Fk-1（m-x）+Gk（x）}x<
三．用算法求最优值
Invest（m,n,f[n][m],g[n][m]）
{for（j=0;
=m;
{f[1][j]=g[1][j];
d[1][j]=j;
for（i=2;
for（j=0;
{f[i][j]=0;
for（k=0;
k<
=j;
k++）
{s=f[i-1][j-k]+g[i][k];
if（s>
f[i][j]）{f[i][j]=s;
d[i][j]=k;
四．构造最优解
d[i][j]存放的是决策—即向前i项工程投资为j时f[i][j]获得最大收益，此时向第i项工程的投资额为d[i][j]，根据d[i][j]构造最优解
d[n][m]=kn
d[n-1][m-kn]=kn-1
d[n-2][m-kn-1]=kn-2
……..
d[1][m-kn-kn-1-….-k2]=k1
构造最优解思路：
s=m;
k[n]=d[n][m]；
for（i=n-1；
i>
0；
i--）
s=s-k[i+1]；
k[i]=d[i][s]；
outputk[i]；
第五章
1．回溯法的基本思想
扩展结点:
一个正在产生儿子的结点称为扩展结点
活结点:
一个自身已生成但其儿子还没有全部生成的节点称做活结点
死结点:
一个所有儿子已经产生的结点称做死结点
确定了解空间的组织结构后，回溯法就从开始结点（根节点）出发，以深度优先的方式搜索整个解空间。
这个开始结点就成为一个活结点，同时成为当前的扩展结点。
在当前的扩展结点处，搜索向纵深方向移至一个新结点。
这个结点就成为一个新的活结点，并成为当前扩展结点。
如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。
此时应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。
回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。
2．n后问题、图的M着色、迷宫问题
n后问题
在n×
n格的棋盘上放置彼此不受攻击的n个皇后。
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n后问题等价于在n×
n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
•解向量：
（x1,x2,…,xn）
•显约束：
xi=1,2,…,n
•隐约束：
1）不同列：
xixj
2）不处于同一正、反对角线：
|i-j||xi-xj|
boolQueen:
:
Place（intk）
for（intj=1;
k;
if（（abs（k-j）==abs（x[j]-x[k]））||（x[j]==x[k]））returnfalse;
returntrue;
voidQueen:
Backtrack（intt）
if（t>
n）sum++;
for（inti=1;
i++）{
x[t]=i;
if（Place（t））Backtrack（t+1）;
Queen:
backtrack（）
X[1]=0;
intk=1;
While（k>
0）{
x[k]+=1;
while（（x[k]<
=n）&
!
（place（k）））x[k]+=1;
if（x[k]<
=n）
if（k==n）sum++;
else{k++;
x[k]=0;
else{x[k]=0;
k--;
{for（intj=1;
if（（abs（k-j）==aba（x[j]-x[k]））||（x[j]==x[k]））returnfalse;
图的M着色
给定无向连通图G和m种不同的颜色。
用这些颜色为图G的各顶点着色，每个顶点着一种颜色。
是否有一种着色法使G中每条边的2个顶点着不同颜色。
这个问题是图的m可着色判定问题。
若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。
求一个图的色数m的问题称为图的m可着色优化问题。
（x1,x2,…,xn）表示顶点i所着颜色x[i]
•可行性约束函数：
顶点i与已着色的相邻顶点颜色不重复。
voidColor:
n）{
sum++;
i<
i++）
cout<
<
x[i]<
'
;
endl;
if（Ok（t））Backtrack（t+1）;
boolColor:
Ok（intk）
{//检查颜色可用性
if（（a[k][j]==1）&
（x[j]==x[k]））returnfalse;
复杂度分析
图m可着色问题的解空间树中内结点个数是
对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O（mn）。
因此，回溯法总的时间耗费是
M_coloring（intn,intm,intg[][]）//非递归算法1
{for（i=1;
i++）x[i]=1;
k=1;
do{if（x[k]<
=m）
{for（i=1;
i++）
{if（g[i][k]==1andx[i]==x[k]）break;
if（i<
k）x[k]++;
elsek++;
else{x[k]=1;
k=k-1;
升级会员 