前面的文章曾提過，在這世界上有很多不同類型的問題，基本上我們太不可能找到一個方法來解決所有的問題．所以，不同類型的問題就會有不同的解法．有的解法很好理解並且單純，有的解法不易理解．解法本身並沒有所謂的好壞，只有適不適合使用的情況．通常來說，難的問題若要有好的執行結果，通常那個解法不見得簡單，就算是簡單，也絕非容易可以想的出來．這也許就是演算法美妙的地方，或許可以說是邏輯之美．廣泛地也可以說成是數學之美，都是宇宙空間裡所擁有的一些特質．
今天要提的解法是一種貪心 (Greedy) 的 “精神”．若你沒念過演算法這門課，恭喜你可以免除這個宇由特質的迫害，可以遠離那種整晚埋頭寫作業的崩潰時光．我想我是比較笨的，所以我以前寫演算法和計算理論的作業時，常常抱著頭在燒．如今，回頭看看，這些都是人生裡蠻有趣且值得回憶的時光．演算法課本裡，前面一半的內容中主要是提到一般市面上對問題的 “解法” 有那些．一個問題可以有多種不同的解法，就像你的工作上要達成某一個任務，可以用不同的技巧或手法來達成該任務．因此，解法可以說是一種邏輯思考的過程，也可以說是一種寫程式的過程．基本上，寫程式就是一種邏輯思考的具體呈現．因此，演算法的課程裡前面一半就是在教你如何 “邏輯思考” 來解決問題，其中最簡單的思考方式就是 "貪心" (Greedy)．
貪心的精神在於在解決問題的過程中選擇一個 "當下" 最好的決定來繼續往下執行程式．這是什麼意思呢 ? 舉一個相當簡單的例子．假設你對台北的街道並不熟悉，而你現在位於台灣大學的校園裡，你接到一個任務是要找出徒步走路到陽明山的路徑．想一想，你會如何思考來解決這個問題呢 ? 別忘了，前提是你對台北的街道並不熟悉，但是你知道陽明山在北邊，因為天氣好時你能看到陽明山．”貪心” 的精神就在於，位於所在位置，在此時那一條路是最好的選擇就走那一條路．由於不熟悉台北街道，你只好依照陽明山的方向前進，可能沿著敦化南北路一直往北走後，結果你發現松山機場卡在前面，不僅如此，機場旁邊還有一條基隆河．只好在機場前做出往右走或往左走的決定，來找到橋讓你渡過基隆河，然後再一直依著陽明山的方向前進．這種邏輯思考就是每走到一個路口，再來決定下一個方向要如何走．如果運氣不好，剛好走到沒有橋能跨越基隆河的路口，那只好再依當下的情況做出最好的決定．往左走或往右走不代表一定會有橋可以過，所以你也可以感受到這種 “貪心” 的解決方法似乎有點風險. 因為 "貪心" 提供的解答通常不會是最好的答案，所謂最好的答案像是最短路徑，最省時的路徑等．除此之外，你也能感受到依照 "貪心" 方法，要寫出這方法的程式還蠻直覺和容易的． 因此，不同方法都有不同的優缺點．要決定用什麼方法之前就必須對你的問題有完整的了解．
再舉另外一個例子，在前面的文章裡曾提到 #48 老鼠走迷宮 ．在這文章所提供的程式碼就是一種 "貪心" 的解法，因為從這一步走到下一步時，只單純考慮是否可以通行，不會考慮其他因素．因此，經由 "貪心" 得到的路徑是一條 "可以走" 的路，但不一定是 "最短" 或 "最省力" 的路．如果你找到的路剛好是最短或最省力，那只是說明你當下的運氣好，並不代表 "貪心" 解法能帶給你最佳值．
你可以想一想，在你的工作中，是不是用了很多 "貪心" 的方式來寫程式呢 ? 我相信大部份朋友們的程式碼一定讓 "貪心" 佔據了大部份，因為 "貪心" 並不需要人類特別去想像才能發明出來的方法，它本身就是最單純的思考方式．如果有一個問題連 "貪心" 都無法解決時，那這問題應該真的可以稱上是超級難題了．
完全沒寫到任何程式碼來解釋 "貪心"，不知道這樣效果如何 ?
Hope it helps,
0 意見:
張貼留言