CH10常用算法.pptVIP

贪心算法 动态规划 回溯算法 10.1 贪心算法 贪心法（Greedy method）是一种最直接的设计技术，它能应用于多种问题。这问题的一般特征是有n个输入以及一组约束条件，满足约束条件的任一输入的子集，称为可行集。要在其中找到一个解，使给定的目标函数达到极大或者极小，满足这样的解，称为最优解。 用贪心法设计算法的特点是一步一步地进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解，每一步只考虑一个输入，它的选取满足局部优化条件；若下一个输入与部分最优解连在一起不再是可行解时，就不把该输入添加到部分解中。 10.1 贪心算法 贪心法在日常生活中经常用到，比如找零钱就是一个典型的例子。假如售货员需要找给小孩67美分的零钱。现在，售货员手中只有25美分、10美分、5美分和1美分的硬币。售货员想尽快将钱找给小孩。她的做法是：先找不大于67美分的最大硬币25美分硬币，再找不大于67－25＝42美分的最大硬币25美分硬币，再找不大于42－25＝17美分的最大硬币10美分硬币，再找不大于17－10＝7美分的最大硬币5美分硬币，最后售货员再找出两个1美分的硬币。至此，售货员共找给小孩6枚硬币。售货员的原则是拿尽可能少的硬币个数找给小孩。从另一个角度看，如果售货员将捡出的硬币逐一放在手中，最后一起交给小孩，那么售货员想使自己手中的钱数增加的尽量快些，所以每一次都尽可能地捡面额大的硬币。这就是贪心法思想。当然贪心法不是最优方案，是相对比较好的解，是最优解的很好的近似。如售货员手中只有11美分、5美分、1美分，若要找15美分，采用贪心法的结果是11+1+1+1+1，5枚硬币，而实际上最好方案是5+5+5，3枚硬币。 10.1.1背包问题 10.1.1背包问题 10.1.1背包问题 10.1.1背包问题 10.1.1背包问题 10.1.2多处理机调度 10.1.2多处理机调度 10.1.2多处理机调度 10.1.2多处理机调度 10.1.2多处理机调度 10.1.2多处理机调度 10.1.3可靠性优化 10.1.3可靠性优化 10.1.3可靠性优化 10.1.3可靠性优化 10.1.3可靠性优化 10.1.4 小结 10.2 动态规划 有许多问题，用穷举法才能得到最佳解。若输入量n稍大一些，计算量太大，特别对渐近时间复杂性为输入量的指数函数的问题，计算机无法完成。采用动态规划（Dynamic programming）能得到比穷举法更有效的算法。动态规划的指导思想是，在每种情况下，列出各种可能的局部解，从局部解中挑出那些有可能产生最佳的结果而扬弃其余，从而大大缩减了计算量。 动态规划遵循的“最佳原理”简而言之，“一个最优策略的子策略总是最优的”。动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种方法，大约产生于50年代，由美国数学家贝尔曼（R?Bellman）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相联系单阶段问题，然后逐个加以解决。动态规划开始只是应用于多阶段决策性问题，后来渐渐被发展为解决离散最优化问题的有效手段，进一步应用于一些连续性问题上。然而，动态规划更像是一种思想而非算法，它没有固定的数学模型，没有固定的实现方法，其正确性也缺乏严格的理论证明。因此，一直以来动态规划的数学理论模型是一个研究的热点。 10.2.1单源最短路问题 10.2.1单源最短路问题 10.2.1单源最短路问题 10.2.1单源最短路问题 10.2.1单源最短路问题 10.2.1单源最短路问题 10.2.1单源最短路问题 10.2.1单源最短路问题 10.2.1单源最短路问题 10.2.1单源最短路问题 10.2.1单源最短路问题 10.2.1单源最短路问题 10.2.2 资源分配问题 10.2.2 资源分配问题 10.2.2 资源分配问题 10.2.2 资源分配问题 10.2.2 资源分配问题 10.2.2 资源分配问题 10.2.2 资源分配问题 10.3 回溯算法 回溯法（Backtracking）属于穷举方法，是一种逐步试探以求出问题解的方法。它的主要思想是：假设能够用n元组（x1,x2,……，xn)表示一个给定问题的解。Xi取值于集合Si，n元组的子组（x1,x2,……，xi) （in）称为部分解应满足一定的约束条件。如果已有满足约束条件的部分解，则添加xi+1属于Si+1到子组中形成新的子组并检查是否满足约束条件，若满足则继续添加，依次类推。如果所有的都不能得到部分解，那么去掉回溯到中，然后添加那些未考察过的，判断其是否满足约束条件。如此反复进行下去，直到得到问题的解或者证明无解为止