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

《华南理工大学广州学院算法设计与分析期末考试复习.pptx》由会员分享，可在线阅读，更多相关《华南理工大学广州学院算法设计与分析期末考试复习.pptx（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、考试题型：考试题型：选择题（算法类型、时间复杂度，共选择题（算法类型、时间复杂度，共15题，题，30分）分）简答题（设计思想，共简答题（设计思想，共2题，题，12分）分）应用题（解题步骤、搜索空间树等，共应用题（解题步骤、搜索空间树等，共4题，题，48分）分）编程题（上机实验题，作业题等，共编程题（上机实验题，作业题等，共1题，题，10分）分）复习复习第1页/共68页2023/3/21复习Page 22023/3/21Page 2算法的几种描述方法（重点掌握伪代码和算法的几种描述方法（重点掌握伪代码和C+语言，会使用伪代码写算法）；语言，会使用伪代码写算法）；理解大理解大O符号的含义；符号的含

2、义；算法的几个重要特性：算法的几个重要特性：输入、输出、有穷性、确定性、可行性。第一章、第二章第一章、第二章第2页/共68页自然语言自然语言r优点：容易理解优点：容易理解r缺点：冗长、二义性缺点：冗长、二义性r使用方法：粗线条描述算法思想使用方法：粗线条描述算法思想 r注意事项：避免写成自然段注意事项：避免写成自然段算法的几种描述方法（重点掌握伪代码和C+语言，会使用伪代码写算法）；第3页/共68页 流程图流程图 r优点：流程直观优点：流程直观 r缺点：缺少严密性、灵活性缺点：缺少严密性、灵活性r使用方法：描述简单算法使用方法：描述简单算法r注意事项：注意抽象层次注意事项：注意抽象层次第4页/

3、共68页程序设计语言程序设计语言r优点：能由计算机执行优点：能由计算机执行 r缺点：抽象性差，对语言要求高缺点：抽象性差，对语言要求高r使用方法：算法需要验证使用方法：算法需要验证r注意事项：注意事项：尽量将算法写成子函数尽量将算法写成子函数第5页/共68页 伪代码伪代码算法语言算法语言r伪代码（伪代码（Pseudocode）：介于自然语言和）：介于自然语言和程序设计语言之间的方法，它采用某一程序设程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语计语言的基本语法，操作指令可以结合自然语言来设计。言来设计。r优点：表达能力强，抽象性强，容易理解优点：表达能力强，抽

4、象性强，容易理解第6页/共68页理解大O符号的含义；时间复杂度第7页/共68页r算法的五大特性：2023/3/21第1章 算法设计基础Page 8输入：输入：一个算法有零个或多个输入。一个算法有零个或多个输入。输出：输出：一个算法有一个或多个输出。一个算法有一个或多个输出。有穷性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。一步都在有穷时间内完成。算法的有穷性意味着不是所有算法的有穷性意味着不是所有的计算机程序都是算法的计算机程序都是算法.确定性：确定性：算法中的每一条指令必须有确切的含义，对于相算法中的每一条指令必须有确

5、切的含义，对于相同的输入只能得到相同的输出。同的输入只能得到相同的输出。可行性：可行性：算法描述的操作可以通过已经实现的基本操作执算法描述的操作可以通过已经实现的基本操作执行有限次来实现（每步可执行）。行有限次来实现（每步可执行）。第8页/共68页2023/3/21复习Page 92023/3/21Page 91.蛮力法的基本思想（蛮力法的基本思想（重要！重要！）:蛮力法依赖的基本技术蛮力法依赖的基本技术扫描技术扫描技术，即采，即采用一定的策略将待求解问题的用一定的策略将待求解问题的所有元素依次所有元素依次处理一次处理一次，从而找出问题的解，从而找出问题的解;关键依次处理所有元素。第三章第三章

