Feng.Li's Java See

抓紧时间,大步向前。
随笔 - 95, 文章 - 4, 评论 - 58, 引用 - 0
数据加载中……

无后效性:(DP)

   首先,请注意无后效性一般是针对问题的分析方式的,不是描述一个问题的。  
   
  我们说某问题不具有无后效性往往是指他的通常解法不具有这种性质,而如果我们把状态定义成满足无后效性原理  
  的方式,状态太多,也没有意义。  
   
  无后效性,就是说当前状态是历史的完全总结,和如何达到这一个状态无关。  
   
  例如,对于这道单词接龙的题目,每个单词最多用两次。  
  那么“当前接到的单词”就不能概括整个“历史”,因为同样是接到的这个单词,以前考虑过的单词究竟是用过  
  没有,用过多少次,将同样影响今后的发展,而单一的状态参量无法概括这些信息。如果把这些信息加到状态  
  参量中,状态太多(指数级),动态规划也没有多大意义。  
   
  如果影响历史的信息并不多,我们可以通过升维的方法让我们的状态具有无后效性,  
  所以我们在思考状态的时候,指导思想就是“简洁而又完全的概括历史”  

posted on 2008-01-15 15:59 小锋 阅读(975) 评论(0)  编辑  收藏


只有注册用户登录后才能发表评论。


网站导航: