Loading... # 10 算法设计与分析 ## 10.1 递归与分治 ### 10.1.1 递归方法设计 用递归方法求解问题的关键是合理的递归定义式的建立，我们以整数划分问题为例考虑递归问题求解过程中的递归算法的建立过程。 将正整数n表示成一系列正整数之和， $n=n_1+n_2+\cdots+n_k$ 其中 $n_1\ge n-2\ge\cdots\ge n_k\ge 1,k\ge 1$ 设计算法求n的不同划分个数p(n)。 例：p(6)=11 6; 5+1; 4+2,4+1+1; 3+3,3+2+1,3+1+1=1; 2+2+2,2+2+1+1,2+1+1+1+1; 1+1+1+1+1+1。 求解方法设计 用q(n,m)表示正整数n的不同划分中，最大加数$n_1$，不大于m的划分个数。可以建立求q(n,m)的递归关系如下： 1. q(n,1) = 1，$n\ge 1$;此时对应的划分为$n=\overbrace{1+1+\cdots+n}^{\rm n}$。 2. q(1,m) = 1；此时对应的划分为1=1。 3. q(n,m)=q(n，n)，$m\le n$；显然在整数n的划分中最大加数不能大于n。 4. q(n,n)=1+g(n,n-1)；因为对应于最大加数为n的划分只有一种。 5. q(n,m)=q=(n,m-1)+q(n-m,m），$n\gt m\gt 1$此时的分洁策略为整数n的划分数对应于最大加数为m和最大加数不大于m-1时两种划分数的和。 递归定义如下： $$ q(n,m)= \begin{cases} 1,&m=1\\ q(n,n),&n\lt m\\ 1+q(n,n-1),&n=m \\ q(n,m-1)+q(n-m,m),&n\gt m\gt 1 \end{cases} $$ ```cpp int q(int n, int m) { if((n<1)||m<1) return 0; if((n==1)||(m==1)) return 1; if(n<m) return q(n,n); if(n==m) return q(n,m-1)+1; return q(n,m-1), q(n-m,m); } ``` ### 10.1.2 分治法 矩阵乘法是矩阵计算中的基本问题之一，它在科学与工程计算领域有广泛的应用。设**A**和**B**是两个$n\times n$的矩阵，它们的乘积AB同样是一个$n\times n$矩阵。乘积矩阵**C**=**AB** 20 世纪60年代末期，Srassen采用了类似于在大整数乘法中用过的分治技术，将计算2个n阶矩阵乘积所需的计算时间改进到$O(2^{log_27})=O(2^{2.81}) $，其基本思想是采用了分治技术。 设n是2的幂，将矩阵**A**、**B**和**C**中每一矩阵都分成4个大小相等的子矩阵，每个子矩阵都是(n/2)×(n/2)的方阵。矩阵分块后得: $$ \begin{bmatrix} C_{11}&C_{12}\\ C_{11}&C_{22}\\ \end{bmatrix}=\begin{bmatrix} A_{11}&A_{12}\\ A_{11}&A_{22}\\ \end{bmatrix}+\begin{bmatrix} B_{11}&B_{12}\\ B_{11}&B_{22}\\ \end{bmatrix} $$ 由矩阵乘法性质得： $$ \begin{array}{c} C_{11}=A_{11}B_{11}+A_{12}B_{21}\\ C_{12}=A_{11}B_{12}+A_{12}B_{22}\\ C_{21}=A_{21}B_{11}+A_{22}B_{21}\\ C_{22}=A_{21}B_{12}+A_{22}B_{22} \end{array} $$ 当n=2时，容易计算2个2阶方阵的乘积时需8次乘法和4次加法。当子矩阵的阶大于2时，为求两个子矩阵的积，可以继续将子矩阵分块，直到子矩阵的阶降为2为止。由此产生分治降阶的递归算法。可以推算，计算2个n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2阶的加法，$2个(n/2)\times(n/2)$矩阵的加法显然可在$O(n^2)$的时间完成。因此上述分治法的计算时间耗费T(n)应满足： $$ T(n)=\begin{cases} O(1),&n=2\\ 8T(n/2)+O(n^2),&n\gt2 \end{cases} $$ 遗憾的是，这个递归方程的解$T(n)=O(n^3) $。此结果表明该方法并不比原始按矩阵乘法定义直接计算更有效。原因是该方法并没有减少矩阵的乘法次数，而矩阵乘法耗费的时间要比矩阵加(减)法耗费的时间多得多，因此，减少矩阵乘法的计算时间复杂度的关键是必须减少乘法运算。 减少乘法运算次数的关键是计算2个2阶方阵的乘积时，能否用少于8次的乘法运算。Strassen提出了一种新的算法计算 2个2阶方阵的乘积。他的算法仅用了7次乘法运算，但增加了加减法的运算次数。Strassen的7次乘法运算是： $$ \begin{array}{c} &M_1=A_{11}(B_{12}-B_{22})\\ &M_2=(A_{11}+A_{12})B_{12}\\ &M_3=(A_{21}+A_{22})B_{11}\\ &M_4=A_{22}(B_{21}-B_{11})\\ &M_5=(A_{11}+A_{22})(B_{11}+B_{22})\\ &M_6=(A_{12}-A_{22})(B_{21}+B_{22})\\ &M_7=(A_{11}-A_{21})(B_{11}+B_{12})\\ \end{array} $$ $$ \begin{array}{c} C_{11}=M_5+M_4-M_2+M_6\\ C_{12}=M_1+M_2\\ C_{21}=M_3+M_4\\ C_{22}=M_5+M_1-M_3-M_7\\ \end{array} $$ 耗时 $$ T(n)=\begin{cases} O(1),&n=2\\ 7T(n/2)+O(n^2),&n\gt2 \end{cases} $$ ## 10.2 回溯法 回溯法对任一解的生成，一般都采用逐步扩大解的方式。每前进一步，都试图在当前部分解的基础上扩大该部分解。它在问题的状态空间树中，从开始结点（根结点）出发，以深度优先搜索整个状态空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为新的活结点，并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的活结点处，并使这个活结点成为当前扩展结点。回溯法以这种工作方式递归地在状态空间中搜索，直到找到所要求的解或解空间中已无活结点时为止。 例 10-2 迷宫问题。 老鼠走迷宫是一个心理学中的一个经典实验，用来测验老鼠的记忆力强弱，如果它的记忆力强，那么在迷宫中对以尝试过的失败路径就不会再去尝试。 问题描述∶设有一只无盖大箱，箱中设置一些隔离板，形成弯弯曲曲的通道作为迷宫。箱子中设有一个入口和出口。实验时，在出口处放一些奶酪之类的东西吸引老鼠，然后将一只老鼠放到入口处，老鼠受到美味的吸引，向出口处走。心理学家需要观察老鼠是如何从入口到达出口的。 要求∶假设老鼠具有很强的记忆力(A级假设智能)，编写一个计算机程序，模拟老鼠走迷宫的过程。实际测验时，可以用运行的计算机程序得到的模拟老鼠走迷宫的过程与老 鼠实际走迷宫的过程进行对比，依此衡量老鼠的记忆力强弱。 求解方法：采用回溯法。老鼠走迷宫的方式为∶试探-回溯，尝试-纠错。数据结构设计： 图10.1是用0-1矩阵表示的迷宫，矩阵四边的1表示迷宫的边界。迷宫的入口设在左上角的0位置，出口设在右下角的0位置。 1. 迷宫。 用二维数组$A_{m\times m}$表示迷宫，用0和1分别表示迷宫中的路"通"与"不通"。当A[i,j]=0时表示迷宫中(i,j)处是通路，而当A[i,j]=1时表示迷宫中(i,j)处是隔板。 2. 路径记录。 对于迷宫中的任一点有8个可行走的方向，可用整数0～7表示。显然，可用三元组(i,j,k)（这里i,j,k分别表示行号、列号和方向）表示。这样的三元组可用来记录在迷宫中行走的路径。 3. 方向与方向增量。 对于矩阵中的每个非边界点都存在八个可能的移动方向，把东、东南、南、西南、西、西北、北、东北8个方向依次定义为方向0～方向7。若沿矩阵中的非边界位置(i,j)到达矩阵这8个方向的下一个位置时，都可通过位置增量计算得到下一位置$(i+\Delta x,j+\Delta y)$，这里$\Delta x,\Delta y$分别为行、列坐标的增量。增量的取值见表 10-1。  ```cpp #include<stido.h> #include<stdlib.h> #define MaxNumCol 10 typedef struct { int row,col,dire;//行列，方向号 }MaxPositon; int Mazetravel(int maze[][MaxNumCol],int n, int m, MaxPosition path[]) { int top,i,j,k,h,dire; int incr[8][2]={0,1 1,1 1,0 1,-1 0,-1 -1,-1 -1,0 -1,1}; top=0; i=1;j=1;dire=0;//置入口信息，起始方向 /*路径信息进栈*/ path[top].row=i; path[top].col=j; path[top].dire=dire; maze[i][j]=-1; while(top>=0||dire<8) { if(dire<8) { k=i+incr[dire][0]; h=j+incr[dire][1]; if(maze[k][h]!=1&&maze[k][h]!=-1) {//这两个判定条件分别是不是墙与没去过 maze[k][h]=-1; top++; path[top].row=k; path[top].col=h; path[top].dire=dire; i=k;j=h;dire=0; if(i==n-2&&j==m-2) return top; } else dire++; } else { dire=path[top].dire+1; top--; if(top>0) { i=path[top].row; j=path[top].col; } } } return 0; } void main() { int maze1[10][10]={ 1,1,1,1,1, 1,1,1,1,1, 1,0.0,0,1, 1,0,1,1,1, 1,1,0,1,0, 1,0,0,0,1, 1,0,1,1,0, 0,1,0,1,1, 1,0,0,0,1, 0,1,1,0,1, 1,1,0,1,0, 1,1,0,1,1, 1,0,0,1,0, 1,0,1,1,1, 1,0,1,1,1, 0,1,0,1,1, 1,1,0,1,1, 1,1,0,0,1, 1,1,1,1,1, 1,1,1,1,1}; MazePostion path1[20]; int 1,k=mazetravel(maze1,10,10,path1); if(k==0) printf("No way from initial position to the end\n"); else for(l=0;l<=k;l++) { printf("Step %d, is %d, %d\n",l+1,path1[l].row path1[l].col); } } ``` 若要改为求全部解，修改方法如下： 1. 求得单个解后算法不终止，而先输出路径再沿着path[top].dire的下一个方向继续搜索； 2. 修改试探标志，仅当位置(i,j)的8个方向都已搜索，才置maze[i][j]=-1。 例10-3 n皇后问题 问题描述：在$n\times n$格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一斜线的棋子。n后问题等价于在$n\times n$格的棋盘上放置n个皇后，任何2 个墓后不放在同一行或同一列或同一斜线上。 求解方法：回溯法。易知，1皇后有1个解，2皇后和3皇后问题无解。可以计算8皇后问题有98个解。 数据结构设计∶用n元组x[1:n]表示后问题的解，其中x[i]表示皇后i放在棋盘的第i行的第x[i]列。显然每个x[i]中的值互不一样。要保留多个解时，需要设立多个这样的一维数组或二维数组。将$n\times n$格的棋盘看作二维方阵，行、列的编号依次为$1,2,\cdots,n$。 算法设计：设目前在i行j列放置皇后，考虑如何判断是否和其他皇后位于同一行或同一列或同一斜线的条件。由于不允许将2个皇后放在同一列，所以解向量x[i]中的值互不一样。2个皇后不能放在同一斜线上是问题的隐约束。对于 n皇后问题这一隐约束条件可以化成显约束的形式。设2个皇后放置的位置分别是(i,j)和(k,l)，且i-k=k-l或i一k=l-j，则这2个皇后位于同一斜线上，上述两条件等价于|i-k|=|j-l|。 ```cpp #include<stdio.h> #include<math.h> #define n 8 int x[n+1], sum; enum boolean{FALSE,TRUE}; typedef enum boolean Bool; Bool place(int); void backtrack(void); int main() { int i; for(i=0;i<n;i++) x[i]=0; backtrack(); printf("%d 皇后解的数目为%d\n",n,sum); } /*判断棋盘第k行是否可放入皇后*/ Bool place(int k) { int j; for(j=1;j<k;j++) if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))//斜线与列 return FALSE; return TRUE; } void backtrack() { int k=1; x[1]=0; while(k>0) { x[k]+=1; while((x[k]<=n)&&!(place(k))) x[k]+=1; if(x[k]<=n) if(k==n)//sum++后，此时k=n,在上面的while循环中使用x[k]=n+1,使得k--; sum++; else { k++; x[k]=0; } else k--; } } ``` ## 10.3分支限界法 分支限界与回溯法在下面两个方面存在差异。 1. 控制条件：回溯法一般使用约束函数产生部分解，若满足约束条件，则继续扩大该解；否则丢弃，重新搜索。而在分支限界法中，除了使用约束函数外，还使用更有效的评判函数——目标函数控制搜索进程，使尽快能得到最优解。 2. 搜索方式：回溯法中的搜索一般是以深度方向优先方式进行，而在分支限界法中一般是以广度方向优先方式进行。 从活结点表中选择下一扩展结点的不同方式导致不同的分支限界方法。常用的有下列两种方式。 1. 队列式（FIFO））分支限界法∶将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。 2. 优先队列式分支限界法∶将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。 例10-4 0-1 背包问题。 给定n种物品和一个背包。物品i的重量是$w_i$，其价值为$p_i$，背包容量为C，对于每种物品i只有两种选择：即装入背包或不装入背包，不能将物品i装入背包多次。问：应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 设$C\gt0,w_i\gt0,p_i\gt0,1\le i\le n$，问题的解对应于求一组n元0-1向量$(x_1,x_2,\cdots,x_n),x_i\in {0,1},1\le i\le n $，它是下面的整数规划问题的解。 $$ \max\sum_{i-1}^{n}p_ix_i $$ $$ \left\{ \begin{array}{c} \sum_{i=1}^nw_ix_i\le C\\ x_i\in \{0,1\}, 1\le i\le n \end{array} \right. $$  用队列式分支限界法解此问题时，算法从根结点A开始，初始时活结点队列为空，结点A是当前扩展结点，结点A的子女结点B、C均为可行结点，依次按从左至右的顺序将C加人活结点队列，并舍弃当前扩展结点 A。队首结点 B 成为当前扩展结点，扩展结点B得到结点D、E，由于D是不可行结点，舍去结点 D，结点 E加入活结点队列。取活结点队列队首结点C，扩展结点C得结点F、G，结点F、G均为可行结点，加入活结点队列。扩展下一结点E得到结点J、K，结点J是不可行结点，舍去，结点K是一个可行结点，加入活结点队列。再次扩展队首结点F，得到结点L、M。L表示获得价值为50的可行解，M表示获得价值为25的可行解。G是最后的一个扩展结点，其儿子结点N、O均为可行叶结点。此时，活结点队对为空，算法结束。算法搜索得到最优值为50。相应的最优解是从根结点 A 到结点L 的路径。 优先队列分支限界法从根结点A开始搜索解空间。更一个大根堆表示活结点表的优先队列。初始时堆为空，扩展结点A得到它的两个子女结点B、C，这两个结点均为奇行结点，加入到堆中，结点A被舍弃。结点B获得的当前价值是45，而结点C的当前价值是0。由于结点 B的价值大于结点C的价值，所以结点 B是堆中的堆顶元素，成为下一个扩展结点。扩展结点B得到结点D和E，因D是不可行结点，故舍弃，E是可行结点，加入到堆中，E的价值为45，是当前堆中的堆顶元素，亦成为下一个扩展结点。扩展结点E得到叶子结点J、K，因结点J是不可行结点，故舍弃，叶结点K表示一个可行解，其价值为45。此时，堆中仅剩下一个活结点，它成为当前扩展结点，扩展得到两个结点F、G，其价值分别为 25、0，将 F、G加入大根堆，取去堆顶的元素F作为下一个扩展结点，扩展得到两个叶子结点L、M，结点L所对应于价值为50的可行解，结点M对应于价值为25的可行解。最后剩下结点G成为扩展结点，扩展得到两个叶子结点N、O，其价值分别为25和0。此时，存储活结点的堆已空，算法结束。算法搜索得到最优值为50。相应的最优解是从根结点A到结点L的路径。 ```cpp #include<stdio.h> #include<stdlib.h> #define MAXNUM 100 struct node{ int step; double price; double weight; double max,min; unsigned long choosemark; }; typedef struct node DataType; struct SeqQueue { int f,r; DataType q[MAXNUM]; }; typedef struct SeqQueue *PSeqQueue; PSeqQueue createEmptyQueue_seq(void) { PSeqQueue queue; queue=(PSeqQueue)malloc(sizeof(struct SeqQueue)); if (queue==NULL) printf("Out of space!!\n"); else queue->=queue->r=0; return queue; } int isEmptyQueue_seq(PSeqQueue queue) { return queue->f==queue->r; } void enQueue_seq(PSeqQueue queue, DataType x) { if((queue->r=1)%MAXNUM==queue->f) printf("Full Queue.\n"); else { queue->q[queue-r]=x; queue->r=(queue->r+1)%MAXNUM; } } void deQueue_seq(PSeqQueue queue) { if(queue->f==queue->r) { printf("Empty Queue.\n"); } else queue->f=(queue->f+1)%MAXNUM } DataType frontQueue_seq(PSeqQueue queue) { return (queue->q[queue->f]); } void sort(int n,double p[], double w[]) { int i,j; for(i=1;i<n-1;i++) for(j=1;i<n-1;j++) { double a=p[j]/w[j]; double b=p[j+1]/w[j+1] if(a<b) { double temp=p[j]; p[j]=p[j+1]; p[j+1]=temp; temp=w[j]; w[j]=w[j+1]; w[j+1]=temp; } } } double up(int k,double c, int n double p[], double w[]) { int i=k; double s=0; while(i<n&&w[i]<c) { s-=w[i]; s+=p[i]; i++; } if(i<n&&c>0) { s+=p[i]*c/w[i]; } return s; } double down(int k, double c, int n, double p[], double w[]) { int i=k; double s=0; while(i<n&&w[i]<0) { c-=w[i]; s+=p[i]; i++; } return s; } double solve(double c,int n, double p[], double w[], unsigned long* choosemark) { double min; PSeqQueue q=createEmptyQueue_seq(); DataType x={0,0,0,0,0,0}; sort(n,p,w); x.max=up(0,c,n,p,w); x.min=min=down(0,c,n,p,w); if (min==0) return -1; enQueue_seq(q,x); while(!isEmptyQueue_seq(q)) { int step; DataType y; x=frontQueue_seq(q); deQueue_seq(q); if (x.max<min) continue; step=x.step+1; if(step==n+1) continue; y.max=x.price+up(step,c-x.weight,n,p,w); if(y.max>=min) { y.min=x.price+down(step,c-x.weight,n,p,w); y.price=x.price; y.weight=x.weight; y.step=step; y.choosemark=x.choosemark<<1; if(y.min>=min) { min=y.min; if(step==n) *choosemark=y.choosemark; } enQueue_seq(q,y); } if(x.weight+w[step-1]<=c) { y.max=x.price+p[step-1]+up(step,c-x.weight-w[step-1],n,p,w); if(y.max>=min) { y.min=x.price+p[step-1]+down(step,c-x.weight-w[step-1],n,p,w); y.price=x.price+p[step-1]; y.weight=x.weight+w[step-1]; y.step=step; y.choosemark=(x.choosemark<<1)+1; if(y.min>=min) { min=y.min; if(step==n)*choosemark=y.choosemark; } enQueue(q,y); } } } return min; } #define n 3 double c=30; double p[n]={45,25,25}; double w[n]={16,15,15}; int main() { int i; double d; unsigned long choosemark; d=solve(c,n,p,w,&choosemark); if(d==1) printf("No solution!\n"); else{ for(i=0;i<n;i++) printf("x%d is %d\n",i+1,((choosemark & (1<<(n-1-i)))!=0)); } return 0; } ``` ## 10.4 贪心算法 贪心算法（Greedy Method）通过一系列的选择得到问题的解。它所做出的每一个选择都是当前状态下局部最好选择，即贪心选择。这种启发式的策略并不总能获得最优解. 然而在许多情况下的确能得到最优解。可以用贪心算法求解的问题一般具有两个重要的性质：贪心选择性质和最优子结构性质。 1. 贪心选择性质。贪心选择性质是指所求问题的整体最优解可以通过一序列局部最优的选择(贪心选择)来达到，它采用自顶向下的方式将所求问题简化为规模更小的子问题。 2. 最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。 第八章的Huffman算法就是贪心算法。 ## 10.5 动态规划法 动态规划法(Dynamic Programming)与分治法和回溯法都有某些类似，也是基于问题的划分解决方案(多步决策、递增生成子解)。动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。但在递增生成子解的过程中，力图朝最优方向进行，而且也不回溯。因此，动态规划法效率较高，且常用来求最优解，而不像回溯法那样可直接求全解。 使用动态规划的问题必须满足一定的条件∶即最优化原理(最优子结构性质)和子问题的重叠性。 1. 最优化原理(最优子结构性质) 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。 2. 子问题的重叠性 对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。 最长公共序列，略。 Last modification：January 20, 2023 © Allow specification reprint Like 如果觉得我的文章对你有用，请留下评论。