6、 蛮力法蛮力法第9页/共68页2023/3/21复习Page 102023/3/21Page 102.熟熟记记哪哪些些问问题题使使用用了了蛮蛮力力法法进进行行解解决决：顺顺序序查查找找、串串匹匹配配（KMP,BM,BF），选选择择排排序序，冒冒泡泡排排序序，生生成成排排列列对对象象，生生成成子子集集，0/1背背包包，任任务务分分配配，哈哈密密顿顿回回路路，TSP，最最近近对对问问题题，凸凸包包问问题题，7-11问问题题，百百钱钱买买百鸡问题百鸡问题；并熟记这些问题的；并熟记这些问题的时间复杂度时间复杂度；第三章第三章 蛮力法蛮力法第10页/共68页2023/3/21复习Page 112023/

7、3/21Page 11其中：其中：BF：依次扫描依次扫描，对比，对比，O(n+m)；KMP：依次扫描依次扫描，对比（虽然这个，对比（虽然这个“依次依次”已已经是按照一定的规律，效率较高），经是按照一定的规律，效率较高），O(n+m)，注意：对于，注意：对于KMP算法，必须求出算法，必须求出next数组；数组；选择排序：扫描整个序列扫描整个序列，找到整个序列的最，找到整个序列的最小记录和序列中的第一个记录交换位置，再扫小记录和序列中的第一个记录交换位置，再扫第二小，依此类推第二小，依此类推，O(n2)；第三章第三章 蛮力法蛮力法第11页/共68页2023/3/21复习Page 122023/3/

8、21Page 12其中：其中：冒泡排序：冒泡排序：扫描整个序列扫描整个序列，在扫描过程中两两，在扫描过程中两两比较相邻记录，如果反序则交换，直到比较相邻记录，如果反序则交换，直到n-1趟扫趟扫描后，即排好序，描后，即排好序，O(n2)；TSP：把：把所有可能所有可能的回路都找出来，就可以得的回路都找出来，就可以得到最短路径，到最短路径，O(n!)；7-11：把：把所有可能所有可能都计算一遍，就能得到正确都计算一遍，就能得到正确的解；的解；百钱买百鸡：把百钱买百鸡：把所有可能所有可能都计算一遍，就能得都计算一遍，就能得到正确的解。到正确的解。第三章第三章 蛮力法蛮力法第12页/共68页2023/

9、3/21复习Page 132023/3/21Page 133.冒泡排序、选择排序、冒泡排序、选择排序、TSP问题的设计思想和伪代码问题的设计思想和伪代码（可（可能出简答题）能出简答题）4.7-11问题、百钱买百鸡问题的代码实现问题、百钱买百鸡问题的代码实现（猜测是编程题）（猜测是编程题）第三章第三章 蛮力法蛮力法第13页/共68页冒泡排序设计思想第14页/共68页选择排序设计思想第15页/共68页TSP问题设计思想 TSP问题：旅行家要旅行问题：旅行家要旅行n个城市然后回到出个城市然后回到出发城市，要求发城市，要求各个城市经历且仅经历一次，并要求各个城市经历且仅经历一次，并要求所走的路程最短。

10、所走的路程最短。用蛮力法解决用蛮力法解决TSP问题，可以问题，可以找出所有可能的找出所有可能的旅行路线，从中选取路径长度最短的简单回路。旅行路线，从中选取路径长度最短的简单回路。第16页/共68页8abdc23571序号路径路径长度是否最短1abcda18 否2abdca11 是3acbda23 否4acdba11 是5adbca23 否6adcba18 否 注注意意到到，在在图图中中有有3对对不不同同的的路路径径，对对每每对对路路径径来来说说，不不同同的的只只是是路路径径的的方方向向，因因此此，可可以以将将这这个个数数量量减减半半，则则可可能能的的解解有有(n-1)!/2个个。这这是是一一个

