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

第14章经典算法思想2024/11/91主要内容贪心算法

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

2024/11/9914.2动态规划2.0-1背包问题

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

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

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

2024/11/91314.2动态规划2.0-1背包问题例子2Example14_2.javaKnapsack.java例子2中的Knapsack类的DP()方法是背包算法.例子1的主类Example14_2使用Knapsack类的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。怎样选课可以让学分最多？2024/11/91414.2动态规划3.优化0-1背包问题例子3Example14_3.javaKnapsackOptimize.java对于许多实际问题，对应的DP-方程中有许多子问题可能是重叠的子问题，因此需要使用动态规划的思想进行优化处理，避免多次计算子问题的解。例子3中的KnapsackOptimize类中的DP()方法是优化的DP-方程。例子3的主类Example14_3解决规模较大0-1背包问题（物品的数量较大）。比较了例子2中的Knapsack类的DP()方法和例子3中KnapsackOptimize类中的DP()方法在解决同一背包问题的运行耗时.14.3回溯算法2024/11/915⒈回溯算法回溯算法又称为试探算法，是一种算法思想，其核心思想是不断地按某种条件求“中间解”来寻找“目标解”，但当进行到某一步时，也称为达到一个“搜索点”时，发现已经无法按既定条件继续求“中间解”时，即无法在此搜索点达到下一个搜索点，就要进行回退操作，这种算法无法进行下去就回退的思想为回溯算法，而满足回溯条件的某个状态的点称为“回溯点”。14.3回溯算法2024/11/916⒈回溯算法

14.3回溯算法2024/11/9172九宫格九宫格游戏是在一个3×3方格中放有1至8的数字、剩下一格为空白。先设定1至8的初始排列状态，然后开始不断的移动空白（空白周围的数字可移至空白，相当于移动空白）的位置，使得九宫格的3×3方格中的数字按1,2,3,4,5,6,7,8的顺序重新排好，九宫格的这个状态也称九宫格的一个解。14.3回溯算法2024/11/9182九宫格14.3回溯算法2024/11/9192九宫格九宫格里隐含着一个重要的规律，即“逆序”数目的奇偶性，叙述如下。把九宫格的1至3行的数字排列成一行得到一个排列，这个排列中相邻的两个数字称作一个“数字对”，九宫格中的一个“逆序”就是满足前者大于后者的一个数字对。●九宫格有解的充分必要条件是“逆序”数目必须是偶数多个（包括0个）。●九宫格在其状态变化过程中，“逆序”的数目的奇偶性保持不变。2024/11/92014.3回溯算法2.九宫格例子4Example14_4.javaGrid.java例子4中的NineGrid类中的backtrackingMove()方法使用回溯算法求九宫格的解。backtrackingMove()方法每移动一次空白格子（用数字0表示空白格子），都要保存当前九宫格的状态作为一个回