《算法基础笔记整理(共16页).docx》由会员分享，可在线阅读，更多相关《算法基础笔记整理(共16页).docx（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上算法重点总结一、引言算法基本概念1. 什么是算法：有限指令序列，对某个问题能够得出正确答案的规则集合2. 算法的特点：确定性，可终止性，可行性，输入，输出3. 算法规模：问题实例的大小，输入的大小4. 基本运算：主要的、关键的、耗时的最小操作5. 算法正确性及复杂度证明方法：反证法、数学归纳法（p(a)成立，且对每个na，只要p(n-1)成立，p(n)一定成立）6. 算法分析标准：正确性、工作量、占用空间量：算法运行过程中的内存占用情况、简单性和清晰性、最优性（即算法的上界（工作量的上界）等于求解问题的下界（问题固有的复杂度）7. 算法选择方法：经验法和理论法（常用）
2、8. 算法的时间复杂度表示方法：大O表示上界，表示下界，表示同阶9. 选择排序：每次选择序列中最小值放在有序序列尾部（与无序数列头部元素交换）10. 插入排序：将当前元素与前向有序数列比较，查找插入位置，移动后插入二、贪心算法1. 贪心算法的一般特性1) 优化问题：建立候选对象集2) 建立对象集合：划分解对象集和抛弃对象集3) 求解终止函数：判断解对象集是否是问题的解或者求解是否结束（未必是最优解）4) 可行解函数：判断候选对象集元素是否可以加入到当前解的对象集中（未必是最优解）5) 选择函数：指出哪个剩余的候选对象最有可能构成问题的解6) 目标函数：给出问题的解2. 贪心算法求解模版func
3、tion greedy (C : set) : set 构造候选对象集S=创建解对象集while C and not solution(S) do循环构造解对象集x=select(C)选取C=Cx去除if feasible(Sx) then S=Sx可否加入？if solution(S) then return S输出解else return“No solution”未找到解3. 找零问题的一般特性（1）找最少硬币数，候选对象集 100,25,10,5,1（2）一选到的硬币集和未被选的硬币集（3）判断解函数（solution）,检查目前已选的硬币集中的金额是否等于要找的钱数（4）如果集合中硬币
4、钱数不超过应找金额，则该集合是可行的（5）选择函数（selection）,从未选硬币集合中找一个面值最大的硬币（6）目标函数（object）：计算硬币金额4. 图：最小生成树算法的一般特性1) 优化问题：建立候选图的边集2) 建立集合：已选中的边集MST，未选边集E-MST3) 求解终止函数：如果MST构成生成树，则它是一个解4) 解存在函数：候选边加入MST构不成回路，则该边可以加入MST5) 选择函数：prim算法选择U和V-U之间的最小边加入MST；KrusKal算法从未选边中选最小边加入MST6) 目标函数：计算MST中边权值和5. Kruskal算法思想（1）将所有边按权由小到大排列
5、 ；（2）MST置空；（3）依次取最小边（u,v）：* 若（u,v）加入MST不构成回路则将（u,v）加入MST;* 若MST中的边达到n-1条，则结束；Kruskal算法证明：归纳G的边数归纳基础：当G只有一条边，显然G就是最小生成树；归纳假设：设T中有sn-1条边时，T是有希望成为最有解的。当向T中再加一条最小边（u,v）时，且进入后不会使T构成回路。原T中有若干联通分量，加入（u,v）后，减少一个。所以加入后T仍然是有希望成为最有解的。所以算法结束后，T中有n-1条边，构成了生成树，且为最优。6. Prim算法思想（1）解集合T为空，B为任意顶点（2）从B和V-B之间的边中选一最小边(u
6、,v), u属于B,v属于V-B（3）将(u,v)加入T,将v加入B（4）重复(2)-(3)n-1次Prim算法证明：归纳于T中边的数目，如果T在任何步骤都是有希望的，则往T里加一条边后，仍然是有希望的。7. 图：单源最短路径（非负边）Dijkstra算法O(n2)Function Dijkstra(L1.n,1.n) : array2.n array D2.n C=2,3,n for i=2 to n do Di=L1,i for i=2 to n do v=some element of C minimizing Dv C=Cv for each wC do Dw=minDw,Dv+Lv,
7、w return DDijkstra算法证明：（数学归纳法）(a)如果一个顶点i满足i1，且i在S中，则Di给出了从源到i的最短路径长度。(b)一个顶点i不在S中，则Di给出了从源到i的最短特殊路径长度。（i的前驱在S中）8. 贪心算法背包问题（可分割）Function knapsack(w1.n,v1.n):array1.n for i=1 to n do xi=0 weight=0; while weightW do i=the best remaining object seletion if weight+wi=W then xi=1 weight=weight+wi else xi=
8、(W-weight)/wi weight=W return x如果根据v/w（价重比）降序顺序选择物品，则knapsack算法可以找到最优解9 贪心算法删数问题算法思想：利用数组（优化问题），输入数字序列组成待选集合，用初始输入数字序列作为解集合和初始抛弃集合为空（建立对象集合）。循环中，每次从解集合中去除一个数加入到抛弃集合中（可行解函数），使得解集合数列最大（选择函数），循环结束（求解终止函数）后所得解集合为所求最大值（目标函数）。选择函数：从高位向低位，比较相邻两位数字大小，若高位比低位数字大，则将高位加入到抛弃集合中，若高位比低位小，则向低位移动继续比较。10 贪心算法会场安排问题算法
9、思想：利用数组（优化问题），记录活动开始时间和结束时间，按结束时间排序建立待选集合，初始解集合为空（建立对象集合）。循环中，从待选集合中选择结束时间较早的活动，令其与解集合最后一项活动比较两者是否相容（待选会议开始时间大于解集合中会议结束时间），若两者相容，则将待选会议加入到解集合中，若不相容，抛弃当前待选会议，从待选集合中选择下一项。三、 分治算法（递归分治算法）1. 分治算法的一般三要素：（1）定义一个最小规模的问题，并给出其解（2）把复杂的问题划分为同类型的若干规模较小的子问题，并分别解决子问题（3）把各子问题的解组合起来，即可得到原问题的解2. 分治算法模版：Function DC(x
10、) if xTn then return 0 else return binRec(T1.n,x)Function binRec(Ti.j,x) if ij then return 0 k=(i+j)/2 if x=Tk then return k else if xTk then return binRec(Ti.k-1,x) else return binRec(Tk+1.j,x)4. 分治算法归并排序算法：算法思想：比较两个有序数列首部，取较小值放入解集合，并删除其在原数列中的数据。若某一数列为空，则依次取非空数列元素加入解集合即可。若两个数列无序，则将两个无序数列递归分割，最终得到两个
11、只有一个元素的数列（即为有序），对其进行归并操作。Procedure merge(U,V,T) i=j=1 Um+1=Vn+1= 哨兵 for k=1 to m+n do if Uip or k=j repeat L=L-1 until Tk=p while kp Repeat L=L-1 until Tk=pProcedure quickSort(Ti.j) if j-i 足够小 insert(Ti.j) else pivot(Ti.j,l) quickSort(Ti.l-1) quickSort(Tl+1.j)6. 分治法求幂算法：算法思想：1最简单问题：n=0，解是12. 问题分解： a
12、n=an-1*a3.解的合成：an=an-1*aProcedure power(a,n): integer if n=0 then return 1 return a*power(a,n-1)四、 动态规划算法1. 动态算法基本思想：用表记录已解决子问题的答案，需要时再找出已求得的答案，避免重复计算，即用空间换取时间，提高解题效率。2. 动态规划设计方法：（1）基于递归算法设计动态规划算法：递归算法对分解的每个子问题都要递归求解，其中可能有许多子问题重复计算，导致效率低下。为避免这种重复，可以将递归算法改写为动态规划算法；（2）基于问题结构设计；3. 动态规划的基本步骤：（1）找出最优解的性质
13、，并刻画其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造一个最优解。（该步骤是求最优解的必须步骤）4. 最优性原则（principle of optimality）：构造最优解所面临的子问题解都是最优的。解决一个问题的过程中，需要依次作出n个决策D1,D2,Dn,若这个决策序列是最优的，对于任何一个整数k，1k=wi) mij=max(mi-1j,mi-1j-wi+vi); else mij=mi-1j; 7. 矩阵乘法链（1） 最优解结构：将矩阵Ai乘到Aj简记为Ai:j(1=i=j=n)，其最少数乘次数为mij，原问题的最优值为
14、 m1n（即矩阵链不需要断开），当i=j时（只有一个矩阵），mij=0；（2） 递归定义最优值：当i=j时，mij=0；当ij时，若计算Ai:j的最优次序在k和k+1之间断开，则有mij=minmik+mk+1j+pi-1*pk*pj (i=k=j)，若将对应于mij的断开位置记为sij，在计算出最优值mij后，可以递归地由sij构造出相应的最优解（3） 递归计算最优解：动态规划计算时，依照递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。时间复杂度O(n3)（4） 构造最
15、优解：从s1n记录的信息可知计算A1:n的最优加括号方式为(A1:s1n)(As1n+1:n)。同理，每个部分的最优加括号方式又可以根据数组s的相应元素得出。照此递推下去，最终可以确定A1:n的最优完全加括号方式，即构造出问题的一个最优解。void matrixChain (int * p, int n, int * * m, int * * s) for ( int i=1;i=n;i+) mii=0; for ( int r=2;r=n;r+) /链长度控制 for ( int i=1;i=n-r+1;i+) /链起始位置 int j=i+r-1; /链终止位置 mij=mi+1j+pi-
16、1*pi*pj; sij=i; for ( int k=i+1;kj;k+) int t=mik+mk+1j+pi- 1*pk*pj; if (tmij) mij=t; sij=k; 8. 最长公共子序列问题（LCS）算法思想：如有两个序列（S1=1,3,4,5,6,7,7,8和S2=3,5,7,4,8,6,7,8,2）。假如S1的最后一个元素 与 S2的最后一个元素相等，那么S1和S2的LCS就等于 S1减去最后一个元素 与 S2减去最后一个元素 的 LCS 再加上 S1和S2相等的最后一个元素。假如S1的最后一个元素 与 S2的最后一个元素不等（本例子就是属于这种情况），那么S1和S2的L
17、CS就等于：S1减去最后一个元素 与 S2 的LCS， S2减去最后一个元素 与 S1 的LCS 中的最大的那个序列。（1）最优解结构：设序列 X=和Y=的一个最长公共子序列Z=，则：若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的LCS；若xmyn且zkxm ，则Z是Xm-1和Y的LCS ； 若xmyn且zkyn ，则Z是X和Yn-1的LCS 。 其中Xm-1=，Yn-1=，Zk-1=。（2）递归最优解：（3） 计算最优解：LCS_LENGTH(X,Y)以序列X=和Y=作为输入。输出两个数组c0.m ,0.n和b1.m ,1.n。其中ci,j存储Xi与Yj的最长公共子序列的长
18、度，bi,j记录指示ci,j的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于cm,n中。 由于每个数组单元的计算耗费(1)时间，算法LCS_LENGTH耗时(mn)。（4） 构造最长公共子序列：从bm,n开始，沿着其中的箭头所指的方向在数组b中搜索。Procedure LCS_LENGTH(X,Y); m:=lengthX; n:=lengthY; for i:=1 to m do ci,0:=0; for j:=1 to n do c0,j:=0; for i:=1 to m do for j:=1 to n do if xi=yj t
19、hen ci,j:=ci-1,j-1+1; bi,j:=“; else if ci-1,jci,j-1 then ci,j:=ci-1,j; bi,j:=“; else ci,j:=ci,j-1; bi,j:=”; return(c,b); 五、 搜索图算法1. 基本思想：（1） 状态空间（Status Space）：所有状态的集合（2） 状态变迁（产生式）：有一个状态变为另一个状态的规则（3） 开始状态（Initial Status）：问题的初始状态（4） 终止状态(End Status)：问题的目标状态2. 深度优先的算法是回溯法，其基本思想：回溯法在问题的解空间树中，按深度优先策略，从根
20、结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。（1） 针对所给问题，定义问题的解空间；（2） 确定易于搜索的解空间结构；（3） 以深度优先方式搜索解空间，在搜索过程中可用剪枝函数（约束函数、限界函数）避免无效搜索。3. 广度优先搜索算法，分支限界法基本思想：每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从
21、活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。六、 概率算法1. 概率算法有两类（1） 给出概率性答案（精度不同，也可能错误）：数值概率算法、Monte Carlo算法（2） 随机搜索找到最优解：Las Vegas算法2. 蒙特卡罗算法基本思想：依概率给出问题的解，但解有可能是错误的，增加时间代价可能减小错误概率3. 拉斯维加斯算法基本思想：进行概率性选择，帮助和指导我们更快地得到正确的解。不会给出错误答案，而给出一个提示。该算法有两种，一种总能给出正确答案，只是选择不合适时，花的时间长；另一种选择不恰当，可能导致算法陷入绝境
22、，它会报告找不到解。七、 算法复杂性1. P类问题（有效算法）多项式界算法（Polynomially Bounded Algorithms）：时间复杂度的上界是多项式，即：T(n)=O(P(n)P类问题：具有多项式界算法的判定问题，P属于NP例如：（1）图G=(V,E)是连通的吗？（2）图G=(V,E,W)有边权之和小于等于L的生成树吗？（3）在图G=(V,E)中，顶点v,u间有路径吗？2. NP类问题NP类问题：判定问题A, 如果给定一个解C，有一个多项式界的算法A可以确定C是一个正确的解。算法A返回true或false（如果C不是A的解，也可能陷入死循环，无结果）例如：TSP问题、团的问题
23、3. NP-Complete问题NP-Complete问题：所有NP问题都可多项式时间归约为问题A，则A是NP-Complete问题，NP-Complete属于NP4. 近似算法近似算法是一种多项式时间算法，不能保证得到问题的最优解，但可以得到近似最优解的解，其特点是平均时间复杂度是P(n)，且大多数情况下能得到较满意的解。近似算法也叫启发式算法。八、 遗传算法1. 遗传算法基本步骤：a)初始化（个体编码）：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。 b)个体评价（适应度函数）：计算群体P(t)中各个个体的适应度。 c)选择运算：将选择算子作用于群体。
24、选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。 f)终止条件判断：若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。2. 遗传算法特点 首先组成一组候选解 依据某些适应性条件测算这些候选解的适应度 根据适应度保留某些候选解，放弃其他候选解 对保留的候选解进行某些操作，生成新的候选解。3. 哈密尔顿回路问题九、 模拟退火算法1. 基本要素和设定方法专心-专注-专业