無後效性

所謂無後效性原則，指的是這樣一種性質：某階段的狀態一旦確定，則此後過程的演變不再受此前各狀態及決策的影響。也就是説，“未來與過去無關”，當前的狀態是此前歷史的一個完整總結，此前的歷史只能通過當前的狀態去影響過程未來的演變。具體地説，如果一個問題被劃分各個階段之後，階段k中的狀態只能通過階段k+1中的狀態通過狀態轉移方程得來，與其他狀態沒有關係，特別是與未發生的狀態沒有關係，這就是無後效性。 ^[2] 

對於不能劃分階段的問題，不能用動態規劃來解；對於能劃分階段，但不符合最優化原理，也不能用動態規劃來解；既能劃分階段，又符合最優化原理，但不具備無後效性原則的，還是不能用動態規劃來解；誤用動態規劃程序設計方法求解會導致錯誤的結果。 ^[3] 

例1 貨郎擔問題和旅行路線問題。貨郎擔問題是對平面給定的n個點確定一條連接各點的、閉合的最短遊歷路線問題。圖1(a)給出了7個點問題的解。旅行路線問題是貨郎擔問題的簡化，這種旅行路線先從最左邊開始，嚴格地由左至右到最右邊的點，然後再嚴格地由右至左到出發點，求路程最短的路徑長度。圖1(b)給出了7個點問題的解。 ^[2] 

這兩個問題看起來非常相似，但本質上是完全不同的。為了方便討論，可以將每個頂點標記號碼。由於必然經過最右邊的頂點7，所以一條路(

到

)可以看成是兩條路線(

到

)與(

到

)的結合。因此，這個題目的狀態可以用兩條道路結合的形式表示。可以把這些狀態中，兩條路中起始頂點相同的狀態歸於一個階段，設為階段[

，

]。

那麼，對於旅行路線問題來説，階段[

，

]如果可以通過階段

推出，則必須滿足的條件就是：

<

或

<

。例如，階段[3，4]中的道路可以通過階段[3，5]中的道路加一條邊4—5得出，而階段[3，5]的狀態卻無法由階段[3，4]中的狀態得出，因為在旅行路線問題的要求中必須嚴格地由左到右來旅行。所以如果已經知道了階段[3，4]中的狀態，那麼階段[3，5]中的狀態必然已知，因此，問題滿足無後效性原則，可以考慮用動態規劃方法求解。

而對於貨郎擔問題，階段與階段之間沒有什麼必然的順序。如道路{3—2—5—7，4—6—7)屬於階段[3，4]，可由屬於階段[2，4]的道路{2—5—7，4—6—7)推出；而道路{2—3—6—7，4—5—7)屬於階段[2，4]，可由屬於階段[3，4]的道路{3—6—7，4—5—7}推出。可以很清晰地看出，這兩個階段的關係是有後效性的。對於這個問題是不能像上一個問題那樣來解決的。

例2 圖2中的⑤，假定從⑤到①的最小距離路由已經找到(本例為⑤一③一①)，則不管過去是從哪裏到達⑤的，從⑤開始以後的最小距離路由總是這一條(即⑤一⑧一①)這也就是説從⑤以後的決策總是一樣的，這就導致一個結論。以某一點為起點到目的地之間的最優化路由只與當前所處的地點或地位或狀態有關，而與過去如何到達這個起點的情況、條件無關，狀態序列的這個特性稱之為“無後效性弦”。 ^[4] 

服從指數分佈的等待時間

具有無後效性：對於任意t>0和s>o，有 ^[5] 

如果表示某系統中接連發生的兩次故障之間的時間間隔，則等式

表明，在時間段(s，s+t]上無故障的概率，只與時間段的長度t有關，不依賴於過去系統無故障工作的時間s。我們把這種性質叫做無後效性，這是指數分佈有廣泛應用的重要原因。

在離散型隨機變量的概率分佈中只有幾何分佈具有無後效性。可以證明，在連續型隨機變量的分佈中，只有指數分佈具有這種無後效性，這兩種分佈分別描繪離散等待時間和連續等待時間。