袁方全套配套课件大学计算机7-1 算法设计方法.docx

《袁方全套配套课件大学计算机7-1 算法设计方法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计方法常用的算法设计方法除了教材中介绍的穷举法、递归法外，还有回溯法、分治法、贪心法和动态规划法。一、回溯法回溯法是一种试探性的算法设计方法。在日常生活中，我们往往需要开车去旅行，假设某次旅行的目的地是F市，但在行进途中的某个地点，突然出现了若干岔路口，对于从来没有去过F市的我们来说，面对如此多的路径选择一片茫然，怎么办呢？于是决定按照次序从第一条路径开始，每一条都尝试着去走一下，并且见到交警就前去咨询该条道路是否通往F市。这样在前进过程中就可能随时遇到两种情况：一种情况是选择正确，一种是选择

2、错误。在遇到交警之前可以一直沿着该条道路走下去，期间一旦发现选择错误，立即回头，返回到岔路口的位置，继续尝试下一条道路。如果其中某一条路最终到达了F市，那么该条路就是旅行问题的一个解。如果有充足的时间和精力，还可以继续尝试未曾走过的其他路径，因为它们也有可能到达F市，此时就可以获得问题的多个解。当然，从算法的角度来看，这个问题的描述过于简单，在实际应用中可能情况会变得非常复杂，出现更多的新问题，比如，所尝试的每条路径中间再次出现岔路口时，该如何做出进一步的选择呢？如果途中经过了许多岔路口以后才发现道

3、路错误，又该返回到哪里继续尝试呢？如果要寻找到所有通往F市的可能路径时，又该如何完成整个算法呢？等等。但是这个例子却反映了回溯法的基本设计思想，我们可以把它形象的称为“向前走，碰壁回头”，即回溯。与穷举法相比，回溯法的聪明之处就体现在能够及时地“回头”，因为已经知道继续走下去是不可能得到问题的解的，所以只能回退一步继续沿着其他的线路寻找答案。很明显，回溯法省去了大量无效的操作，因而更加适宜工作量大、候选解多的问题。二、分治法当面对一个复杂庞大的系统性问题时，通常难以直接求解，所以人们采取了“化整为零

4、”、“分而治之”的策略，将复杂问题分解为多个规模较小的同类问题，然后对所划分出来的小问题逐个加以分析与处理，最终使整个大的问题得以解决。各子问题之间以一定的结构形式相对独立，共同构成整个大的系统。当每个子系统都得到正确、高效的处理和运行时，总系统的问题也就迎刃而解了。一个庞大工程的设计与实施、一个复杂软件系统的开发等等都用到了这种思想。在利用分治法进行算法设计时，可以采取如下的步骤：（1）首先对将要求解的问题进行系统分析；（2）将问题分解为若干性质相同的子问题；（3）当某些子问题需要继续深入分解时，

5、递归使用上述方法，直到不能再分为止；（4）对所分解的每个子问题分别求解，所得结果称为求解子集；（5）归并求解子集，得到原问题的解。三、贪心法贪心法又称贪婪法，是指在对问题求解时，总是做出在当前阶段看来是最好的选择，求得当前步骤的最优解。我们把在某个阶段求得的最优解称为局部最优解。在算法设计中，贪心法与分治法一样，也需将求解过程划分为若干个步骤，在每个步骤确定恰当的子问题，并根据当前的情况应用贪心原则，对子问题进行处理，选取当前状态下最好的或最优的选择。每个子问题的局部最优解一旦确定之后，就不再改变，

6、直到算法结束，最后再将每个步骤的阶段性解堆叠在一起，形成原问题的最终解。贪心法并不考虑整体的情况，每个步骤的求解过程只考虑当前情况，因而最终面向整个大问题的解不一定是最优的，也就是说，局部最优解的简单堆叠并不一定形成整体最优解。但有时贪心法对一些特定的问题是非常有效的。我们来看一个找零钱的例子。假设有3种硬币，面值分别为1元、5角和1角，且数量不限。如果要找给顾客2元6角钱，请问怎么找才能使得找给顾客的硬币数量最少呢？这个问题可以分为几个步骤，每个步骤以找出一枚硬币来划分，则求解的步骤可以这样：（1

7、）找出一枚不超过2元6角的最大硬币，即一枚1元硬币；（2）找出一枚不超过1元6角的最大硬币，也为一枚1元硬币；（3）找出一枚不超过6角的最大硬币，即一枚5角硬币；（4）找出一枚不超过1角的最大硬币，即一枚1角硬币，至此全部找完。通过分析以上步骤发现，在每一步中都选取了一个当前情况下的最优选择，结果总共找出了4枚硬币，是一个整体最优解。所以这个找钱的过程就是贪心算法的一个典型应用。四、动态规划法动态规划是解决多阶段决策问题常用的最优化理论，用于解决多阶段过程的最优化问题。所谓多阶段决策问题，是指这样的

8、一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，最后形成一个决策序列。与贪心法不同的是，动态规划考虑到由阶段性最优解堆叠出的决策序列不一定是结果最优的，所以多阶段决策问题的最优化求解目标是获取导致问题最优值的最优决策序列，即得到最优解。为此，动态规划也需要将问题进行分解，和分治法不同的是，动态规划在分解子问题时并不是简单地按照“大事化小”的方式进行，而是沿着决策的阶段划分子问题，决策的阶段可以按照时间序列划分，也可以按照问题在求解和演化