算法（三）——贪心算法

定义

贪心算法是指在求解问题时，总是做出在当前来看是最好的选择，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。在一些特定的问题中，贪心算法可以通过逐步构建最优解来实现全局最优。

基本原理

贪心算法的核心在于它所具有的贪心选择性质。这意味着在对问题求解时，每一步都可以做出一个在当前看来是最优的选择，而不用考虑整体的最优解。
例如，在找零问题中，假设我们有无限量的面值为 25 美分、10 美分、5 美分和 1 美分的硬币，要找给顾客 63 美分的零钱。贪心算法的做法是，每次都选择尽可能大面值的硬币，先选 2 个 25 美分，剩下 13 美分，再选 1 个 10 美分，剩下 3 美分，接着选 3 个 1 美分。这种每一步都选择当前最优（面值最大的硬币）的方式就是贪心选择。

基本思路

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。

但是存在问题：
不能保证求得的最后解是最佳的；
不能用来求最大或最小解问题；
只能求满足某些约束条件的可行解的范围。

优缺点

优点

简单易懂：
贪心算法通常非常直观和易于理解，解决问题的思路简单直接。

局部最优解：
贪心算法通过每一步选择当前最优解（局部最优解），尝试构建全局最优解。

高效：
贪心算法的时间复杂度通常较低，适合解决某些大规模问题。常见的时间复杂度为 O(nlogn) 或 O(n)。

应用广泛：
贪心算法在诸如图论（如最小生成树、最短路径）、任务调度、资源分配等多个领域有广泛的应用。

缺点

局限性：
贪心算法并不总能找到问题的最优解。它依赖于每一步的局部最优选择，可能会错过全局最优解。例如，背包问题的贪心算法不能保证找到最优解。

问题依赖性：
贪心算法只有在某些特定类型的问题（满足贪心选择性质和最优子结构性质）中才能有效工作。对于不满足这些性质的问题，贪心算法无法保证最优解。

分析复杂：
对于某些问题，证明贪心算法的正确性和最优性可能较为复杂，需要仔细的数学推导和验证。

无回溯：
贪心算法一旦做出选择，就不会回溯或改变决定。因此，一旦做出错误的选择，就无法修正。

经典案例及解析

找零问题

问题描述

给定一些面额不同的硬币，如1元、5元、10元，要找零n元，找零的硬币数量要尽可能少。

贪心思路

在每一步选择中，选择面额最大的硬币，直到找零的总金额达到n

算法解析

先初始化一个空列表，用于存储找零的硬币。从面额最大的硬币开始，将尽可能多的这个硬币加入列表，直到总金额超过n。如果总金额等于n，算法结束。否则，将面额减小到次大的硬币，重复上述步骤。

java代码示例

