当前位置: 首页 > news >正文

算法第四次作业

我的贪心策略:
将所有区间按照右端点b从小到大排序;选择第一个区间的右端点作为第一个点,遍历后续区间,如果当前区间包含已选择的点,跳过;否则,选择当前区间的右端点作为新点。
我对贪心算法的理解:
贪心算法的核心思想:局部最优选择:每一步都做出当前看起来最好的选择;无后效性:当前选择不影响后续问题的结构;贪心选择性质:局部最优能导致全局最优;最优子结构:问题的最优解包含子问题的最优解。
贪心算法的适用场景:
1.活动选择问题:选择不冲突的最大活动集合;
2.哈夫曼编码:数据压缩;最小生成树:
3.Prim和Kruskal算法;单源最短路径:
4.Dijkstra算法;硬币找零问题(特定面额)
贪心算法的局限性:
1.不是万能的:许多问题无法用贪心解决(如0-1背包问题);
2.需要证明:必须严格证明贪心选择性质和最优子结构;
3.局部最优不等于全局最优:对于不能证明贪心性质的问题,贪心可能得到次优解。
贪心算法的证明技巧:

  1. 交换论证:证明任何最优解可以通过交换调整为贪心解
  2. 归纳法:对问题规模进行归纳证明
  3. 领先:证明贪心选择始终保持领先于其他选择
  4. 剪切粘贴:证明将最优解的一部分替换为贪心选择不会变差
    选点问题的实际意义:资源分配:如会议安排、天线覆盖;传感器部署:用最少的传感器覆盖所有区域;任务调度:在时间轴上安排任务检查点。
    贪心算法在选点问题上的成功应用,展示了其"以简驭繁"的哲学:通过简单的排序和一次遍历,就能解决看似复杂的优化问题。这要求我们在设计算法时,不仅要关注"怎么做",更要思考"为什么这样做是最优的"。
http://www.zskr.cn/news/81803.html

相关文章:

  • 二手房翻新怎么选?这3类靠谱公司帮你避坑(附2025口碑榜单) - 品牌测评鉴赏家
  • re入门
  • 能工智人
  • 第三天—C++语法基础
  • 2025年12月超级充电桩,欧标充电桩,日标充电桩厂家推荐:行业权威盘点与品质红榜发布​ - 品牌鉴赏师
  • 2025新房整装服务哪家强?这份避坑指南+口碑榜单请收好 - 品牌测评鉴赏家
  • DSU on array - 反向操作区间合并
  • 关于Visual Studio 2022 Git无法使用的解决办法
  • Python 面向对象编程 (OOP) 核心:类、封装与继承
  • 12/10
  • 完整教程:分享一个基于服务端地图服务裁剪的方法
  • Nginx安全配置
  • 并发编程的三大基石:从底层逻辑聊透“同步、互斥与分工”
  • 在 .Net 8 WEBAPI 中实现实体框架的 Code First 办法
  • Coppersmith 学习笔记
  • 【SQL技术】不同数据库引擎 SQL 优化方案剖析 - 详解
  • Python list all files in dir recursivelly
  • python —— 树的遍历 —— 深度优先遍历(先序、中序、后序)
  • 恰好被k个区间覆盖的点的数量
  • windriver 第5章:USB 概述
  • Airflow - from airflow import DAG and from airflow.sdk import DAG, which one is better?
  • 货代邮件自动化处理系统设计文档
  • DSU on array
  • 吐血整理!新房全包装修,性价比之王大盘点 - 品牌测评鉴赏家
  • Resources资源同步加载、异步加载、卸载
  • windriver 第6章:使用DriverWizard
  • MATLAB R2025a免费下载安装教程与激活教程超详细图文步骤(附安装包)
  • 新房装修公司大揭秘!一文教你避坑选好公司 - 品牌测评鉴赏家
  • 2025整装公司排行榜发布:十大整装品牌引领行业新趋势 - 速递信息
  • 头歌MySQL——单表查询 - 详解