算法课PPT和贪心算法

简介：
贪心算法作为一种在计算机科学领域内应用广泛的核心策略，其主要特征是在解决问题的每一步骤中优先采用当前看来最优化的选择，进而实现整体方案的优化。这种算法的基本策略是通过在每一步选择看似最优的局部解决方案来逐步构建全局最优解的过程。特别适合于能够通过分阶段实施局部优化策略从而实现整体最佳结果的复杂问题。 贪心算法的应用示例： 调度问题：如活动选择问题，其目标是优化系统资源的使用效率。在活动选择问题中，我们需要从一组互不相交的活动中选出数量最多的活动集合。解决这一类问题通常采用先对活动按照结束时间排序，然后依次选取最早结束且与之前选中活动无冲突的活动，直到无法再添加为止。 图算法：例如最小生成树问题，可分别使用Prim算法或Kruskal算法求解。Dijkstra算法则是一种经典的贪心策略，用于计算图中任意两节点之间的最短路径长度。 其他启发式算法包括哈夫曼编码（用于数据压缩）、图着色问题（旨在用最少颜色给顶点着色以避免相邻颜色冲突）以及旅行商问题、集合覆盖问题等。此外，子集和问题则关注是否存在一个子集其元素之和等于目标值这一判定性问题。 本问题是贪心算法的一个典型应用场景。在进行找零操作时，算法通过贪心策略逐步选择最大面额的硬币，在确保总和不超过目标金额的前提下，实现找零过程中的最小化问题求解。具体而言，在处理67分的例子时，算法首先选取两个25分的硬币（总和为50分），随后选择一枚10分的硬币以达到60分，接着加入一枚5分的硬币使总额变为65分。最后，通过添加两枚1分的硬币，最终获得所需目标金额。经过上述步骤计算得出的结果是使用了五枚硬币即可完成找零任务。 在活动选择问题中，假设有一组任务，每项任务都有一个起始时间和截止时间；目标是从这些任务中选出尽可能多且互不冲突的任务。为了解决这一问题，可以采用贪心算法：首先将所有任务按照结束时间进行排序，接着从中选出最早完成的那个任务。之后，继续从剩下的任务中重复以上步骤，依次选出下一批最早完成的任务。直至所有可选的任务都被安排完毕。作为一种高效的解决策略，在问题能够分解为相互独立的决策，并且每个单个阶段的选择都能直接导出全局最优解时，贪心算法表现出显著的优势。这表明，当一个优化问题需要综合考虑所有可能组合以获得最终结果时，贪心算法往往难以达到预期效果。鉴于此，若要合理运用贪心算法，必须充分理解其特点和局限性。