贪心算法（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背包问题）：
场景： 物品不可分割，每个物品只能选择“拿”或“不拿”。
方法： 通过回溯算法尝试所有可能的物品组合，计算总价值和总重量，选择符合条件的最大价值组合。
结果： 能够找到全局最优解，但计算量大。
总结：
-
贪心算法：
优势： 高效、实现简单，在某些问题上可以快速得到最优解。
劣势： 由于只考虑局部最优，可能无法得到全局最优解，适用范围有限。
-
回溯算法：
优势： 能够找到所有可能的解，确保全局最优。
劣势： 计算复杂度高，可能导致性能问题。
总体来说，贪心算法和回溯算法在思想和应用上有显著区别：
贪心算法适用于希望快速找到一个可能是最优的解，但不要求遍历所有可能性的情况。
回溯算法则用于需要穷举所有可能的方案，以确保找到所有解或最优解的情况。
