数据结构与算法（Python语言版）课件 第14章 经典算法思想

第14章经典算法思想2025/6/111主要内容贪心算法

动态规划回溯算法2025/6/112经典算法思想是经过长时间的实践积累，总结出的算法思想。通过运用经典算法思想去分析问题，采用抽象的数学模型来描述问题，然后再使用算法进行求解，能够提高算法的效率和解决问题的质量。很多重要的具有特色算法都是在经典算法思想的基础上发展起来的，例如深度学习中的神经网络就是基于动态规划和优化的思想而发展起来的。总之，经典算法思想的重要性不仅在于它们被广泛应用于解决实际问题，更重要的是这些思想具有一定的普适性和通用性，是学习算法设计者必须要了解和掌握的。2025/6/113本章讲解贪心算法、动态规划和回溯算法这三种经典算法思想，这些算法思想和普通的具体的算法，比如起泡排序、二分法、遍历二叉树等算法不同，这些算法思想不会给出具体的代码流程，仅仅是提供一种算法的设计思想或解决问题的算法思路，这些算法思想应用在不同的具体问题里，所呈现的具体代码可能有很大的差异。。14.1贪心算法2025/6/114⒈贪心算法贪心算法（也称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。即不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。也就是说，不从整体最优上加以考虑，做出的只是在某种意义上的局部最优解。贪心算法的特点是一步一步地进行，以当前情况为基础，根据某个算法作最优选择，而不考虑各种可能的整体情况，通过每一步贪心选择，可得到局部最优解。由于贪心算法每一步是局部最优解，因此，如果使用贪心算法，必须要判断是否得到了最优解。14.1贪心算法2025/6/115⒈贪心算法例如，蒙眼爬山，蒙眼爬山者选择的策略是每次在周围选择一个最陡峭的方向爬行1小步（局部最优选择），但是蒙眼爬山者最后爬上去的山可能不是最高的山（爬山者周围是多峰山），假设蒙眼爬山者携带了一个自动通报海拔高度的小仪器，每次都报告海拔高度，当蒙眼爬山者发现周围没有陡峭的方向可走了，报告海拔高度恰好是想要的高度，那就找到了最优解，否则就知道自己旋入了局部最优解，无法继续下去了。贪心算法仅仅是一种思想而已，不像我们熟悉的选择法排序、二分法等算法有明确的算法步骤。2025/6/11614.1贪心算法2老鼠走迷宫贪心策略如下（这里称二维数组元素为路点，其值为路值）。①如果当前路点不是出口（最大值），即不是最优解，就降低优先度，将当前路值减1，进行②，如果当前路点是出口（最大值）进行④。②在当前路点的东西南北方向选出路值比当前路值大的最大新路点，如果找到进行③，否则回到①。③老鼠达到选出的新路点，进行①。④结束。如果路点的路值不会被减到等于墙的值(MIN_VALUE)，就一定能到达出口，否则某个路点或墙会被当成出口（因为MIN_VALUE-1等于MAX_VALUE，老鼠陷入局部最优解）。2025/6/11714.1贪心算法2老鼠走迷宫例子1ch14_1.pych14_1.py中的walk_maze()函数使用了贪心算法，main()函数使用walkMaze()演示了老鼠走迷宫、老鼠找到了出口.显示效果的提示：如果路值是-1表示老鼠走过此路点1次、-2老鼠走过此路点2次……依次类推14.2动态规划2025/6/118⒈动态规划

2025/6/11914.2动态规划2.0-1背包问题

0-1背包问题中的价值和重量仅仅是问题的一种描述形式，对于某些实际问题，重量可能是体积等其它单位，比如，集装箱装载货物的0-1背包问题，可能用体积代替重量。2025/6/111014.2动态规划2.0-1背包问题

0-1背包是背包问题中最简单的问题，动态规划的思想很适合用于解决0-1背包问题。2025/6/111114.2动态规划2.0-1背包问题0-1背包是背包问题中最简单的问题，动态规划的思想很适合用于解决0-1背包问题。

2025/6/111214.2动态规划2.0-1背包问题0-1背包是背包问题中最简单的问题，动态规划的思想很适合用于解决0-1背包问题。

2025/6/111314.2动态规划2.0-1背包问题例子2用动态规划求解0-1背包问题ch14_2.pych14_2.py中的DP()函数是背包算法，本例main()函数中使用DP()函数解决了下列两个背包问题:①背包最多可以载量8kg的物品，现在有重量依次为2,4,5,1（单位是kg）的4件物品，对应的价值依次为7,6,8,2（单位是￥）。怎样让背包中放置的物品价值最大？②学生选课时限制总学时为100个学时，现有5门选修课，这5门选修课的学时依次为20,20,60,40,50。对于5门选修课中的每门课程，学生修完该课程对应的全部学时才能得到这门课程的学分（要么不选，选了就必须完成课程规定的学时），这5门课程对应的学分依次为6,3,5,4,6。怎样选课可以让学分最多？14.3回溯算法2025/6/1114⒈回溯算法回溯算法又称为试探算法，是一种算法思想，其核心思想是不断地按某种条件求“中间解”来寻找“目标解”，但当进行到某一步时，也称为达到一个“搜索点”时，发现已经无法按既定条件继续求“中间解”时，即无法在此搜索点达到下一个搜索点，就要进行回退操作，这种算法无法进行下去就回退的思想为回溯算法，而满足回溯条件的某个状态的点称为“回溯点”。14.3回溯算法2025/6/1115⒈回溯算法

2025/6/111614.3回溯算法2.八皇后问题国际象棋棋盘是一个8×8的方格棋盘、由64个黑白交替的方格组成。国际象棋的棋子有兵、马、象、车、皇后、国王，其中皇后（Quenn）是最强大的棋子，她可以在水平、垂直和对角线上不限距离地移动。八皇后问题起源于国际象棋中的皇后棋子、由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题：要在8×8的国际象棋棋盘上放置8个皇后，使得她们互相之间无法攻击到对方（如图所示），即任意两个皇后都不能在同一行、同一列或同一对角线上。数学家高斯认为八皇后问题有76个解（方案），后来数学家用图论的方法给出了92个解。计算机出现以后，八皇后问题成为递归算法、回溯搜索算法的经典示例。2025/6/111714.3回溯算法2.八皇后问题例子