11、个非非常常大大的的数数，随随着着n的的增增长长，TSP问问题题的的可可能能解解也也在在迅迅速速地地增增长长。用用蛮蛮力力法法求求解解TSP问问题题，其时间复杂性为其时间复杂性为O(n!)，只能解决问题规模很小的实例。，只能解决问题规模很小的实例。第17页/共68页一个简单的例子一个简单的例子百元买百鸡问题百元买百鸡问题已知公鸡已知公鸡5元一只，母鸡元一只，母鸡3元一只，元一只，小鸡小鸡1元三只元三只，用，用100元钱买元钱买100只鸡，问只鸡，问公鸡、母鸡、小鸡各多少只？公鸡、母鸡、小鸡各多少只？voidchicken()intx,y,z;for(x=0;x=20;x+)for(y=0;y=3

12、3;y+)z=100-x-y;if(z%3=0)&(5*x+3*y+z/3=100)cout公鸡:x母鸡:y小鸡:zendl;（编程，代码要记牢）第18页/共68页7-11问题（编程，代码要记牢）第19页/共68页设计蛮力算法找出四件物品的价格各是什么？#includevoid main()int a,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.0endl;return;第20页/共68页2023/3/2

13、1复习Page 212023/3/21Page 211.分治法的基本思想（分治法的基本思想（重要！重要！自底向上，理解，理解+应用）：应用）：将要求解的将要求解的原问题划分成原问题划分成k个较小规模的子问题个较小规模的子问题，对这，对这k个子问题分别个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，出其解为止，再将子问题的解合并为一个更大规模

14、的问题的解，自底自底向上向上逐步求出原问题的解。逐步求出原问题的解。步骤：（1）划分（2）求解子问题（3）合并第四章第四章 分治法分治法第21页/共68页2023/3/21复习Page 222023/3/21Page 221.分治法的基本思想（分治法的基本思想（自底向上，理解，理解+应用）：应用）：第四章第四章 分治法分治法子问题1的规模是n/2 子问题子问题1的解的解 子问题子问题2的解的解子问题2的规模是n/2 原问题的解原问题的解原问题的规模是n第22页/共68页2023/3/21复习Page 232023/3/21Page 232.熟记哪些问题使用了分治法进行解决：熟记哪些问题使用了分

15、治法进行解决：归并归并排序排序，快速排序快速排序，最大子段和最大子段和，棋盘覆盖，棋盘覆盖，循环赛日程安排，最近对问题，凸包问题；循环赛日程安排，最近对问题，凸包问题；并熟记这些问题的并熟记这些问题的时间复杂度时间复杂度：第四章第四章 分治法分治法第23页/共68页2023/3/21复习Page 242023/3/21Page 24其中：其中：归并排序归并排序：划分成等长子序列：划分成等长子序列分别对两子序列分别对两子序列归并排序归并排序将排完的有序子序列合并成一个有序将排完的有序子序列合并成一个有序序列，序列，O(nlog2n)；快速排序快速排序：用一个轴值划分成两个子序列：用一个轴值划分成

16、两个子序列分别分别对两个子序列递归地快速排序，对两个子序列递归地快速排序，O(nlog2n)；最大子段和最大子段和：划分成等长子序列：划分成等长子序列针对针对3种情况种情况分别处理求子序列最大子段和分别处理求子序列最大子段和合并合并3种情况下种情况下的最大子段和，的最大子段和，O(nlog2n)。第四章第四章 分治法分治法第24页/共68页2023/3/21复习Page 252023/3/21Page 253.归并排序、快速排序、最大子段和问题的设归并排序、快速排序、最大子段和问题的设计思想和伪代码；计思想和伪代码；（可能出简答题）（可能出简答题）4.用快速排序和归并排序算法对数字序列排序。用

17、快速排序和归并排序算法对数字序列排序。第四章第四章 分治法分治法第25页/共68页归并排序设计思想 二路归并排序的分治策略是：二路归并排序的分治策略是：（1）划分划分：将待排序序列：将待排序序列r1,r2,rn划分为两个长度相等的子序列划分为两个长度相等的子序列r1,rn/2和和rn/21,rn；（2）求解子问题求解子问题：分别对这两个子序列进行排序，得到两个有序子序列；：分别对这两个子序列进行排序，得到两个有序子序列；（3）合并合并：将这两个有序子序列合并成一个有序序列。：将这两个有序子序列合并成一个有序序列。二二路路归归并并排排序序在在合合并并过过程程中中需需要要与与原原始始记记录录序序列

