2014华南理工大学广州学院,算法设计与分析期末考试复习PPT.ppt

复习,考试题型：选择题（算法类型、时间复杂度，共15题，30分）简答题（设计思想，共2题，12分）应用题（解题步骤、搜索空间树等，共4题，48分）编程题（上机实验题，作业题等，共1题，10分）,复习,2019/11/25,复习,Page3,2019/11/25,Page3,算法的几种描述方法（重点掌握伪代码和C+语言，会使用伪代码写算法）；理解大O符号的含义；算法的几个重要特性：输入、输出、有穷性、确定性、可行性。,第一章、第二章,自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想注意事项：避免写成自然段,算法的几种描述方法（重点掌握伪代码和C+语言，会使用伪代码写算法）；,流程图优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次,程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：尽量将算法写成子函数,伪代码算法语言伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解,理解大O符号的含义；时间复杂度,算法的五大特性：,2019/11/25,第1章算法设计基础,Page9,输入：一个算法有零个或多个输入。输出：一个算法有一个或多个输出。有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。算法的有穷性意味着不是所有的计算机程序都是算法.确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现（每步可执行）。,2019/11/25,复习,Page10,2019/11/25,Page10,蛮力法的基本思想（重要！）:蛮力法依赖的基本技术扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;关键依次处理所有元素。,第三章蛮力法,2019/11/25,复习,Page11,2019/11/25,Page11,熟记哪些问题使用了蛮力法进行解决：顺序查找、串匹配（KMP,BM,BF），选择排序，冒泡排序，生成排列对象，生成子集，0/1背包，任务分配，哈密顿回路，TSP，最近对问题，凸包问题，7-11问题，百钱买百鸡问题；并熟记这些问题的时间复杂度；,第三章蛮力法,2019/11/25,复习,Page12,2019/11/25,Page12,其中：BF：依次扫描，对比，O(n+m)；KMP：依次扫描，对比（虽然这个“依次”已经是按照一定的规律，效率较高），O(n+m)，注意：对于KMP算法，必须求出next数组；选择排序：扫描整个序列，找到整个序列的最小记录和序列中的第一个记录交换位置，再扫第二小，依此类推，O(n2)；,第三章蛮力法,2019/11/25,复习,Page13,2019/11/25,Page13,其中：冒泡排序：扫描整个序列，在扫描过程中两两比较相邻记录，如果反序则交换，直到n-1趟扫描后，即排好序，O(n2)；TSP：把所有可能的回路都找出来，就可以得到最短路径，O(n!)；7-11：把所有可能都计算一遍，就能得到正确的解；百钱买百鸡：把所有可能都计算一遍，就能得到正确的解。,第三章蛮力法,2019/11/25,复习,Page14,2019/11/25,Page14,冒泡排序、选择排序、TSP问题的设计思想和伪代码（可能出简答题）7-11问题、百钱买百鸡问题的代码实现（猜测是编程题）,第三章蛮力法,冒泡排序,设计思想,选择排序,设计思想,TSP问题,设计思想,TSP问题：旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。用蛮力法解决TSP问题，可以找出所有可能的旅行路线，从中选取路径长度最短的简单回路。,注意到，在图中有3对不同的路径，对每对路径来说，不同的只是路径的方向，因此，可以将这个数量减半，则可能的解有(n-1)!/2个。这是一个非常大的数，随着n的增长，TSP问题的可能解也在迅速地增长。用蛮力法求解TSP问题，其时间复杂性为O(n!)，只能解决问题规模很小的实例。,一个简单的例子百元买百鸡问题已知公鸡5元一只，母鸡3元一只，小鸡1元三只，用100元钱买100只鸡，问公鸡、母鸡、小鸡各多少只？,voidchicken()intx,y,z;for(x=0;x=20;x+)for(y=0;y=33;y+)z=100-x-y;if(z%3=0),（编程，代码要记牢）,7-11问题（编程，代码要记牢）,设计蛮力算法找出四件物品的价格各是什么？#includevoidmain()inta,b,c,d;for(a=1;a=711;a+)for(b=1;b=711;b+)for(c=1;c=711;c+)d=711-a-b-c;if(a*b*c*d=711)couta/100.0tb/100.0tc/100.0td/100.014,714,14=14,查找成功！,选择下列数字序列中的第3小的元素12,5,8,44,23,7,9,2,2019/11/25,复习,Page40,2019/11/25,Page40,动态规划法的基本思想（重要！自底向上，理解+应用）：将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。,第六章动态规划法,2019/11/25,复习,Page41,2019/11/25,Page41,动态规划法的求解过程：分成相互重叠的子问题；求解子问题，填表；自底向上计算出原问题的解。,第六章动态规划法,2019/11/25,复习,Page42,2019/11/25,Page42,熟记哪些问题使用了动态规划法进行解决：TSP，多段图的最短路径问题，0/1背包，最长公共子序列问题，最优二叉查找树，近似串匹配问题；并熟记这些问题的时间复杂度：多段图的最短路径问题：O(n+m)0/1背包问题：O(nC),第六章动态规划法,2019/11/25,第6章动态规划法,Page43,用动态规划法解决多段图的最短路径问题，写出求解过程（可能出应用题）,第六章动态规划法,2019/11/25,第6章动态规划法,Page45,根据动态规划函数，用一个(n+1)(C+1)的二维表V，Vij表示把前i个物品装入容量为j的背包中获得的最大价值。,实例：有5个物品，其重量分别是2,2,6,5,4，价值分别为6,3,5,4,6，背包的容量为10。,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,6,6,6,6,6,6,6,6,0,6,6,9,9,9,9,9,9,9,0,6,6,9,9,9,9,11,11,14,0,6,6,9,9,9,10,11,13,14,0,6,6,9,9,12,12,15,15,15,x5=1,x4=0,x3=0,x2=1,x1=1,用动态规划法解决0/1背包问题，写出求解过程。（可能出应用题）,物品,容量,2019/11/25,复习,Page46,2019/11/25,Page46,贪心法的基本思想（重要！局部最优，理解+应用）：贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。,第七章贪心法,2019/11/25,复习,Page47,2019/11/25,Page47,熟记哪些问题使用了贪心法进行解决：TSP，图着色问题，最小生成树问题（Prim算法、Kruskal算法），背包问题，活动安排问题，多机调度问题，哈弗曼编码；并熟记这些问题的时间复杂度：,第七章贪心法,2019/11/25,复习,Page48,2019/11/25,Page48,其中：背包问题：每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，O(nlog2n)。注意：背包问题要求装满整个背包，最后一个物体若装不下一个整体，可以装其中的一部分。,第七章贪心法,2019/11/25,复习,Page49,2019/11/25,Page49,背包问题的贪心算法设计思想和伪代码；给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?4.用贪心法解决背包问题，写出求解过程（第7章作业：先按单位价值重量比排序，再依次放置物品，最后求出总价值，写出）（可能出应用题）,第七章贪心法,背包问题（可能出简答题）,设计思想有三种看似合理的贪心策略：（1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。（2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。（3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。,2019/11/25,第7章贪心法,Page51,12050背包180190200(a)三个物品及背包(b)贪心策略1(c)贪心策略2(d)贪心策略3,例如，有3个物品，其重量分别是20,30,10，价值分别为60,120,50，背包的容量为50，应用三种贪心策略装入背包的物品和获得的价值如图所示。,2019/11/25,复习,Page53,2019/11/25,Page53,回溯法的基本思想（深度优先搜索，理解+应用）：从根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。,第八章回溯法,2019/11/25,复习,Page54,2019/11/25,Page54,熟记哪些问题使用了回溯法进行解决：图m着色问题，哈密顿回路问题，八皇后问题（4皇后问题），批处理作业调度问题；,第八章回溯法,3.用回溯法解决m颜色图着色问题，画出搜索空间图；（可能出应用题）图的m着色问题描述为：给定无向连通图G=(V,E)和正整数m，判断能否用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。,4.画出用回溯法求解8皇后或4皇后问题的搜索过程（课本P161）（可能出应用题）,八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在88的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在nn的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。,回溯法求解4皇后问题的搜索过程,2019/11/25,复习,Page57,2019/11/25,Page57,分支限界法的基本思想：首先确定一个合理的限界函数，并根据限界函数确定目标函数的界down,up；按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值；如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表PT）中；依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点；重复上述过程，直到找到最优解。,第九章分支限界法,2019/11/25,复习,Page58,2019/11/25,Page58,分支限界法的基本思想：当搜索到一个叶子结点时，如果该结点的目标函数值是表PT中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表PT中的结点，将超出目标函数界的结点丢弃，然后从表PT中选取使目标函数取得极值的结点继续进行扩展。,第九章分支限界法,2019/11/25,复习,Page59,2019/11/25,Page59,熟记哪些问题使用了分支限界法进行解决：TSP，多段图的最短路径问题，任务分配问题，批处理作业调度问题，0/1背包；并熟记这些问题的时间复杂度；用分支限界法解决任务分配问题，画出搜索空间。（可能出应用题）用分支限界法解决0/1背包问题，画出搜索空间。（可能出应用题）,第九章分支限界法,2019/11/25,第9章分支限界法,Page60,任务分配问题要求把n项任务分配给n个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。如图9.10所示是一个任务分配的成本矩阵。,任务分配问题（可能出应用题）,2019/11/25,第9章分支限界法,Page61,求最优分配成本的上界和下界考虑任意一个可行解，例如：矩阵中的对角线是一个合法的选择，表示将任务1分配给人员a、任务2分配给人员b、任务3分配给人员c、任务4分配给人员d，其成本是9+4+1+4=18；或者应用贪心法求得一个近似解：将任务2分配给人员a、任务3分配给人员b、任务1分配给人员c、任务4分配给人员d，其成本是2+3+5+4=14。显然，14是一个更好的上界。为了获得下界，考虑人员a执行所有任务的最小代价是2，人员b执行所有任务的最小代价是3，人员c执行所有任务的最小代价是1，人员d执行所有任务的最小代价是4。因此，将每一行的最小元素加起来就得到解的下界，其成本是2+3+1+4=10。需要强调的是，这个解并不是一个合法的选择（3和1来自于矩阵的同一列），它仅仅给出了一个参考下界，这样，最优值一定是10,14之间的某个值。,2019/11/25,第9章分支限界法,Page62,图9.11分支限界法求解任务分配问题示例(表示该结点被丢弃，结点上方的数组表示搜索顺序),搜索空间,分支限界法求解0/1背包问题（可能出应用题）,例：0/1背包问题。假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=1