贪心算法(一)——概述

贪心法用于求解最优化问题,即求解某一问题的最优解。 既然能用贪心法求解的问题是一个最优化问题,那么我们首先来了解下最优化问题的几个基本概念。

最优化问题的几个基本概念

  • 目标函数 解决一个最优化问题,首先要将问题抽象成一个数学函数,这也就是一个数学建模的过程,这个能够描述问题的函数就称为『目标函数』,这个函数的最大/小值就是我们要求的最优值。
  • 约束条件 任何函数都有它的取值范围,所有取值范围的集合就称为『约束条件』。
  • 可行解 满足所有约束条件的解称为『可行解』。
  • 最优解 满足约束条件,并且使得目标函数最大/小的解称为『最优解』。

贪心法的求解思路

既然贪心法用于解决最优化问题,所以我们首先对问题进行数学建模,找出其中的:目标函数、约束条件。 最优化问题的结果需要用一个n元组来表示,如X=(x1,x2,x3,……,xn)。 贪心法的执行一共需要n步,每一步都会确定n元组中的一个元素,并保证每一步选取的值都是局部最优的。在经过n步之后,一共选取了n个值,每个值都是局部最优的,最终我们就可以认为这n个局部最优的值是整体最优的。

那么,在每一步中,究竟通过怎样的策略来选取一个当前局部最优解呢?这个选取策略就叫做『最优量度标准』(也叫做贪心准则)。 最优量度标准选择的好坏,直接影响最终的结果是不是整体最优。 而最优量度标准的选择往往是根据经验来确定的,也就是并不是所有的最优量度标准都能达到整体最优。所以你选取的那个最优量度标准能否导致整体最优,这是需要额外证明的。

贪心算法原型

SolutionType greedy(int[] a){

    // 一开始结果集为空
    SolutionType solution = {};
    // 进行n步选值
    for ( int i=0; i<n; i++ ) {
        // 选出当前局部最优解x
        x = select(a);
        // 判断x是否满足约束条件,若不满足则继续选
        while( !isFeasible(x) ){
            x = select(a);
        }
        // 将当前最优解添加至结果集中
        solution.add(x);
    }
}

何时使用贪心法

满足如下条件,可以使用贪心法:

  1. 要求解的问题是一个最优化问题;
  2. 这个问题的解可以用n元组表示;
  3. 该问题满足最优子结构特性;
  4. 可以找到最优量度标准,并可以证明该最优量度标准能导致一个整体最优解;

PS:并非对所有最优化问题都能找到最优量度标准,若找不到可以使用动态规划法。

贪心法的应用

  • 一般背包问题
  • 最佳合并模式
  • 最小代价生成树
  • 单元最短路径

总结

贪心法用于求解最优化问题。采用多步决策的方式求解,每一步根据最优量度标准求出结果集的一个分量,保证该分量为当前的局部最优解。那么当进行n步决策后,就求出结果集的所有分量。只要最优量度标准选的合理,最终的结果就是一个最优解。 当然,你选取的那个最优量度标准究竟能不能导致整体最优解,这是需要证明的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

Machine Learning -- GBDT(RF)

前言: 决策树这种算法有着很多良好的特性,比如说训练时间复杂度较低,预测的过程比较快速,模型容易展示(容易将得到的决策树做成图片展示出来)等。但是同时, 单决策...

3075
来自专栏深度学习之tensorflow实战篇

随机森林基本原理

基础内容: 这里只是准备简单谈谈基础的内容,主要参考一下别人的文章,对于随机森林与GBDT,有两个地方比较重要,首先是information gain,其次是决...

3299
来自专栏fangyangcoder

Andrew Ng机器学习课程笔记(三)之正则化

http://www.cnblogs.com/fydeblog/p/7365475.html

421
来自专栏深度学习之tensorflow实战篇

随机森林,random forest

模型组合(比如说有Boosting,Bagging等)与决策树相关的算法比较多,这些算法最终的结果是生成N(可能会有几百棵以上)棵树,这样可以大大的减少单决策树...

2745
来自专栏机器学习算法全栈工程师

朴素贝叶斯算法详解(1)

1. 引言   朴素贝叶斯算法(Naive Bayes)是机器学习中常见的基本算法之一,主要用来做分类任务的。它是基于贝叶斯定理与条件独立性假设的分类方法。...

3398
来自专栏奇点大数据

最新训练神经网络的五大算法

作者: Alberto Quesada 译者: KK4SBB 神经网络模型的每一类学习过程通常被归纳为一种训练算法。训练的算法有很多,它们的特点和性能各不相同...

3434
来自专栏决胜机器学习

深层神经网络参数调优(五) ——超参数调试、batch归一化、softmax回归

深层神经网络参数调优(五) ——超参数调试、batch归一化、softmax回归 (原创内容,转载请注明来源,谢谢) 一、超参数调试 1、超参数 超参数是不直...

3728
来自专栏机器学习算法原理与实践

逻辑回归原理小结

    逻辑回归是一个分类算法,它可以处理二元分类以及多元分类。虽然它名字里面有“回归”两个字,却不是一个回归算法。那为什么有“回归”这个误导性的词呢?个人认为...

622
来自专栏老秦求学

Deep Learning Tutorial 李宏毅(一)深度学习介绍

大纲 深度学习介绍 深度学习训练的技巧 神经网络的变体 展望 深度学习介绍 深度学习介绍 深度学习属于机器学习的一种。介绍深度学习之前,我们先大致了解一下机器学...

39210
来自专栏机器人网

【深度学习思维导图】必备的基本概念和架构

概念一节下分为激活函数:反向传播算法、学习率、梯度下降和损失(最小化)目标(最大化)函数。

802

扫描关注云+社区