贪心算法
2023-02-18 16:34:27 时间
贪心算法
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。
算法思路
贪心算法一般按如下步骤进行:
①建立数学模型来描述问题 。
②把求解的问题分成若干个子问题 。
③对每个子问题求解,得到子问题的局部最优解 。
④把子问题的解局部最优解合成原来解问题的一个解 。
使用条件
利用贪心法求解的问题应具备如下2个特征。
1、贪心选择性质
一个问题的整体最优解可通过一系列局部的最优解的选择达到,并且每次的选择可以依赖以前作出的选择,但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。
2、最优子结构性质
当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中,至于什么问题具有什么样的贪心选择性质是不确定的,需要具体问题具体分析 。
存在问题
贪心算法也存在如下问题:
1、不能保证解是最佳的。因为贪心算法总是从局部出发,并没从整体考虑;
2、贪心算法一般用来解决求最大或最小解;
3、贪心算法只能确定某些问题的可行性范围。
相关文章
- [MySQL] 解决Error 1698: Access denied for user 'root'@'localhost'
- [日常] 前端资源测试机上忽略版本号的的nginx配置
- [PHP] PHP PDO与mysql的连接单例防止超时情况处理
- [PHP] 使用Socket提供Http服务
- [PHP] 实现路由映射到指定控制器
- [PHP] 命令行执行整合pathinfo模拟定时任务
- [PHP] 自定义错误处理
- [Php] windows下使用composer出现SHA384 is not supported by your openssl extension
- [PHP] url的pathinfo模式加载不同控制器的实现
- [PHP] 自动加载的实现
- [PHP] 新版本PHP7.4与新版本MySQL8认证问题
- [PHP] PHP请求Socket接口测试
- [PHP] error_reporting(0)可以屏蔽Fatal error错误
- [PHP] 读取大文件并显示
- [PHP] PDO对象与mysql的连接超时
- [PHP] time_wait与长连接短连接
- [PHP] Ubuntu快速安装起PHP7.4
- [PHP] CentOS下搭建下PHP的运行环境
- [日常] 修复了grub引导问题
- [MySQL] docker下安装使用mysql配置主从复制