算法之旅(十二) 核心算法思想之一贪心算法

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望能够得到全局最优解的算法。它不从整体最优上考虑，只是在每个子步骤上作出局部最优的选择。

贪心算法的思想：

局部最优选择： 在问题求解的每个阶段，都作出当前看来最好的选择，不考虑未来可能产生的影响。
全局最优目标： 希望通过一系列的局部最优选择，最终得到问题的全局最优解。
一次决策，不可回退： 一旦作出选择，便不再更改，不会回溯或调整之前的决策。

贪心算法的应用：

其实有很多，我举例比较日常的两个

一、最短路径

Dijkstra算法

应用背景：

在带非负权值的有向图中，寻找从源点到其他所有节点的最短路径。Dijkstra算法通过贪心策略，每次选择距离最近的未访问节点，更新其邻居的最短路径。

贪心策略：

每次选择当前已知的最近节点，更新其邻接节点的最短路径。
不回溯，因为一旦确定了节点的最短路径，就不会再更新。

实际应用：

导航系统：如GPS导航，计算从当前位置到目的地的最短路线。
网络路由：在数据通信中，寻找数据包传输的最短路径。

二、工序调度问题

应用背景：

有多个需要在同一台机器上处理的任务，每个任务有不同的处理时间和截止时间，目标是最小化延迟任务的数量或总延迟时间。

贪心策略：

按照截止时间排序，优先处理截止时间早的任务。
或者按照处理时间排序，优先处理处理时间短的任务（SJF调度）。

实际应用：

生产线调度：提高生产效率，减少延迟。
CPU调度：优化任务执行顺序，提升系统性能。

简单来说-。- 短进程优先

贪心算法的特性：

贪心选择性质（Greedy Choice Property）： 可以通过局部最优选择构建全局最优解。
最优子结构性质（Optimal Substructure）： 问题的最优解包含其子问题的最优解。

贪心算法的优点：

高效性： 通常具有较低的时间复杂度，计算速度快。
实现简单： 算法逻辑直观明了，编程实现较为容易。

贪心算法的缺点：

局限性： 并非所有问题都适合贪心算法，只有满足特定性质的问题才能保证最优解。
可能非最优： 由于只关注局部最优，可能导致无法获得全局最优解。

贪心算法与回溯算法的区别：

1. 思想不同：

贪心算法：
- 局部视角： 每一步都作出当前最优选择，不考虑整体情况和未来可能的后果。
- 不可回退： 一旦作出选择，不会回溯调整之前的决策。
回溯算法：
- 全局视角： 通过遍历所有可能的解空间，找到所有满足条件的解或最优解。
- 回退机制： 当某条路径无法达成目标时，回溯到上一步，尝试其他可能性。

2. 解决问题方式不同：

贪心算法： 一次性决策，逐步构建解答，不考虑之前或之后的选择对当前的影响。
回溯算法： 试探性地搜索，通过递归和回溯机制，系统地尝试所有可能的方案。

3. 时间复杂度不同：

贪心算法： 通常为多项式时间复杂度，如O(n log n)、O(n)，效率高。
回溯算法： 时间复杂度通常为指数级别，随着问题规模增大，计算量迅速增长。

4. 适用问题类型不同：

贪心算法： 适用于满足贪心选择性质和最优子结构性质的问题。
回溯算法： 适用于需要搜索全部解空间的问题，如组合、排列、路径搜索等。

5. 解的最优性保证不同：

贪心算法： 不能保证对所有问题都得到全局最优解。
回溯算法： 通过全面搜索，可以找到全局最优解或所有可行解。

举例对比：

背包问题：

贪心算法（部分背包问题）：
- 场景： 物品可以分割成任意大小。
- 方法： 按照物品的单位价值从高到低排序，依次装入背包，直到容量用完。
- 结果： 能够获得最大总价值，贪心算法在此适用且最优。
回溯算法（0-1背包问题）：
- 场景： 物品不可分割，每个物品只能选择“拿”或“不拿”。
- 方法： 通过回溯算法尝试所有可能的物品组合，计算总价值和总重量，选择符合条件的最大价值组合。
- 结果： 能够找到全局最优解，但计算量大。

总结：

贪心算法：
- 优势： 高效、实现简单，在某些问题上可以快速得到最优解。
- 劣势： 由于只考虑局部最优，可能无法得到全局最优解，适用范围有限。
回溯算法：
- 优势： 能够找到所有可能的解，确保全局最优。
- 劣势： 计算复杂度高，可能导致性能问题。

总体来说，贪心算法和回溯算法在思想和应用上有显著区别：

贪心算法适用于希望快速找到一个可能是最优的解，但不要求遍历所有可能性的情况。
回溯算法则用于需要穷举所有可能的方案，以确保找到所有解或最优解的情况。