無後效性是指如果在某個階段上過程的狀態已知，則從此階段以後過程的發展變化僅與此階段的狀態有關，而與過程在此階段以前的階段所經歷過的狀態無關。利用動態規劃方法求解多階段決策過程問題，過程的狀態必須具備無後效性。
基本介紹
- 中文名：無後效性
- 外文名：without aftereffect
- 所屬學科：數學
- 相關詞語：動態規劃法、決策問題等
原則簡介,實例說明,無後效性,
原則簡介
所謂無後效性原則，指的是這樣一種性質：某階段的狀態一旦確定，則此後過程的演變不再受此前各狀態及決策的影響。也就是說，“未來與過去無關”，當前的狀態是此前歷史的一個完整總結，此前的歷史只能通過當前的狀態去影響過程未來的演變。具體地說，如果一個問題被劃分各個階段之後，階段k中的狀態只能通過階段k+1中的狀態通過狀態轉移方程得來，與其他狀態沒有關係，特別是與未發生的狀態沒有關係，這就是無後效性。
對於不能劃分階段的問題，不能用動態規劃來解；對於能劃分階段，但不符合最最佳化原理，也不能用動態規劃來解；既能劃分階段，又符合最最佳化原理，但不具備無後效性原則的，還是不能用動態規劃來解；誤用動態規劃程式設計方法求解會導致錯誤的結果。
實例說明
例1 貨郎擔問題和旅行路線問題。貨郎擔問題是對平面給定的n個點確定一條連線各點的、閉合的最短遊歷路線問題。圖1(a)給出了7個點問題的解。旅行路線問題是貨郎擔問題的簡化，這種旅行路線先從最左邊開始，嚴格地由左至右到最右邊的點，然後再嚴格地由右至左到出發點，求路程最短的路徑長度。圖1(b)給出了7個點問題的解。
圖1
圖1這兩個問題看起來非常相似，但本質上是完全不同的。為了方便討論，可以將每個頂點標記號碼。由於必然經過最右邊的頂點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中的⑤，假定從⑤到①的最小距離路由已經找到(本例為⑤一③一①)，則不管過去是從哪裡到達⑤的，從⑤開始以後的最小距離路由總是這一條(即⑤一⑧一①)這也就是說從⑤以後的決策總是一樣的，這就導致一個結論。以某一點為起點到目的地之間的最最佳化路由只與當前所處的地點或地位或狀態有關，而與過去如何到達這個起點的情況、條件無關，狀態序列的這個特性稱之為“無後效性弦”。
無後效性
服從指數分布的等待時間
具有無後效性：對於任意t>0和s>o，有
