動態規劃和貪心的本質區別是什麼？

作者：由匿名使用者發表于攝影時間：2015-07-11

黃立夫2015-10-19 13:42:44

某種程度上，動規是貪心的泛化，貪心是動規的特例。

BillXu20002017-02-27 22:58:54

動規：大爆搜

貪心：把大爆搜剪枝剪到只有一條

（大霧

知乎使用者RH7FQr2017-05-07 08:38:12

我嘗試用一個最近我琢磨的動態規劃問題作為例子解釋一下，看看能不能幫到題主。由於沒怎麼正經學過演算法，如果答案中有什麼不對的地方，懇請各位路過的朋友批評指正，我好「聞過裝喜」。

這個問題叫做 Bitonic euclidean salesman 問題（《演算法導論》一書動態規劃一章後面的習題）。考慮平面直角座標系上的 n 個點（n >= 2），它們的橫座標兩兩不同。假如我想這樣經過所有這些點：

先從最左邊一個點出發，以直線段連線其中一部分點，到達最右邊一個點。

再從最右邊一個點出發，以直線段連線剩下的點，到達最左邊一個點。

這種遍歷的方式，叫做 Bitonic 的（雙調的，即兩次單調之和）。要求找到滿足上述方式而構成的直線段環路中最短的。

由於常年是一個糊塗蟲，我一上來就把問題想簡單了。將這些點從左到右記為 P_0， P_1，。。。， P_{n - 1}，考慮前 k 個點加上最後一個點組成的環路。這些點中，肯定有一部分在最優環路的從左到右的那部分（記為 L2R），而另一部分在最優環路的從右到左部分（記為 R2L）。（當然，由於對稱性，L2R 和從 R2L 可以互換。以及，兩端的兩個點，我們認為既不屬於 L2R，也不屬於 R2L。）現在考慮第 k + 1 個點，即 P_{k}。我肯定得把它加到 L2R 或 R2L 中。那麼，我當然選擇其一，使得新行程 L2R 和 R2L 的長度總和最小啦。這樣做，我其實考慮的只是「眼前利益」，這種做法就是所謂「貪心」的。

很遺憾，在這個問題上，「貪心」的做法是得不到全域性最優解的。

因為，我沒有考慮，將 P_{k} 加入的時候，之前已經決定好的 L2R 和 R2L 是否需要做出改變。

這一點不難找到反例，如 n = 5，各點分別為（0， 0），（1， 2），（2， 1），（3， 5），（4， 0）。當 k = 3 時，我們只是沒有考慮（3， 5）這個點，另外 4 個點構成的最優環路中，

L2R = （0， 0）

--> (1, 2) --> (2, 1) -->

（4， 0）以及 R2L = （0， 0）

<--

（4， 0）。

這個結論透過窮舉就不難得到。但我們加入第 k + 1 個點（3， 5），再透過窮舉可以發現，新形成的最優環路中，

L2R = （0， 0）

--> (1, 2) --> (3, 5) -->

（4， 0）以及 R2L = （0， 0）

<-- (2, 1) <--

（4， 0）。

這裡帶上左右端點，顯得清楚一點。也就是說，我們把 P_k = （3， 5）這個點加入 L2R 的時候，需要把（2， 1）挪到 R2L 中去，才能保證新形成的環路的最優性。這就使得「貪心」的計劃破產了。

用動態規劃來解決這個問題可能有不止一種辦法。例如，我們維護幾個陣列：

L［1 。。 n - 2， 0 。。 n - 2］

second_right_most_L2R［0 。。 n - 1］

right_most_R2L［0 。。 n - 1］

除左右端點外，將剩餘的點即 P_1， P_2，。。。， P_{n - 1} 從做到右遍歷一次。透過適當的計算，使得遍歷經過 P_i 之後，對 j <= i：

L［i， j］記住的是 P_0， P_1，。。。， P_i 以及 P_{n - 1} 組成，且 L2R 部分的最右點為 P_j 的最優環路的長度；

second_right_most_L2R［j］是這條環路 L2R 部分次右點的編號；

right_most_R2L［j］是這條環路 R2L 部分最右點的編號。

不論是 L，還是剩下那倆倒黴催的陣列，其實維護的都是遍歷經過某個點時的「狀態」。維護了這些「狀態」（或者說，擴充了問題本身能直接看出來的那些「狀態」），就能讓問題呈現出「最優子結構」，即子問題的最優解經過適當的計算能得到母問題的最優解。這種計算方式，由於不僅僅是看「眼前利益」，還利用了記錄了「歷史」的「狀態」們，就不再是「貪心」的。