Chinaunix首页 | 论坛 | 博客
  • 博客访问: 216319
  • 博文数量: 40
  • 博客积分: 2512
  • 博客等级: 大尉
  • 技术积分: 492
  • 用 户 组: 普通用户
  • 注册时间: 2010-08-24 10:23
文章存档

2014年(1)

2011年(4)

2010年(35)

分类: C/C++

2010-10-03 16:56:20

  
贪心算法
   贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部 最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

贪心算法的基本要素
  1贪心选择性质
  2最优子结构性质

贪心算法的基本思路
 1.建立数学模型来描述问题。  
 2.把求解的问题分成若干个子问题。
  3.对每一子问题求解,得到子问题的局部最优解。   
  4.把子问题的解局部最优解合成原来解问题的一个解。  

 实现该算法的过程:   
    从问题的某一初始解出发;
   while 能朝给定总目标前进一步 do
  求出可行解的一个解元素;
  由所有解元素组合成问题的一个可行解。

阅读(950) | 评论(0) | 转发(0) |
0

上一篇:八皇后

下一篇:背包问题

给主人留下些什么吧!~~