目录一 算法概述二 递归与分治策略三 动态规划四 贪心算法五 回溯法六 分支限界法七 随机化算法八 线性规划与网络流一 算法概述算法的概念通俗地讲算法是指解决问题的一种方法或一个过程。更严格地讲算法是由若干条指令组成的有穷序列。算法的性质1.输入有0个或多个由外部提供的量作为算法的输入。2.输出算法产生至少一个量作为输出。3.确定性组成算法的每条指令是清晰的无歧义的。4.有限性算法中每条指令的执行次数是有限的执行每条指令的时间也是有限的。程序与算法不同程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质4。例如操作系统是一个在无限循环中执行的程序因而不是一个算法。描述算法的多种方式自然语言方式表格方式伪代码等。算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上所需资源越多该算法的复杂性越高反之所需资源越少该算法的复杂性越低。对计算机资源最重要的是时间和空间资源。算法的复杂性有时间复杂性和空间复杂性。算法复杂性是算法运行需要的计算机资源的量。算法复杂性只依赖于要解的问题的规模、算法的输入和算法本身的函数。最坏情况、最好情况和平均情况下的时间复杂度从某个角度反映算法的效率各有局限性各有用处。可操作性最好且最有实际价值的是最坏情况下的时间复杂度。渐进符号类似ab类似ab类似ab类似ab类似ab二 递归与分治策略直接或间接地调用自身的算法称为递归算法。阶乘函数可以递归的表示int factorial(int n){ if(n0) return 1; return n*factorial(n-1); }斐波那契数列可以递归的表示int fibonacci(int n){ if(n1) return 1; return fibonacci(n-1)fabonacci(n-2); }排列问题Perm(t){ if(tn) print else for i t~n //让每个都做一下排头然后把剩下的全排列就变成了一个全新的全排列。 Swap(a[t],a[i]); Perm(t1); Swap(a[t],a[i]); //交换回来以便下一次全排列 }汉诺塔问题void hanoi(int n,int a,int b,int c){//参数b是目标塔座参数c是辅助塔座 //hanoi函数的任务是把n个圆盘通过辅助c塔,从a塔全搬到目标b塔 if(n0){ //如果n0,此时没有圆盘需要移动了 hanoi(n-1,a,c,b); //如果想把第n个移到目标就需要把上面的n-1个挪走到辅助塔座 move(a,b); // move 是一个圆盘从指定塔到另一个指定塔的移动 //执行完hanoi(n-1,a,c,b)之后就可以移动第n个到目标塔座了 hanoi(n-1,c,b,a); //这个时候在把辅助塔座上n-1个放到目标塔座的第n个上面 //此时n个汉诺塔的转移全部完成 } }分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题这些子问题相互独立且与原问题相同。递归地解这些子问题然后将各个子问题的解合并得到原问题的解。二分搜索算法采用分治策略可在最坏情况下用O(logn)的时间完成搜索任务。二分法的基本思想是将n个元素分成个数大致相同的两半取a[n/2]与x比较。如果xa[n/2]则找到x算法终止如果xa[n/2]则只在数组a的左半部继续搜索x如果xa[n/2]则只在数组a的右半部继续搜索x。int BinarySearch(int a[],int x,int n){ int left 0; int right n-1; while(left right){ int mid(leftright)/2; if(xa[middle]) return middle; if(xa[middle]) leftmiddle1; else rightmiddle-1; } return -1; }Strassen 矩阵乘法(分治法 减少矩阵乘法次数)矩阵乘法耗费的时间要比矩阵加(减)法耗费的时间多得多要想改进矩阵乘法的计算时间复杂性必须减少乘法运算。棋盘覆盖问题import java.util.Scanner; public class Main { static int tile 1; public static void main(String[] args) { Scanner scnew Scanner(System.in); int k sc.nextInt(); int dr sc.nextInt(); // 特殊方格所在行 int dc sc.nextInt(); // 特殊方格所在列 int[][] Board new int[(int) Math.pow(2, k)][(int) Math.pow(2, k)]; Board[dr][dc]0; ChessBoard(Board, 0, 0, dr, dc, Board.length); for (int i 0; i Board.length; i) { for (int j 0; j Board.length; j) { System.out.print(Board[i][j] \t); } System.out.println(); } } public static void ChessBoard(int Board[][],int r_0,int c_0,int dr,int dc,int size){ int s; int t; if (size1) return; ttile; ssize/2; if (drr_0s-1 dcc_0s-1) ChessBoard(Board,r_0,c_0,dr,dc,s); else{ Board[r_0s-1][c_0s-1]t; ChessBoard(Board,r_0,c_0,r_0s-1,c_0s-1,s); } if (drr_0s-1 dcc_0s) ChessBoard(Board,r_0,c_0s,dr,dc,s); else{ Board[r_0s-1][c_0s]t; ChessBoard(Board,r_0,c_0s,r_0s-1,c_0s,s); } if (drr_0s dcc_0s) //判断特殊方格是否在左下角子棋盘 ChessBoard(Board,r_0s,c_0,dr,dc,s); else //用t号骨牌覆盖右上角继续覆盖此子棋盘 { Board[r_0 s][c_0 s - 1] t; ChessBoard(Board, r_0 s, c_0, r_0 s, c_0 s - 1, s); } if (drr_0s dcc_0s) //判断特殊方格是否在右下角子棋盘 ChessBoard(Board,r_0s,c_0s,dr,dc,s); else //用t号骨牌覆盖左上角继续覆盖此子棋盘 { Board[r_0s][c_0s]t; ChessBoard(Board,r_0s,c_0s,r_0s,c_0s,s); } } }合并排序合并排序算法是用分治策略实现对n个元素的进行排序的算法其基本思想是将待排序元素分成大小大致相同的两个子集合分别对两个子集合进行排序最终将排好的子集合合并成要求的排好序的集合。MergeSort(int a[],int left,int right){ //left从左面指right从右面指 //MergeSort的作用是给数组a做合并排序 if(leftright){ int i(leftright)/2; //i取中间 MergeSort(a,left,i); //对左面合并排序 MergeSort(a,i1,right); //对右面合并排序 Merge(a,b,left,i,right); //排完序后合并到数组b,数组b是一个中间数组 Copy(a,b,left,right); //因为是给数组a排序所以把数组b原封不动挪到数组a } }快速排序算法是基于分治策略的另一个排序算法。其基本思想是对于输入的子数组a[p:r]按以下三个步骤进行排序。分解以a[p]为基准元素将a[p:r]划分成3段a[p:q-1]a[q]和a[q1:r]使a[p:q-1]中的任何一个元素小于等于a[q]而a[q1:r]中任何一个元素大于等于a[q]。下标q在划分过程中确定。递归求解通过递归调用快速排序算法分别对a[p:q-1]和a[q1:r]进行排序。合并由于对a[p:q-1]和a[q1:r]的排序使就地进行的因此在a[p:q-1]和a[q1:r]都已排好的序后不需要执行任何计算a[p:r]则已排好序。void QuickSort(int a[],int p,int r){ //QuickSort的功能是对a数组下标p到r的部分进行快速排序 if(pr){ //当pr,就要排的数了 int qPartition(a,p,r); //取下标q,从而分成左右两部分 //比a[q]小的放左边大的放右边 QuickSort(a,p,q-1); //对左边的进行排序 QuickSort(a,q1,r); //对右边的进行排序 } 不停的递归调用拆成两部分直到要排的只有一个数或不存在就停止 }三 动态规划动态规划的基本要素最优子结构性质重叠子问题性质动态规划算法与分治法类似其基本思想是将待求解问题分解成若干子问题先求解子问题再结合这些子问题的解得到原问题的解。与分治法不同的是适合用动态规划求解的问题经分解得到的子问题往往不是独立的。若用分治法来解这类问题则分解得到的子问题数目太多以致最后解决原问题需要耗费指数级时间。然而不同子问题的数目常常只有多项式量级。在用分治法求解时有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案在需要时再找出已求得的答案这样可以避免大量的重复计算从而得到多项式时间算法。所以动态规划又叫填表法动态规划适用于解最优化问题通常4个步骤1.找出最优解的性质并刻画其结构特征。2.递归地定义最优解。3.自底向上的方式计算最优值。4.根据计算最优值时得到的信息构造最优解。最优子结构问题的最优解包含了其子问题的最优解。重叠子问题递归自顶向下解问题时每次产生的子问题不总是新问题有些子问题被反复计算。动态规划对每个子问题只解一次然后将解保留在一个表格中。相同的子问题反复出现并且不同子问题的个数相对较小时用动态规划算法是有效的。矩阵连乘问题求需要的数乘次数最少假设A1A2A3矩阵维数分别是10*100100*55*50如果按((A1A2)A3)计算3个矩阵连乘积需要数乘次数10*100*510*5*507500如果按(A1(A2A3))计算3个矩阵连乘积需要数乘次数100*5*5010*100*5075000以此类推......将矩阵连乘积A1*A2*...*An记为A[i:j]。所以A[1:n]的计算量就是A[1:k]的计算量加上A[k1:An]的计算量再加上A[1:k]和A[k1:n]相乘的计算量。那么A[1:n]如果是最优的A[1:k]和A[k1:n]这俩必须也是最优的。设A[i,j]所需的最少乘次数为m[i][j]。其中k还未定k的位置有j-i种可能k是这j-i个位置中使计算量达到最小的那个位置。但是这样的话许多子问题被重复计算多次。所以还有记录最优断开位置的数组s和记录输入参数的数组p。void MatrixChain(int *p, int n, int **m, int **s){ for(int i1;in;i) m[i][i]0; //填表只有一个矩阵都没有矩阵和它乘数层数次数等于0 //也就是表的对角线都填0 for(int r2;rn;r){ for(int i1;in;i){ int jir-1; //对角线向上平移r格得新的斜线开始走这条新斜线这个斜线上列比行多r-1r从2到n //r最开始是2j比i多1总共两个矩阵相乘求连乘次数 //当rn已经把表填完了两个for嵌套循环结束 //很明显这是自底向下的 m[i][j]m[i1][j]p[i-1]*p[i]*p[j]; //m[i][j]最开始的初值 //默认是i处断开m[i][j]0m[i1][j]p[i-1]*p[i]*p[j] //左边乘次数0右边乘次数m[i1][j] //左右相乘次数p[i-1]*p[i]*p[j] s[i][j]i; //s[i][j]最开始的初值 for(int ki1;kj;k){ //for循环之后最优值t赋给m[i][j] int tm[i][k]m[k1][j]p[i-1]*p[k]*p[j]; if(tm[i][j]){ m[i][j]t; s[i][j]k; //i和j之间断开处为s[i][j](也就是k)的时候得到最优值 } } } } }计算次序如下图可以看出是自底向上。最开始填表解决的是简单问题最后得到复杂问题的解。备忘录方法与动态规划算法不同的是备忘录方法的递归方式是自顶向下的而动态规划算法则是自底向上递归的。因此备忘录方法的控制结构与直接递归方法的控制结构相同区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看避免了相同子问题的重复求解。最长公共子序列一个给定序列的子序列是在该序列中删除若干元素后得到的序列。最长公共子序列具有最优子结构的性质。递归结构/递归关系计算最优值最长公共子序列的长度c[m][n]X长度m,Y长度nvoid LCSLength(int m, int n, char *x, char *y ,int **c,int **b){ int i,j; for(i1;im;i) c[i][0]0; //j0的位置都填0因为Xi和一个空序列的公共子序列肯定空。 for(i1;in;i) c[0][i]0; //同理i0的位置都填0 for(i1;im;i){ for(j1;jn;j){ if(x[i]y[j]){ c[i][j]c[i-1][j-1]1; b[i][j]1; //b[i][j]用来记录c[i][j]的值是由哪个子问题得到的。 //1是XmYn,则ZkXmYn,且Zk-1是Xm-1和Yn-1的最长公共子序列也就是上上图的圈1和上图的中间那行。 } //下面是为了找c[i][j]的取值也就是c[i-1][j]和c[i][j-1]中更大的那个此时Xi和Yi的最后一个元素不相等。Xi和Yj的最长公共子序列应该和Xi-1和Yj的最长公共子序列或Xi和Yj-1的最长公共子序列相等要求长度最长取两者中较大的 else if(c[i-1][j]c[i][j-1]){ c[i][j]c[i-1][j]; b[i][j]2; //2是上上图的圈2 和 上图的第三行更大的是c[i-1][j] } else{ c[i][j]c[i][j-1]; b[i][j]3; //3是上上图的圈3 和 上图的第三行更大的是c[i][j-1] } } } }构造最长公共子序列//刚刚的代码只求了长度下面的代码可以打印最长公共子序列 void LCS(int i,int j, char *x, int **b){ if(i0||j0) 到头返回 return; if(b[i][j]1){ LCS(i-1,j-1,x,b); //x[i]和y[j]相等输出任意一个都行 coutx[i]; //相同元素的输出最后一定会把公共子序列的元素都输出出来。 } else if(b[i][j]2) LCS(i-1,j,x,b); //这种情况是Z是Xi-1和Yj的最长公共子序列 else LCS(i,j-1,x,b); //这种情况是Z是Xi和Yj-1的最长公共子序列 }最大字段和没画重点不写。四 贪心算法顾名思义贪心算法总是做出在当前看来是最好的选择。也就是说贪心算法并不从整体最优上加以考虑所做的选择只是在某种意义上的局部最优选择。虽然贪心算法不是对所有问题都能得到整体最优解但对范围相当广的许多问题能产生整体最优解如最小生成树问题、图的单源最短路径问题等。贪心算法的基本要素1.最优子结构性质一个问题的最优解包含其子问题的最优解。2.贪心选择性质所求问题可以的整体最优解可以通过一系列局部最优的选择(即贪心选择)来达到。贪心算法和动态规划算法都要求问题具有最优子结构性质。背包问题可以装一部分不一定全部装入可以用贪心算法求解而0-1背包问题要么装要么不装不能用贪心算法求解。对于0-1背包问题贪心选择之所以不能得到最优解是因为在这种情况下无法保证最终能将背包装满部分闲置的背包空间使每千克背包空间的价值降低了。事实上考虑0-1背包问题时应比较选择该物品和不选择该物品所导致的最终方案再做出最好选择。由此可导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。动态规划确实可以有效解决0-1背包问题。活动安排问题活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。各活动的起始时间和结束时间存储于数组s和f中且按时间排序的非减序列。void GreedySelector(int n, int s[], int f[], bool A[]){ A[1]true; //活动1要因为是最早结束的留给后面活动的时间多 int j1; //记录活动1的下标方便后面活动2的开始时间和活动1的结束时间做比较 for(int i2;in;i){ //n个活动 if(s[i]f[j]){ //活动2的开始时间和活动1的结束时间做比较 //一种情况时间没撞该活动可以被安排进来 A[i]true; //活动2的开始时间比活动1的结束时间晚时间没撞活动2可以被安排进来 //以此类推活动i的开始时间比活动j的结束时间晚时间没撞活动i可以被安排进来 ji; //活动i被安排进来更新活动i的下标用活动i的结束时间和下一个活动开始时间比较 } else //另一种情况时间撞了该活动不被安排进来 A[i]false; } }背包问题与0-1背包的区别看前面//n个物品 M背包容量 v[i]物品i的价值 w[i]物品i重量 x[i]物品i是否装进去 void Knapsack(int n, float M, float v[], float w[], float x[]){ Sort(n,v,w); //给n个物品按照单位价值进行降序排序 int i; for(i1;in;i) x[i]0; //默认每一个都不装 float cM; //c是背包剩余容量等于背包总容量M for(i1;in;i){ //从价值比较大的物品开始找 if(w[i]c) 如果第i个物品不能装下重量比背包剩余容量大跳出for循环而不是开始下一轮新的for循环 break; x[i]1; //如果第i个物品能装下重量比背包剩余容量大装物品ix[i]1表示装物品[i] c-w[i]; //装了物品i之后背包剩余容量减少 } if(in) //如果还有东西没装break导致的那就装c/w[i]取值再0没装和1全装之间 x[i]c/w[i]; //for如果没经过break,in1进不来上面的if,所有如果执行了上面的if一定是break了 }哈夫曼编码哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方式前缀码对每个字符规定一个01串作为其代码并要求任一字符的代码都不是其他代码的前缀。最优前缀码的二叉树总是一棵完全二叉树即树中任意结点都有两个儿子。构造哈夫曼编码有点多 回头再弄最小生成树构造最小生成树的Prim和Kruskal算法都可以看作应用贪心算法设计策略的典型例子。尽管他们做贪心选择的方式不同但他们都利用了下面的最小生成树性质MST性质。两种方法构造最小生成树Prim算法加点法Kruskal算法加边法五 回溯法回溯法有通用的解题法之称可以系统地搜索一个问题的所有解或任意解它是一个既带有系统性又带有跳跃性的搜索算法。在问题的解空间树中按深度优先策略从根结点出发搜索解空间树算法搜索至解空间树的任一结点时先判断该结点是否包含问题的解——如果肯定不包含则跳过对以该结点为根大的子树的搜索逐层向其祖先结点回溯否则进入该子树继续按深度优先策略搜索。回溯法求问题所有解时只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题解的算法称为回溯法适合解组合数较大的问题。回溯法的算法框架1.问题的解空间例如 0-1背包问题的解空间树2.回溯法的基本思想确定了解空间的组织结构后回溯法从开始结点根节点出发以深度优先方式搜索整个解空间。这个开始结点成为活结点同时成为当前的扩展结点。在当前的扩展结点处搜索向纵深方向移至一个新节点。这个新节点就成为新的结点并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动则当前扩展结点就成为了死结点。此时应往回移动回溯至最近的一个活结点处并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归地在解空间中搜索直至找到所要求的解或解空间中已无活结点为止。回溯法解旅行售货员问题某售货员要到若干城市去推销商品已知各城市之间的路程或旅费。他要选定一条从驻地出发经过每个城市一遍最后回到驻地的路线使总的路程或总旅费最小。回溯法搜索解空间树时通常采用两种策略来避免无效搜索提高回溯法的效率。其一是用约束函数在扩展结点处剪去不满足约束的子树其二是用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。解0-1背包问题的回溯法用剪枝函数减去导致不可行解的子树。解旅行售货员问题的回溯法如果从根结点到当前扩展结点处的部分周游路线费用已经超过当前找到的最好的周游路线费用则可以断定以该结点为根的子树中不含最优解因此可将该子树剪去。回溯法解题3个步骤1.针对问题定义解空间2.确定易于搜索的解空间结构3.以深度优先方式搜索解空间并在搜索过程中用剪枝函数避免无效搜索。3.递归回溯void Backtrack(int t){ //t表示递归深度 if(tn) //到叶节点 Output(x); //输出可行解 else{ for(int if(n,t);ig(n,t);i){ //没到叶节点就要继续递归 x[t]h(i); if(Constraint(t)Bound(t)){ //剪枝函数 Backtrack(t1); } } } }4.迭代回溯不考 跳了void IterativeBacktrack(void){ int t1; while(t0){ if(f(n,t)g(n,t)){ for(int if(n,t);ig(n,t);i){ x[t]h(i); if(Contraint(t)Bound(t)){ if(Solution(t)) Output(x); else t; } } } } }用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻算法只保存从根节点到当前扩展结点的路径。如果解空间树中从根节点到叶结点的最长路径的长度为h(n)则回溯法所需的计算空间通常为O(h(n))。5.子集树与排列树当所给的问题是从n个元素的集合S中找出满足某种性质的子集时相应的解空间树称为子集树。例如n个物品的0-1背包问题所对应的解空间树就是一棵子集树。当所给的问题是确定n个满足某种性质的排列时相应的解空间树称为排序树。例如旅行售货员问题所对应的解空间树就是一棵排列树。回溯法搜索子集树//子集树01两个取值表示解空间的某元素是要着还是不要着 void Backtrack(int t){ //t表示递归深度 if(tn) //到叶节点 Output(x); //输出可行解 else{ //没到叶节点就要继续递归 for(int i0;i1;i){ //两个选择01。左子树0右子树1 x[t]i; //对于0-1背包问题来说i1放包里i0不放包里 if(Constraint(t)Bound(t)){ //剪枝函数 Backtrack(t1); } } } }回溯法搜索排序树void Backtrack(int t){ //t表示递归深度 if(tn) //到叶节点 Output(x); //输出可行解 else{ //没到叶节点就要继续递归 for(int t;in;i){ Swap(x[t],x[i]); //如果把把剪枝条件去掉就和第二章递归的全排列问题一模一样 if(Constraint(t)Bound(t)){ //剪枝函数 Backtrack(t1); } Swap(x[i],x[t]); } } }n后问题之前的笔记里面写过子集树问题和上面的代码差不多n后问题 回溯笔记-CSDN博客0-1背包问题的回溯算法有点多回头补六 分支限界法分支限界类似回溯法也是在解空间上搜索问题解的算法。一般情况下分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解而分支限界法的求解目标是找出满足约束条件的一个解或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解即在某种意义下的最优解。分支限界法常以广度优先或以最小耗费最大效益优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树常见的有子集树和排列树。在搜索问题的解空间树时分支限界法与回溯法的主要区别在于它们对当前扩展结点所采用的扩展方式不同。在分支限界法中每个活结点只有一次机会成为扩展结点。活结点一旦称为扩展结点就一次性产生其所有儿子结点。在这些儿子结点中导致不可行解或者非最优解的儿子结点被舍弃其余儿子结点其余儿子结点被加入活结点表中。此后从活结点表中取下一结点成为当前扩展结点并重复上述结点扩展过程。这一过程一直持续到找到所需的解或活结点表为空为止。从活结点表中选择下一扩展结点的不同方式导致不同的分支限界。最常见的有以下两种方式。1.队列式(FIFO)分支限界法队列先进先出的原则。2.优先式队列分支限界法p值较小优先级较高最小费用优先的原则。代码部分这里目前还不明白P183老师说while里的很重要这里也是P186while里面比较重要七 随机化算法计算Π值的随机投点法//按面积在圆里概率等于Π/4投中圈内的点/总投点次数应该等于Π/4 double Darts(int n){ static RandomNumber dart; //随机投点的对象 int k0; //开始在圆里的点只有0个,k0 for(int i-1;in;i){ //随机投n个点 double xdart.fRandom(); 随机x double ydart.fRandom(); 随机y if((x*xy*y)1) 投中在1/4圆里计数加一 k; } return 4*k/double(n); }计算定积分double Darts(int n){ static RandomNumber dart; int k0; for(int i1;in;i){ double xdart.fRandom(); double ydart.fRandom(); if(yf(x)) //点在灰色区域 k; } return k/double(n); }主元素问题之前写过笔记主元素问题蒙特卡罗方法笔记-CSDN博客RandomNumber rnd; bool Majority(char *T,int n){ int irnd.Random(n)1; char xT[i]; int k0; for(int j1;jn;j) if(T[j]x) k; return (kn/2); }八 线性规划与网络流线性规划问题表示标准型要求1.目标函数最大2.约束条件等式3.等式左右的资源量是非负4.变量非负线性规划基本定理如果线性规划问题有最优解则必有一基本可行最优解。约束标准型线性规划问题的单纯形算法之前写过线性规划问题——单纯形算法_线性规划约束标准型c语言求解-CSDN博客