#79 貪心策略 - Greedy (2)

上一篇文章談了貪心策略的基本想法，但並沒有提到任何的程式碼來說明貪心策略是怎麼進行的．其實貪心策略並沒有一個很明顯程式碼撰寫方式，如果硬是要湊出一個程式碼外型的話，我覺得它的長相可能如下:

while ( 依問題條件來決定是否要繼續下一步 )
{
    // 1. 依照問題，在這一個步驟裡取得最佳解
    // 2. 根據步驟一得到的最佳解來決定程式的下一個狀態
    // 3. 將程式目前的狀態移動到下一個狀態，下一個狀態將會更接近最終的答案
}

老鼠走迷宮是很典型資料結構 Stack 作業，它的內容是假設一個方形的土地，這土地用畫分成許多面積相等的小格子，就像棋盤那樣．每一個格子都是一種地形，如山，河，平地．老鼠只能走平地，不能爬山也不能過河．老鼠將從起點走到終點，起點是在這土地的左上角，而終點是在右下角．這個作業就是要讓老鼠能走出一條路從起點到終點．如果沒有路存在，則最後的答案是 null，若有路存在，則最後的答案是每個格子的座標集合．老鼠走迷宮用貪心策略來展現其演算法，它的程式結構如下:

while ( 老鼠未到達終點 )
{
    1. 在目前格子，依順時鐘順序找到一個可以走的格子，並且這個格子沒走過而且其地形不是山或河
    2. 如果所有可走的格子都已走過或都是山河等地形，則下一個格子是上一個步驟的格子．
    3. 將老鼠移動到下一個格子
}

在老鼠走迷宮的例子中，老鼠在每一個格選擇下一個格子時，此時便是要求一個 “當下” 的最佳解．走過的格子不能走，地形是山或河的格子也不能走，所以只剩下一般的平路．在 “當下” 的情況下，下一個格子是平路的情況可能超過一個方向，此時我們無法得知下一個格子之後的狀態，因此，可以依序或隨機選擇一個格子來走．畢竟都是平路的格子，所以在 “當下” 來說都是最佳解．

誠如上一篇文章所說，這樣的解法通常不會是最佳解．在老鼠走迷宮的問題中，最佳解通常是指最短路徑．如果老鼠走的土地剛好只有一條路可以走的話，那麼用貪心策略寫出來的程式找到的路徑剛好就是最短路徑，因為只有一條而己．但現實中的問題裡，幾乎很難會遇到這種情況．

另外，你也能感受到貪心策略只考慮 “當下” 而己，不會再多考慮下一步，所以你也能看到貪心的策略並不用利用其他的資料結構去記錄一些有關那一條才是最佳路徑的事情．也是因為如此，程式寫起來才比較簡單，因為你只需要用一個 Stack 來記錄走過的格子，而不需要為每一個格子去記錄所有可能的狀態．由此，你也能感受到求最短路徑就不是那麼簡單直覺的事情了．

Hope it helps,

閱讀全文