yangruiyi0505 2022-06-04 22:41 采纳率: 0%
浏览 1009
已结题

提出反例说明贪心算法不是2-近似算法

假设以下列贪心思想解决最小顶点覆盖问题：重复选择度数最高的顶点，并去掉所有邻接边。给出一个例子，说明该贪心算法不是2-近似算法。

img

  • 写回答

4条回答 默认 最新

  • BadCodeBuilder 2022-06-09 15:26
    关注

    北京某高校算法课作业？（不会写菜鸡的路过）

    评论

报告相同问题？

  • 五大常用算法之三：贪心算法 (2)，算法数据结构
    2022-04-07 16:27
    贪心算法并不保证在所有情况下都能得到全局最优解，因为它的决策过程是局部最优的，即每一步只考虑当前情况下的最佳选择，而不是考虑整个问题的整体最优解。 一、贪心算法的基本概念 贪心算法的核心思想是局部最优...
  • 五大常用算法之三：贪心算法 (3)，算法数据结构
    2022-04-07 16:27
    为了确定一个问题是适合贪心算法的，需要分析该问题的性质，可以通过实验数据来初步判断。例如，背包问题是一个经典的贪心算法应用题目，但并非所有背包问题都适合贪心算法，因为不同的贪心策略可能产生不同的结果。...
  • 五大常用算法之三：贪心算法 (1)，算法数据结构
    2022-04-07 16:25
    然而，贪心算法并非对所有问题都适用，因为它依赖于无后效性，即一个决策不会影响之前的决策状态，只与当前状态有关。 贪心算法的基本步骤包括： 1. 建立数学模型来定义问题。 2. 将问题分解为若干子问题。 3. 对每...
  • LeetCode-贪心算法-java
    2024-10-05 10:25
    贪心算法是计算机科学中解决问题的一种策略，它在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法并不保证会得到最优解，但是在某些问题中贪心策略...
  • 数据结构：贪心算法
    2024-09-22 18:53
    OutlierLi的博客 贪心法没有固定套路，在做题时，要有贪心的思想，如果不能用贪心做出了也正常，甚至用模拟做出来发现是贪心也正常；注意“两个维度权衡问题在分发糖果中，顺序遍历是一个维度，逆序遍历又是一个维度，然后最终结果取...
  • 《代码随想录》贪心算法详解与实战应用
    2024-09-17 20:26
    贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。然而，贪心算法并不保证会得到最优解，但是对于许多问题它会产生最优解。贪心算法的核心是...
  • 数据结构与算法（三）贪心算法（Java）
    2023-11-25 17:34
    不愿放下技术的小赵的博客 数据结构与算法（三）贪心算法（Java）
  • 数据结构与算法 - 贪心算法的适用场景：如何判断问题可贪心解决
    2025-10-11 17:35
    Jinkxs的博客 （活动选择、MST、霍夫曼等）能否提出一个清晰的贪心策略？（如“选最早结束”、“合并最小”）能否用交换论证证明该策略的安全性？能否构造一个小反例推翻贪心？问题是否具有拟阵结构？（遗传性 + 交换性）若前3问...
  • 贪心算法+0-1背包算法----2022年2月27日
    2022-02-27 19:19
    smile_keep looking的博客 贪心算法 就是不管其他因素，只找对应最大的。 符合贪心的例子: 通过分析，发现减少逆序就可以减少加工时间。 背包问题 对于背包问题不能这么思考 经过以上反例可以知道，不能一味找最大值。 数学的问题： 求， ...
  • 会议安排（贪心算法和动态规划） 贪心算法和动态规划.pdf
    2022-04-08 20:19
    会议安排问题可以使用贪心算法和动态规划两种方法来解决，两种方法都有其优缺，贪心算法简单高效，但可能不是最优解，而动态规划可以找到最优解，但时间复杂度较高。 代码实现： ```c //贪心算法 void Greedy...
  • 五大常用算法之三，算法数据结构
    2022-04-07 17:35
    ### 五大常用算法之三：贪心算法 #### 一、基本概念 贪心算法是一种在每一步选择中都采取当前看起来最好的选择的算法。这种算法并不试图从整体上优化解决方案，而是关注于每个步骤的局部最优解。贪心算法的设计...
  • 算法设计基于贪心策略的优化方法：概念解析、代码实现与典型应用场景研究
    2025-09-15 10:07
    进一步对比了贪心算法与动态规划、分治法的区别，强调贪心算法适用于具有贪心选择性质和最优子结构的问题。最后提供了判断贪心算法适用性的方法，包括贪心选择性质、最优子结构性质的证明以及反证法的应用。; 适合...
  • C++ 数据结构与算法（十）（贪心算法）
    2022-04-08 12:09
    chenyfan_的博客 贪心算法、 LeetCode、 代码随想录
  • 利用贪心算法解决数据结构与算法难题
    2025-06-24 03:23
    AI 算法学习的博客 贪心算法是算法设计中最“接地气”的策略之一，它广泛应用于任务调度、网络路由、资源分配等领域。本文将聚焦贪心算法的核心原理、设计步骤及实战应用，覆盖从概念理解到代码实现的全流程，帮助读者掌握“如何判断...
  • 算法与数据结构高手养成：朴素的贪心法(上)最优化策略
    2024-05-29 16:49
    Srlua小谢的博客 记得先点赞后阅读哦~ 所属专栏：算法与数据结构高手养成 欢迎访问我的主页：Srlua小谢 获取更多信息和资源。✨✨ ​​ ​​ 目录​​​​​​​ 朴素的贪心法(上)最优化策略 常见贪心法归类 何为“朴素”贪心 最...
  • 贪心算法和动态规划讲解
    2023-04-11 18:22
    贪心算法不是对所有问题都能得到整体最优解。但是如果经过大量证明成立之后，那么它就是一种高效的算法。如果用贪心来看，这个问题我们似乎只能根据单价来排序了A单价6，B单价5，C单价3，那么我们按排序结果选择，就...
  • 数据结构与算法 - 贪心vs动态规划：核心差异与场景选择
    2025-10-11 17:49
    Jinkxs的博客 **摘要：贪心算法与动态规划的本质区别与适用场景 贪心算法（局部最优）和动态规划（全局最优）是解决最优化问题的两大核心方法。贪心算法通过每一步的局部最优选择追求高效（如分数背包问题），但需满足贪心选择...
  • 算法设计基于贪心策略的最优化方法研究：从局部最优到全局最优的实现路径与应用局限分析
    2025-10-13 11:50
    阅读建议：学习时应结合文中Python代码实例动手实践，重点理解贪心策略的选择依据，并通过反例（如0-1背包问题）深入体会贪心法的局限性，建议在掌握基础后拓展学习贪心法与其它算法的融合应用。
  • 算法-贪心算法
    2021-11-11 11:41
    玉面小白龍(peng)的博客 1、贪心算法有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法。 2、举例： 2.1：假设我们有一个可以容纳 100kg 物品的背包，可以装各种物品...
  • 没有解决我的问题, 去提问

问题事件

  • 系统已结题 6月12日
  • 创建了问题 6月4日