import java.util.ArrayList;
import java.util.List;public class CoinChangeGreedy {public static void main(String[] args) {int n = 28; // 需要找零的金额int[] coins = {10, 5, 1}; // 可用的硬币面额List<Integer> result = getMinimumCoins(n, coins);// 输出结果System.out.println("所需硬币数量: " + result.size());System.out.println("硬币面额: " + result);}public static List<Integer> getMinimumCoins(int n, int[] coins) {List<Integer> result = new ArrayList<>();// 遍历硬币面额，从大到小for (int coin : coins) {// 尽可能多地使用当前面额的硬币while (n >= coin) {result.add(coin);n -= coin;}}return result;}
}

本贪心算法适用于硬币面额满足贪心选择性质的情况。在本例中，10 和 5 的面额对于任何情况都能进行贪心选择，因此算法是有效的。如果硬币面额不同，比如 {1, 3, 4}，则贪心策略可能无法获得最优解。

活动选择问题

问题描述

给定一系列活动，每个活动都有开始时间和结束时间，目标是选择尽可能多的互不相交的活动。

贪心思路

在每一步选择中，选择结束时间最早的活动，可以腾出更多时间给其他活动。

算法解析

1.排序：首先根据活动的结束时间对活动进行排序。
2.选择活动：从第一个活动开始，选择结束时间最早的活动，并继续选择所有不与已选活动重叠的活动。

java代码示例

import java.util.*;class Activity {int start;  // 活动的开始时间int end;    // 活动的结束时间Activity(int start, int end) {this.start = start;this.end = end;}
}public class ActivitySelection {// 方法：选择尽可能多的互不相交的活动public static List<Activity> selectActivities(List<Activity> activities) {// 1. 按照结束时间排序activities.sort(Comparator.comparingInt(a -> a.end));List<Activity> selectedActivities = new ArrayList<>();// 2. 选择活动int lastEndTime = -1;  // 上一个被选择的活动的结束时间，初始为负值for (Activity activity : activities) {// 如果当前活动的开始时间大于或等于上一个选择的活动的结束时间if (activity.start >= lastEndTime) {// 选择当前活动selectedActivities.add(activity);lastEndTime = activity.end;  // 更新结束时间}}return selectedActivities;}public static void main(String[] args) {// 创建一些活动对象 (开始时间, 结束时间)List<Activity> activities = new ArrayList<>();activities.add(new Activity(1, 4));activities.add(new Activity(3, 5));activities.add(new Activity(0, 6));activities.add(new Activity(5, 7));activities.add(new Activity(8, 9));activities.add(new Activity(5, 9));// 调用选择活动的方法List<Activity> selectedActivities = selectActivities(activities);// 打印选择的活动System.out.println("选中的活动如下：");for (Activity activity : selectedActivities) {System.out.println("活动开始时间: " + activity.start + ", 活动结束时间: " + activity.end);}}
}

车辆路径问题

问题描述

有一组客户点和一个中心仓库，目标是找到一条路径，使得所有客户都被访问，并且路径总长度最短。

贪心思路

从仓库出发，选择离当前位置最近的客户点，重复此过程直到所有客户都被访问。

算法分析

从仓库出发，选择距离仓库最近的客户。访问该客户，然后选择距离当前客户最近的未被访问的客户。重复这个过程，直到所有客户都被访问完。

java代码示例

import java.util.*;
public class GreedyTSP {// 定义一个二维数组表示客户和仓库的坐标static class Point {int x, y;Point(int x, int y) {this.x = x;this.y = y;}// 计算两点之间的欧几里得距离double distanceTo(Point other) {return Math.sqrt(Math.pow(this.x - other.x, 2) + Math.pow(this.y - other.y, 2));}}public static void main(String[] args) {// 仓库的坐标Point warehouse = new Point(0, 0);// 客户的坐标List<Point> customers = Arrays.asList(new Point(2, 3),new Point(5, 2),new Point(8, 8),new Point(6, 7),new Point(1, 6));// 调用贪心算法获取访问路径List<Point> path = greedyTSP(warehouse, customers);// 输出路径System.out.println("访问顺序：");for (Point p : path) {System.out.println("客户位置: (" + p.x + ", " + p.y + ")");}}// 贪心算法实现public static List<Point> greedyTSP(Point warehouse, List<Point> customers) {List<Point> path = new ArrayList<>();Set<Point> visited = new HashSet<>();Point current = warehouse;// 将仓库添加到路径path.add(current);// 循环直到所有客户都被访问while (visited.size() < customers.size()) {Point nearestCustomer = null;double minDistance = Double.MAX_VALUE;// 寻找最近的未访问客户for (Point customer : customers) {if (!visited.contains(customer)) {double dist = current.distanceTo(customer);if (dist < minDistance) {minDistance = dist;nearestCustomer = customer;}}}// 将找到的最近客户添加到路径，并标记为已访问if (nearestCustomer != null) {path.add(nearestCustomer);visited.add(nearestCustomer);current = nearestCustomer; // 更新当前客户为最近客户}}return path;}
}

以上是我对贪心算法学习过程中的一部分内容进行了总结，我一直秉持着只有先了解学习过这些算法思想和原理之后才能对它的应用掌握得更深入，后续还会继续学习总结一系列算法思想，不定时进行总结。