18、列同同样样数数量量的的存存储储空空间间，因因此此其其空空间间复复杂杂性性为为O(n)。r1 rn/2 rn/21 rn 划分划分r1 rn/2 rn/21 rn 递归处理递归处理r1rn/2rn/21 r n 合并解合并解 第26页/共68页 r1 rn/2 rn/21 rn 划分划分r1 rn/2 rn/21 rn 递归处理递归处理r1rn/2rn/21 r n 合并解合并解 第27页/共68页快速排序设计思想以第一个记录作为轴值，对待排序序列进行划分的过程为：以第一个记录作为轴值，对待排序序列进行划分的过程为：（1）初初始始化化：取取第第一一个个记记录录作作为为基基准准，设设置置两两个个参

19、参数数i，j分分别别用用来来指指示示将将要要与与基基准准记记录录进进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；（2）右右侧侧扫扫描描过过程程：将将基基准准记记录录与与j指指向向的的记记录录进进行行比比较较，如如果果j指指向向记记录录的的关关键键码码大大，则则j前前移移一一个个记记录录位位置置。重重复复右右侧侧扫扫描描过过程程，直直到到右右侧侧的的记记录录小小（即即反反序序），若若ij，则则将将基基准记录与准记录与j指向的记录进行交换；指向的记录进行交换；（3）左左侧侧扫扫描描过过程程：将将基基准准记记录录与与i指指向向的

20、的记记录录进进行行比比较较，如如果果i指指向向记记录录的的关关键键码码小小，则则i后后移移一一个个记记录录位位置置。重重复复左左侧侧扫扫描描过过程程，直直到到左左侧侧的的记记录录大大（即即反反序序），若若ij，则则将将基基准记录与准记录与i指向的记录交换；指向的记录交换；（4）重复重复（2）（）（3）步，直到）步，直到i与与j指向同一位置，即基准记录最终的位置。指向同一位置，即基准记录最终的位置。第28页/共68页第29页/共68页最大子段和问题设计思想第30页/共68页复习1.减治法的基本思想（理解减治法的基本思想（理解+应用）：应用）：原问题的解原问题的解只存在于其中一个只存在于其中一个较

21、小规模的子问题较小规模的子问题中，所以，中，所以，只需求解其中一个较小规模的子问题只需求解其中一个较小规模的子问题就可以得到原问题的解。就可以得到原问题的解。2.熟记哪些问题使用了减治法进行解决：熟记哪些问题使用了减治法进行解决：折半折半查找查找，二叉树查找，二叉树查找，插入排序插入排序，堆排序，堆排序，选选择问题择问题，淘汰赛冠军问题，淘汰赛冠军问题，假币问题（假币问题（8枚枚硬币不知道假币轻重）硬币不知道假币轻重）；并熟记这些问题的；并熟记这些问题的时间复杂度：时间复杂度：第五章第五章 减治法减治法第31页/共68页2023/3/21复习Page 322023/3/21Page 32其中：

22、其中：折半查找：折半查找：在在有序表有序表中，中，取中间记录作为比较取中间记录作为比较对象，对象，若给定值与中间记录的关键码相等，则若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区于中间记录的关键码，则在中间记录的右半区继续查找，继续查找，O(log2n)。插入排序：插入排序：依次将待排序序列中的每一个记录依次将待排序序列中的每一个记录插入到一个已排好序的序列插入到一个已排好序的序列中，直到全部记录中，直到全部

23、记录都排好序，都排好序，O(n2)第五章第五章 减治法减治法第32页/共68页2023/3/21复习Page 332023/3/21Page 33其中：其中：选择问题：选择问题：考虑快速排序中的划分过程，选定考虑快速排序中的划分过程，选定一个轴值将序列一个轴值将序列rirj进行划分，使得比轴值小进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元素都的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是位于轴值的右侧，假定轴值的最终位置是s，则：，则：（1）若）若k=s，则，则rs就是第就是第k小元素；小元素；（2）若）若ks，则第，则第k小元素一定在轴值后半区中；

