無後效性

無後效性

無後效性是指一個問題可以用動態規劃求解的標誌之一。

基本介紹


無後效性的性質:某階段的狀態一旦確定,則此後過程的演變不再受此前各種狀態及決策的影響,簡單地說,就是“未來與過去無關”,當前的狀態時此前歷史的一個完整總結,此前的歷史只能通過當前的狀態去影響過程未來的演變。具體地說,如果一個問題被劃分各個階段之後,階段I中的狀態只能由階段I+1中的狀態通過狀態轉移方程得來,與其它狀態沒有關係,特別是與未發生的狀態沒有關係。從圖論的角度去考慮,如果把這個問題中的狀態定義成圖中的頂點,兩個狀態之間的轉移定義為邊,轉移過程中的權值增量定義為邊的權值,則構成一個有向無環加權圖,因此,這個圖可以進行“拓撲排序”,至少可以按它們拓撲排序的順序去劃分階段。