注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

碳基体

http://weibo.com/tanjiti

 
 
 
 
 

日志

 
 

常见算法  

2011-05-25 09:52:44|  分类: basic |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一、贪心算法

贪婪法是一种不追求最优解,只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不要回溯。

二、分治法

1)基本思想:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

2)适用条件:

① 该问题的规模缩小到一定的程度就可以容易地解决;

② 该问题可以分解为若干个规模较小的相同问题;

③ 分解出的子问题的解可以合并为原问题的解;

④ 分解出的各个子问题是相互独立的。 

divide-and-conquer(P)

  {

    if ( | P | <= n0) adhoc(P);   //解决小规模的问题

    divide P into smaller subinstances P1,P2,...,Pk;//分解问题

    for (i=1,i<=k,i++)

      yi=divide-and-conquer(Pi);  //递归的解各子问题

    return merge(y1,...,yk);  //将各子问题的解合并为原问题的解

  }

例子:

1. 归并排序

基本思想:将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合。 

2. 快速排序

基本思想:在快速排序中,记录的比较和交换是从两端向中间进行的,关键字较大的记录一次就能交换到后面单元,关键字较小的记录一次就能交换到前面单元

三、动态规划法

动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题.但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。

四、回溯法

回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。

五、分支限界法

(1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。 

(2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 

  评论这张
 
阅读(274)| 评论(1)
推荐

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017