24、小元素一定在轴值后半区中；第五章第五章 减治法减治法第33页/共68页2023/3/21复习Page 342023/3/21Page 34其中：其中：假币问题（假币问题（8枚硬币不知道假币轻重）：枚硬币不知道假币轻重）：从八枚从八枚硬币中任取六枚硬币中任取六枚a，b，c，d，e，f，在天平两端，在天平两端各放三枚进行比较。假设各放三枚进行比较。假设a，b，c三枚放在天平三枚放在天平的一端，的一端，d，e，f三枚放在天平的另一端，可能三枚放在天平的另一端，可能出现三种比较结果出现三种比较结果（再根据三种比较结果进行（再根据三种比较结果进行分析）分析）abcdef abcdef abcdef第五章

25、第五章 减治法减治法第34页/共68页2023/3/21复习Page 352023/3/21Page 353.折半查找问题的设计思想和伪代码折半查找问题的设计思想和伪代码（可能出简答题）（可能出简答题）4.给一个数字序列，要求采用折半查找，找某个数，给一个数字序列，要求采用折半查找，找某个数，写出求解的过程。写出求解的过程。第五章第五章 减治法减治法第35页/共68页折半查找问题设计思想在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上

26、述过程，直到查找成功，或所查找的区域无记录，查找失败。r1 rmid-1 rmid rmid+1 rn （mid=(1+n)/2）如果如果krmid查找这里查找这里 k第36页/共68页2023/3/21第5章 减治法Page 37例：查找值为例：查找值为14的记录的过程：的记录的过程：0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52low=1high=13mid=7 high=6 mid=3 high=2 mid=1 31141814714low=2mid=2 14=14查找成功！查找成功！第37页/共

27、68页选择下列数字序列中的第3小的元素12,5,8,44,23,7,9,2第38页/共68页2023/3/21复习Page 392023/3/21Page 391.动态规划法的基本思想（动态规划法的基本思想（重要！重要！自底向上，理理解解+应用）：应用）：将待求解问题分解成若干个将待求解问题分解成若干个相互重叠相互重叠的子问的子问题，每个子问题对应决策过程的一个题，每个子问题对应决策过程的一个阶段阶段，将子问题的解求解一次并将子问题的解求解一次并填填入入表表中，当需要中，当需要再次求解此子问题时，可以通过查表获得该再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。子问题的解而不用

28、再次求解。第六章第六章 动态规划法动态规划法第39页/共68页2023/3/21复习Page 402023/3/21Page 402.动态规划法的求解过程：动态规划法的求解过程：分成相互重叠的子问题；分成相互重叠的子问题；求解子问题，填表；求解子问题，填表；自底向上计算出原问题的解。自底向上计算出原问题的解。第六章第六章 动态规划法动态规划法第40页/共68页2023/3/21复习Page 412023/3/21Page 413.熟记哪些问题使用了动态规划法进行解决：熟记哪些问题使用了动态规划法进行解决：TSP，多段图的最短路径问题多段图的最短路径问题，0/1背包背包，最，最长公共子序列问题，

29、最优二叉查找树，近似长公共子序列问题，最优二叉查找树，近似串匹配问题；并熟记这些问题的串匹配问题；并熟记这些问题的时间复杂度时间复杂度：多段图的最短路径问题：多段图的最短路径问题：O(n+m)0/1背包问题：背包问题：O(nC)第六章第六章 动态规划法动态规划法第41页/共68页2023/3/21第6章 动态规划法Page 422120345678949387684756866537 一个多段图一个多段图用动态规划法解决多段图的最短路径问题，写用动态规划法解决多段图的最短路径问题，写出求解过程出求解过程（可能出应用题）第六章第六章 动态规划法动态规划法第42页/共68页第43页/共68页202

