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

东南隅

wantnon的blog

 
 
 

日志

 
 
 
 

动态规划,递归,穷举的关系  

2009-09-10 16:56:59|  分类: 算法/程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

如果有重叠子问题,则用动态规划。
如果无重叠子问题,则用递归。
穷举法效率太低几乎不用。
递归的构造方法:
其实递归就是"树型搜索+剪枝"(只不过搜索顺序只能是先序遍历),因
此对于一个问题,只要画出它的决策树,就可以很容易地构造出递归(
而无需构造递推方程)。
递归与穷举的区别:
穷举法是首先生成所有的叶子节点,然后逐个测试。而递归法则是"树
型搜索+剪枝",即无需生成所有叶子。因此可以这样认为:穷举法就是
"树型搜索"(没有剪树),而递归是"树型搜索+剪枝"。
动态规划与递归的区别:
前面说了,递归就是"树型搜索+剪枝"。而动态规划是"树型搜索+剪枝+
子问题(节点)合并"。
--
总结:
穷举     =树型搜索
递归     =树型搜索+剪枝
动态规划=树型搜索+剪枝+节点合并
因此算法效率:
动态规划>递归>穷举

  评论这张
 
阅读(205)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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