自学内容网 自学内容网
自学内容网 > 正文

贪心算法简记

🕗 发布于 2024-10-18 05:26 贪心算法  算法  

一、概念

贪心算法的理念是每步都选择局部最优解，最终得到的全局最优解。

贪心算法的特点是实现起来很容易，运行速度快，得到的结果又与正确结果相当接近。

贪心算法可以认为是一种近似算法

二、一般步骤

（1） 选出当前最优

（2） 重复直到覆盖所有情况

三、近似算法

指能为问题寻找近似解的算法，该类算法找到的近似解与最优解之间的差值需能证明不超过某个值

在获得精确解（最优解）需要的时间太长时，可使用近似算法。

判断近似算法优劣的标准如下：
（1） 速度有多快；
（2） 得到的近似解与最优解的接近程度。

近似算法被认为是面临NP完全问题时的最佳做法

四、NP完全问题

1、定义

P 问题是指可以在多项式时间内求解的问题。

NP 表示不确定性多项式时间（nondeterministic polynomial time），NP 问题是指在多项式时间内近似验证答案的问题。但很多此类问题需要指数时间才能求解。

NP完全或NP完备 （NP-Complete，缩写为NP-C或NPC），是NP中最难的决定性问题，目前为止并未发现任何能在多项式时间内解决NP完全问题的方法，甚至认为根本不可能找出快速解决方案

2、典型例子

旅行商问题和集合覆盖问题是NP完全问题的典型例子

旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个。

3、NP完全问题的判定

没办法判断问题是不是NP完全问题，但NP完全问题往往有以下特征
（1） 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
（2） 涉及“所有组合”的问题通常是NP完全问题。
（3） 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
（4） 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
（5）  如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
（6） 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。


原文地址：https://blog.csdn.net/well_fly/article/details/143029124

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

  • Libevent源码剖析之reactor

    是一种事件驱动的并发处理模式，常用于网络服务器和事件循环系统中。它主要的功能是通过或者处理I/O操作，避免阻塞，并且能够高效处理的事件。，以下摘自原文：Theis ansingleor, whichf

    阅读更多2024-10-20
  • IDEA如何配置自己的maven和maven设置阿里云仓库

    我们在使用IDEA开发Java应用时，一般是需要配置maven仓库的，那么我们应该如何配置呢？此外，默认的maven仓库下载速度很慢，我们一般可以配置阿里云或者华为云仓库，这个又应该怎么配置呢？然后，

    阅读更多2024-10-20
  • 84.【C语言】数据结构之顺序表的头部插入和删除

    注意头插时,元素会逐个向后移动,因此要先进行容量检查,再移动元素,最后不要忘记为有效元素个数size+1;头插N个元素的时间复杂度为O(N^2),运行效率不高,尽量避免头插,使用尾插(尾插N个元素的时

    阅读更多2024-10-20
  • 安装gpu版本的tensorflow-2.11

    参考：https://medium.com/nerd-for-tech/installing-tensorflow-with-gpu-acceleration-on-linux-f3f55dd15a9

    阅读更多2024-10-20
  • 英语

    给出英语面试的常见问题和答案当然可以。以下是一些英语面试中常见的提问及其参考答案：Can you introduce yourself? 答：Certainly. My name is [Your N

    阅读更多2024-10-20
  • LiveKit 在Kylin Server V10 下离线安装和配置

    首先简单介绍了 LiveKit,其次介绍了在 Kylin Server V10 下设置 Go 语言环境，编译 LiveKit 服务端以及 LiveKit 网页客户端的部署。

    阅读更多2024-10-20
  • 数据分箱：决策树得到特征的分箱区间后后怎么映射到原数据中？

    在这个例子中，我们将原数据中的每个值与分箱区间进行比较，确定其所属的分箱，并将分箱结果映射回对应的区间描述，存储在新的列中。如果一个值不匹配任何分箱，可以根据需要进行特殊处理。

    阅读更多2024-10-20
  • fanuc远程PNS启动

    PNS & RSR区别 前者是8bit=255 个程序 后者是bitN对应8个程序。

    阅读更多2024-10-20
  • HTTP 请求的请求体是什么

    请求体是 HTTP 请求的重要组成部分，用于传输实际的数据内容。根据不同的应用场景和数据格式，可以选择适当的内容类型来组织请求体中的数据。在 Web 开发中，正确处理请求体中的数据对于实现 RESTf

    阅读更多2024-10-20
  • Python PyQt5应用程序实现中英文切换

    在Python中使用PyQt5实现应用程序的中英文切换功能，可以通过国际化（i18n）和本地化（l10n）的技术来实现。以下是一个详细的教程，包括UI界面多语言切换和程序内部字符串多语言切换两部分。

    阅读更多2024-10-20
自学内容网
Copyright © 2015-2024