30、3/3/21第6章 动态规划法Page 44 根据动态规划函数，用一个根据动态规划函数，用一个(n+1)(C+1)的二维表的二维表V，Vij表示把前表示把前i个物品装入容量为个物品装入容量为j的背包的背包中获得的最大价值。中获得的最大价值。实例：实例：有有5个物品，其重量分别是个物品，其重量分别是2,2,6,5,4，价值分别为，价值分别为6,3,5,4,6，背包的容量为，背包的容量为10。0123456789100w1=2v1=61w2=2v2=32w3=6v3=53w4=5v4=44w5=4v5=650000000000000000066666666606699999990669999111

31、11406699910111314066991212151515x5=1x4=0 x3=0 x2=1x1=1用动态规划法解决0/1背包问题，写出求解过程。（可能出应用题）物品容量第44页/共68页2023/3/21复习Page 452023/3/21Page 451.贪心法的基本思想（贪心法的基本思想（重要！重要！局部最优，理解，理解+应用）：应用）：贪心法在解决问题的策略上目光短浅，只根据贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会选择，不管将来有什么结果，这个选择都不会改变。

32、改变。第七章第七章 贪心法贪心法第45页/共68页2023/3/21复习Page 462023/3/21Page 462.熟记哪些问题使用了贪心法进行解决：熟记哪些问题使用了贪心法进行解决：TSP，图着色问题，图着色问题，最小生成树问题（Prim算法、Kruskal算法），背包问题，活动安排问题，活动安排问题，多机调度问题，哈弗曼编码；并熟记这些问多机调度问题，哈弗曼编码；并熟记这些问题的题的时间复杂度时间复杂度：第七章第七章 贪心法贪心法第46页/共68页2023/3/21复习Page 472023/3/21Page 47其中：其中：背包问题：每次从物品集合中背包问题：每次从物品集合中选择单

33、位重量价值选择单位重量价值最大的最大的物品，如果其重量小于背包容量，就可以物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，把它装入，并将背包容量减去该物品的重量，O(nlog2n)。注意：背包问题要求装满整个背包，注意：背包问题要求装满整个背包，最后一个物体若装不下一个整体，可以装其中的最后一个物体若装不下一个整体，可以装其中的一部分。一部分。第七章第七章 贪心法贪心法第47页/共68页2023/3/21复习Page 482023/3/21Page 483.背包问题的贪心算法设计思想和伪代码；背包问题的贪心算法设计思想和伪代码；给定给定n种物品和一个容量为种物品和一

34、个容量为C的背包，物品的背包，物品i的重量是的重量是wi，其价值为，其价值为vi，背包问题是如，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大何选择装入背包的物品，使得装入背包中物品的总价值最大?4.用贪心法解决背包问题，写出求解过程（第用贪心法解决背包问题，写出求解过程（第7章作业：先按章作业：先按单位价值重量比排序，再依次放置物品，最后求出总价值，单位价值重量比排序，再依次放置物品，最后求出总价值，写出）写出）（可能出应用题）（可能出应用题）第七章第七章 贪心法贪心法第48页/共68页背包问题（可能出简答题）设计思想有三种看似合理的贪心策略：（1）选择价值最大的物品，因为

35、这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。（2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。（3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。第49页/共68页2023/3/21第7章 贪心法Page 5060 120 50 背包背包 180 190 200(a)三个物品及背包三个物品及背包 (b)贪心策略贪心

36、策略1 (c)贪心策略贪心策略2 (d)贪心策略贪心策略3 50 30 10 20 20 3020/30 20 1010/20 30 10例如，有3个物品，其重量分别是20,30,10，价值分别为60,120,50，背包的容量为50，应用三种贪心策略装入背包的物品和获得的价值如图所示。第50页/共68页第51页/共68页2023/3/21复习Page 522023/3/21Page 521.回溯法的基本思想（回溯法的基本思想（深度优先搜索，理解，理解+应用）：应用）：从根结点出发，按照从根结点出发，按照深度优先策略深度优先策略遍历解空间树，在搜遍历解空间树，在搜索至树中任一结点时，先判断该结点

