贪心算法的思想

greedy algorithm

概念

    是一种在每一步的选择上都采取在当前状态下最好或者最优的选择,从而导致结果是最好或者最优的算法。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。

基本思路

    1.创建数学模型来描述问题

    2.把求解的问题分成若干个子问题

    3.对每一个子问题求解,得到子问题的局部最优解

    4.把子问题的解局部最优解合成原来解问题的一个解

实现该算法的过程:

从问题的某一初始解出发

while 能朝给定总目标前进一步 :

    求出可行解的一个解元素

最后,由所有解元素组合成问题的一个可行解

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 分治算法 一、基本概念 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题...
    Java资讯库阅读 9,803评论 0 14
  • 分治算法 一、基本概念 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题...
    木叶秋声阅读 5,320评论 0 3
  • 本文整理自MIT算法导论公开课 1. 动态规划(Dynamic progamming) 动态规划是一种设计技巧,...
    one_zheng阅读 7,028评论 0 2
  • 五大常用算法之一:分治算法 基本概念: 把一个复杂的问题分成两个或更多的相同的或相似的子问题。再把子问题分成更小的...
    親愛的破小孩阅读 4,966评论 0 1
  • 6月23日和6月24日我参加了毕希名老师的《平衡观点说心理》培训活动,作为一个80岁的老头子,还能这么精神矍铄的给...
    不二小師弟阅读 700评论 1 0