intq=Partition(a,p,r);
QuickSort(a,p,q-1);//对左半段排序
QuickSort(a,q+1,r);//对右半段排序
}
}
快速排序算法的性能取决于划分的对称性。
通过修改算法partition,可以设计出采用随机选择策略的快速排序算法。
在快速排序算法的每一步中,当数组还没有被划分时,可以在a[p:
r]中随机选出一个元素作为划分基准,这样可以使划分基准的选择是随机的,从而可以期望划分是较对称的。
template
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>1
解方程得:
T(n)=n+nlog2n=O(nlog2n)
最坏情况,每次q=p或q=r
O
(1)n=1
T(n)=T(n-1)+nn>1
解方程得:
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加括号方式为
计算量:
A[1:
k]的计算量加上A[k+1:
n]的计算量,再加上
A[1:
k]和A[k+1:
n]相乘的计算量
1、分析最优解的结构
特征:
计算A[1:
n]的最优次序所包含的计算矩阵子链A[1:
k]和A[k+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这里
的维数为
可以递归地定义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
0
1
2
3
4
5
6
7
8
G1(x)
0
5
15
40
80
90
95
98
100
G2(x)
0
5
15
40
60
70
73
74
75
G3(x)
0
4
26
40
45
50
51
53
53
动态规划策略解题步骤:
1、分析投资问题的最优解结构特征
2、用递归式描述最优值结构
3、用算法求最优值
4、构造最优解
一.分析投资问题的最优解结构特征
设总投资额为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<=m
⏹更一般化的形式Fk(m)=max{Fk-1(m-x)+Gk(x)}x<=m
三.用算法求最优值
Invest(m,n,f[n][m],g[n][m])
{for(j=0;j<=m;j++)
{f[1][j]=g[1][j];d[1][j]=j;}
for(i=2;i<=n;i++)
for(j=0;j<=m;j++)
{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;jif((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;
returntrue;
}
voidQueen:
:
Backtrack(intt)
{
if(t>n)sum++;
else
for(inti=1;i<=n;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--;}
}
}
Place(intk)
{for(intj=1;jif((abs(k-j)==aba(x[j]-x[k]))||(x[j]==x[k]))returnfalse;
returntrue;}
图的M着色
给定无向连通图G和m种不同的颜色。
用这些颜色为图G的各顶点着色,每个顶点着一种颜色。
是否有一种着色法使G中每条边的2个顶点着不同颜色。
这个问题是图的m可着色判定问题。
若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色,则称这个数m为该图的色数。
求一个图的色数m的问题称为图的m可着色优化问题。
•解向量:
(x1,x2,…,xn)表示顶点i所着颜色x[i]
•可行性约束函数:
顶点i与已着色的相邻顶点颜色不重复。
voidColor:
:
Backtrack(intt)
{
if(t>n){
sum++;
for(inti=1;i<=n;i++)
cout<cout<}
else
for(inti=1;i<=m;i++){
x[t]=i;
if(Ok(t))Backtrack(t+1);
}
}
boolColor:
:
Ok(intk)
{//检查颜色可用性
for(intj=1;j<=n;j++)
if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;
returntrue;
}
复杂度分析
图m可着色问题的解空间树中内结点个数是
对于每一个内结点,在最坏情况下,用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。
因此,回溯法总的时间耗费是
M_coloring(intn,intm,intg[][])//非递归算法1
{for(i=1;i<=n;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(ielsek++;}
else{x[k]=1;k=k-1;