37、对应的部分解是否索至树中任一结点时，先判断该结点对应的部分解是否满足满足约束条件约束条件，或者是否超出，或者是否超出目标函数目标函数的界，也就是判的界，也就是判断该结点是否断该结点是否包含包含问题的（最优）解，如果肯定不包含，问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓则跳过对以该结点为根的子树的搜索，即所谓剪枝剪枝（PruningPruning）；否则，进入以该结点为根的子树，继续按）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。照深度优先策略搜索。第八章第八章 回溯法回溯法第52页/共68页2023/3/21复习Page 532023/3/21Pa

38、ge 532.熟记哪些问题使用了回溯法进行解决：熟记哪些问题使用了回溯法进行解决：图图m着色问题着色问题，哈密顿回路问题，哈密顿回路问题，八皇后问题八皇后问题（4皇后问题）皇后问题），批处理作业调度问题；，批处理作业调度问题；第八章第八章 回溯法回溯法第53页/共68页3.用回溯法解决m颜色图着色问题，画出搜索空间图；（可能出应用题）图的m着色问题描述为：给定无向连通图G=(V,E)和正整数m，判断能否用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。D=1ACBDE1234567891011121314A=1B=2C=3D=3E=1(a)一个无向图一个无向图 (b)回溯法搜索空间回溯

39、法搜索空间图图8.8 回溯法求解图着色问题示例回溯法求解图着色问题示例第54页/共68页4.画出用回溯法求解8皇后或4皇后问题的搜索过程（课本P161）（可能出应用题）八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在88的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在nn的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。回溯法求解回溯法求解4皇后问题的搜索过程皇后问题的搜索过程第55页/共68页2023/3/21复习Page 562023/3/21Page 561.分支限

40、界法的基本思想：分支限界法的基本思想：首先确定一个合理的限界函数，并根据限界函数首先确定一个合理的限界函数，并根据限界函数确定目标函数的界down,up；按照按照广度优先策略遍历问题的解空间树，在分支结点遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值；孩子结点的目标函数的可能取值；如果某孩子结点的目标函数可能取得的值超出目标函如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表（以下简称表PT）

41、中；）中；依次从表依次从表PT中选取使目标函数的值取得极值的结点中选取使目标函数的值取得极值的结点成为当前扩展结点；成为当前扩展结点；重复上述过程，直到找到最优解。重复上述过程，直到找到最优解。第九章第九章 分支限界法分支限界法第56页/共68页2023/3/21复习Page 572023/3/21Page 571.分支限界法的基本思想：分支限界法的基本思想：当搜索到一个叶子结点时，如果该结点的目标函数值当搜索到一个叶子结点时，如果该结点的目标函数值是表是表PT中的极值（对于最小化问题，是极小值；对于最中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问大

42、化问题，是极大值），则该叶子结点对应的解就是问题的最优解；题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），小化问题，调整上界；对于最大化问题，调整下界），依次考察表依次考察表PT中的结点，将超出目标函数界的结点丢弃，中的结点，将超出目标函数界的结点丢弃，然后从表然后从表PT中选取使目标函数取得极值的结点继续进行中选取使目标函数取得极值的结点继续进行扩展。扩展。第九章第九章 分支限界法分支限界法第57页/共68页2023/3/21复习Page 582023/3/21Page 582.熟记哪些问

43、题使用了分支限界法进行解决：熟记哪些问题使用了分支限界法进行解决：TSP，多段图的最短路径问，多段图的最短路径问题，题，任务分配问题任务分配问题，批处理作业调度问题，批处理作业调度问题，0/1背包背包；并熟记这些问题；并熟记这些问题的的时间复杂度；时间复杂度；3.用分支限界法解决任务分配问题，画出搜索空间。用分支限界法解决任务分配问题，画出搜索空间。（可能出应用题）（可能出应用题）4.用分支限界法解决用分支限界法解决0/1背包问题，画出搜索空间。背包问题，画出搜索空间。（可能出应用题）（可能出应用题）第九章第九章 分支限界法分支限界法第58页/共68页2023/3/21第9章 分支限界法 Pa

