Feng.Li's Java See

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

无后效性:(DP)

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

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

转载(ACM国际大学生程序设计大赛)

     摘要: 一篇关于ACM的文章,有时间的朋友可以进来看看  阅读全文

posted @ 2008-01-15 15:15 小锋 阅读(846) | 评论 (1)编辑 收藏

tsp递归程序实现(Java)(zz)

     摘要: TSP程序的递归实现  阅读全文

posted @ 2008-01-08 16:15 小锋 阅读(509) | 评论 (0)编辑 收藏

TSP问题的解决算法

     摘要: 一些解决TSP问题的算法  阅读全文

posted @ 2007-12-28 17:13 小锋 阅读(6875) | 评论 (0)编辑 收藏

递归求解问题的通用方法

     摘要: 一篇很好的讲解递归的文章  阅读全文

posted @ 2007-12-26 20:04 小锋 阅读(661) | 评论 (0)编辑 收藏

DOM数据模型图


此模型为DOM模型图

posted @ 2007-12-26 15:32 小锋 阅读(519) | 评论 (0)编辑 收藏

数学归纳法的证明



证明方法:反证法
使用公理:任何一个非空正整数集合存在切仅存在一个最小元素
证明大致过程:
1、构造反命题:存在一个命题集合P,P(1)成立,P(n)成立时P(n+1)成立,但存在至少一个正整数m,使得P(m)不成立。
2、所有的m构成一个非空正整数集合A,根据公理,其中存在最小元素m1,那么m1>1一定成立(因为P(1)为真)
3、对于m1 - 1,存在如下矛盾:P(m1 - 1)应该为真,因为m1为集合A的最小元素,而如果P(m1 - 1)为真,那么根据题设P(m1 - 1 + 1) = P(m1)应该为真,与已知P(m1)为假矛盾

posted @ 2007-12-17 15:57 小锋 阅读(270) | 评论 (0)编辑 收藏

递归设计与数学归纳法

     摘要: 其实,递归和数学归纳法里面所隐含的思想其实是一样的  阅读全文

posted @ 2007-12-11 14:39 小锋 阅读(350) | 评论 (0)编辑 收藏

基数排序

     摘要: 基数排序  阅读全文

posted @ 2007-11-11 16:33 小锋 阅读(1282) | 评论 (0)编辑 收藏

汇编初学者入门

     摘要: 如何学习汇编  阅读全文

posted @ 2007-10-19 10:03 小锋 阅读(315) | 评论 (0)编辑 收藏

仅列出标题
共10页: 上一页 1 2 3 4 5 6 7 8 9 下一页 Last