Feng.Li's Java See

          抓緊時間,大步向前。
          隨筆 - 95, 文章 - 4, 評論 - 58, 引用 - 0
          數據加載中……

          無后效性:(DP)

             首先,請注意無后效性一般是針對問題的分析方式的,不是描述一個問題的。  
             
            我們說某問題不具有無后效性往往是指他的通常解法不具有這種性質,而如果我們把狀態定義成滿足無后效性原理  
            的方式,狀態太多,也沒有意義。  
             
            無后效性,就是說當前狀態是歷史的完全總結,和如何達到這一個狀態無關。  
             
            例如,對于這道單詞接龍的題目,每個單詞最多用兩次。  
            那么“當前接到的單詞”就不能概括整個“歷史”,因為同樣是接到的這個單詞,以前考慮過的單詞究竟是用過  
            沒有,用過多少次,將同樣影響今后的發展,而單一的狀態參量無法概括這些信息。如果把這些信息加到狀態  
            參量中,狀態太多(指數級),動態規劃也沒有多大意義。  
             
            如果影響歷史的信息并不多,我們可以通過升維的方法讓我們的狀態具有無后效性,  
            所以我們在思考狀態的時候,指導思想就是“簡潔而又完全的概括歷史”  

          posted on 2008-01-15 15:59 小鋒 閱讀(986) 評論(0)  編輯  收藏


          只有注冊用戶登錄后才能發表評論。


          網站導航:
           
          主站蜘蛛池模板: 清苑县| 贵阳市| 平利县| 陆川县| 木里| 错那县| 静宁县| 福贡县| 石城县| 辽中县| 新竹市| 壤塘县| 枣强县| 德阳市| 沁水县| 久治县| 武邑县| 罗定市| 广灵县| 利辛县| 芒康县| 北辰区| 禹州市| 尼玛县| 长阳| 赣榆县| 蚌埠市| 兖州市| 汤阴县| 大埔县| 威信县| 石泉县| 江口县| 盐亭县| 苍梧县| 延津县| 建昌县| 洛浦县| 兴业县| 无锡市| 车险|