44、ge 59任务分配问题要求把n项任务分配给n个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。如图9.10所示是一个任务分配的成本矩阵。C9278643758187694任务任务1 任务任务2 任务任务3 任务任务4人员人员a人员人员b人员人员c人员人员d图图9.10 任务分配问题的成本矩阵任务分配问题的成本矩阵任务分配问题任务分配问题（可能出应用题）第59页/共68页2023/3/21第9章 分支限界法 Page 60求最优分配成本的上界和下界求最优分配成本的上界和下界考虑任意一个可行解，例如：考虑任意一个可行解，例如：矩阵中的矩阵中的对角线对角线是一个合法的选择，表示将

45、任务是一个合法的选择，表示将任务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

46、，人员，人员b执行所有任务的最小代价是执行所有任务的最小代价是3，人员，人员c执行所有任务执行所有任务的最小代价是的最小代价是1，人员，人员d执行所有任务的最小代价是执行所有任务的最小代价是4。因此，将。因此，将每一行的每一行的最小元素加起来最小元素加起来就得到解的下界，其成本是就得到解的下界，其成本是2+3+1+4=10。需要强调的是，这个解并不是一个合法的选择（需要强调的是，这个解并不是一个合法的选择（3和和1来自于矩阵的同一来自于矩阵的同一列），它仅仅给出了一个参考下界，这样，最优值一定是列），它仅仅给出了一个参考下界，这样，最优值一定是10,14之间之间的某个值。的某个值。第60页/共

47、68页2023/3/21第9章 分支限界法 Page 61图图9.11 分支限界法求解任务分配问题示例分支限界法求解任务分配问题示例(表示该结点被丢弃，结点上方的数组表示搜索顺序表示该结点被丢弃，结点上方的数组表示搜索顺序)4alb=16104startlb=101alb=172alb=103alb=151blb=133blb=104blb=141clb=144clb=174clb=203clb=134dlb=1323567891213111搜索空间第61页/共68页分支限界法求解0/1背包问题（可能出应用题）例例：0/1背背包包问问题题。假假设设有有4个个物物品品，其其重重量量分分别别为为(

48、4,7,5,3)，价价值值分分别别为为(40,42,25,12)，背背包包容容量量W=10。首首先先，将将给给定定物物品品按按单单位位重重量量价价值值从从大大到到小小排排序序，结结果果如下：如下：物品重量(w)价值(v)价值/重量(v/w)144010274263525543124第62页/共68页2023/3/21第9章 分支限界法 Page 63 应用贪心法求得近似解为应用贪心法求得近似解为(1,0,0,0)，获得的价值为，获得的价值为40，这可以作，这可以作为为0/1背包问题的下界。背包问题的下界。如何求得如何求得0/1背包问题的一个合理的上界呢？考虑最好情况，背包中背包问题的一个合理的

49、上界呢？考虑最好情况，背包中装入的全部是第装入的全部是第1个物品且可以将背包装满，则可以得到一个非常简单的个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：上界的计算方法：ub=W(v1/w1)=1010=100。于是，得到了目标函数的界于是，得到了目标函数的界40,100。假设背包中已装入物品的重量是假设背包中已装入物品的重量是w，获得的价值是，获得的价值是v，计算该结点的目标，计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值函数上界的一个简单方法是把已经装入背包中的物品取得的价值v，加上，加上背包剩余容量背包剩余容量W-w与剩下物品的最大单位重量价值与

50、剩下物品的最大单位重量价值的积，于是，得到限界函数为：的积，于是，得到限界函数为：第63页/共68页2023/3/21第9章 分支限界法 Page 64w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11无效解无效解w=4,v=40ub=70w=9,v=65ub=69w=4,v=40ub=64w=12无效解无效解w=9,v=65ub=65234567891分支限界法求解分支限界法求解0/1背包问题背包问题第64页/共68页1、掌握、掌握随机数生成算法随机数生成算法的原理的原理2、理解几大概率算法的思想、理解几大概率算法的思想第十二章第十二章 概率算法概率算法第6