字体排版设计网站,重庆建设工程招标信息网,家装公司官网,营销型网站方案ppt模板文章目录 定义基本原理基本思路优缺点优点缺点 经典案例及解析找零问题问题描述贪心思路算法解析java代码示例 活动选择问题问题描述贪心思路算法解析java代码示例 车辆路径问题问题描述贪心思路算法分析java代码示例 定义
贪心算法是指在求解问题时#xff0c;总是做出在当前… 文章目录 定义基本原理基本思路优缺点优点缺点 经典案例及解析找零问题问题描述贪心思路算法解析java代码示例 活动选择问题问题描述贪心思路算法解析java代码示例 车辆路径问题问题描述贪心思路算法分析java代码示例 定义
贪心算法是指在求解问题时总是做出在当前来看是最好的选择不从整体最优上加以考虑只做出在某种意义上的局部最优解。在一些特定的问题中贪心算法可以通过逐步构建最优解来实现全局最优。
基本原理
贪心算法的核心在于它所具有的贪心选择性质。这意味着在对问题求解时每一步都可以做出一个在当前看来是最优的选择而不用考虑整体的最优解。 例如在找零问题中假设我们有无限量的面值为 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}; // 可用的硬币面额ListInteger result getMinimumCoins(n, coins);// 输出结果System.out.println(所需硬币数量: result.size());System.out.println(硬币面额: result);}public static ListInteger getMinimumCoins(int n, int[] coins) {ListInteger 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 ListActivity selectActivities(ListActivity activities) {// 1. 按照结束时间排序activities.sort(Comparator.comparingInt(a - a.end));ListActivity 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) {// 创建一些活动对象 (开始时间, 结束时间)ListActivity 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));// 调用选择活动的方法ListActivity 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);// 客户的坐标ListPoint customers Arrays.asList(new Point(2, 3),new Point(5, 2),new Point(8, 8),new Point(6, 7),new Point(1, 6));// 调用贪心算法获取访问路径ListPoint path greedyTSP(warehouse, customers);// 输出路径System.out.println(访问顺序);for (Point p : path) {System.out.println(客户位置: ( p.x , p.y ));}}// 贪心算法实现public static ListPoint greedyTSP(Point warehouse, ListPoint customers) {ListPoint path new ArrayList();SetPoint 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;}
}
以上是我对贪心算法学习过程中的一部分内容进行了总结我一直秉持着只有先了解学习过这些算法思想和原理之后才能对它的应用掌握得更深入后续还会继续学习总结一系列算法思想不定时进行总结。
