1樓：sugarsxjtu
關鍵在於狀態的定義，一般都是用最短路來講解動態規劃，其中點為定義的狀態，但狀態一般不是這麼簡單的，都是乙個複雜的結構體表現形式進行復合定義的。
2樓：Lunarnai
簡單來講，無後效性指的是當前狀態確定後，之後的狀態轉移與之前的狀態/決策無關。
題主猜想的沒錯，無後效性放到隨即過程裡可以表述為Markov性質。
我們可以將其以條件概率的形式表述為：
未來的狀態(t+1)只和當前狀態(t)相關，而和之前的狀態無關。
舉兩個例子：
簡單些的例子：迷宮問題中，假設你走到了(n,m)點，之後的狀態轉移不會再關心你是如何走到(n,m)點的，只關心你在(n,m)點的狀態資訊（例如耗費）。
更複雜的例子：圖模型中Clique Tree上的Belief Propagation演算法也利用了這種無後效性（馬爾可夫性質）來做動態規劃。每個clique在傳送belief message給下乙個節點時（狀態轉移），不再關心它的message是由哪些節點傳給它後聚合得到的。
3樓：zilongzkw
我說兩句吧。就好像社會規則是，只要你達到成功的那個狀態了，社會給你的評價，報酬和光環就一模一樣。那麼很多人就會想，我該怎麼達到成功狀態？
兢兢業業麼？那要十幾二十年啊，還是抄襲剽竊或者找個富婆吧。這就是無後效性導致的狀態轉移過程-- 每個階段我都盡量「最優」，少付出一點算一點。
如果社會對成功人士的「不擇手段」都進行歷史過程調查的話，那麼成功的狀態就僅僅是乙個參考了。被用來未來評價的狀態變數會變成：（院士，三代貧農，高考無作弊，始終愛黨愛學生）。
這樣人們會更注重過程，恪盡職守，腳踏實地。
4樓：
說白了就是，在最長公共子串行問題裡面：
輸10個字元，求到第5個字元的最長子序列的結果和，只輸前面5個字元，求到第5個字元（最後乙個）的結果；
一樣。
5樓：冒泡
如何理解動態規劃？ - 冒泡的回答
從不同的路徑走到乙個共同狀態，而後續的狀態變遷都是一樣的，和之前採用何種路徑到這個狀態沒有關係，即前面的各種決策結果由這個狀態表示，在考慮後半段的決策方面沒有任何區別
6樓：
非要按題主說的話，應該說之後發生的不會影響之前的結果。
拿最長公共子串行來說，你在後面碰到的字元不會影響你前面字元的匹配數量和結果，每次增加匹配到的字元時，都是「繼承」前面的結果之後加一。
所以如果後面的字元如果能改變前面的字元，那麼我們存狀態意義就不大了。就是因為有大量重複計算在遞迴裡，我們才用空間換時間，用了動態規劃。如果狀態總是變，那也沒必要存了。每次都暴力算就行
7樓：靈劍
一般我們說的最優解問題，最樸素的做法是搜尋所有的方案，大部分時候這個複雜度是不能接受的。對某些問題來說，我們可以將問題分解成子問題，子問題具有最優子結構的特點：對子問題的優化可以帶來對整個問題的優化。
但僅僅是這樣並沒有很大的幫助，因為我們對子問題的優化可能會導致整個問題的其他部分的解法變得不成立，或者變得不夠優化，這樣我們仍然不能有效計算整個問題的最優解。
但是，某些情況下，子問題對於整個問題的影響，可以歸納到乙個比「所有子問題解法」的空間小得多的「子問題狀態」空間中，只要子問題解決後的狀態處於某個狀態，它對於整個問題的影響就是一致的，這樣如果已知子問題處於某個狀態，我們就可以求出這個狀態條件下子問題的最優解，當全域性最優且這個子問題取這個狀態時，子問題本身的解法一定是我們剛剛求出的最優解。這樣我們只需要對每個子問題的每個狀態計算最優解，然後通過這些最優解的遞推關係就可以求出整個問題的最優解。這種子問題對主問題的影響可以總結為少數「狀態」的特性就叫做無後效性，意味著只要狀態一致，具體經過怎樣的步驟到達這一狀態是沒有影響的。
8樓：
馬爾可夫性就是無後向性。
無後向性是指以前出現狀態和以前狀態的變化過程不會影響將來的變化。
舉個簡單的例子就是：
圍棋具有無後向性。
比如我們下圍棋，現在有個局面，可能是隨機擺成的，也可能是認真下成這樣的，但是這不會影響我們下一步應該下的位置。也就是說歷史資訊不會影響我們以後的決策，當前的局面就是乙個里程碑，就是對歷史的總結，也是唯一影響未來的東西。
資料的異質性是什麼意思？
baccano 同樣搬經管之家的回答 異質性就是說研究的樣本的重要屬性上存在差異，比如人和人之間的消費習慣可能大相徑庭，這樣你記錄1000個人10年的月消費資料，即便他們收入流和資產完全相同，消費流也可能截然不同。在統計性質上，這種不同表現為異方差。所以在計量模型上，橫截面資料和面板資料經常出現，也...
動態規劃中的階段，狀態是什麼？應該怎麼找？
KellyFrog 一般來說，狀態要包含當前的所有可能用到的資訊，比如揹包中的體積，如果發現有後效性 當前的狀態內的資訊會影響後面的決策 那就加一維，就是這麼簡單。 ChathFaern 我認為動態規劃裡的 規劃 其實是遞推的意思，只是每一步運用的遞推規則會根據情況而動態變化，因此動態規劃其實就是動...
數學中的 分析 是什麼意思？
饒展 極限和無限描述的是過程，而不是狀態。任何乙個具體的狀態，都有發展的過程，你找到任何乙個角度，都可以無盡的拆分梳理這個過程，所以數學中的 分析 就是要把握森林中的每一棵樹木，甚至每一棵樹木的前世今生和平行空間，這和日常語言中講的 提綱挈領 是完全不同的。 Ethan Cheng 我們平日裡說分析...