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