#78 演算法裡的貪心方法

前面的文章曾提過,在這世界上有很多不同類型的問題,基本上我們太不可能找到一個方法來解決所有的問題.所以,不同類型的問題就會有不同的解法.有的解法很好理解並且單純,有的解法不易理解.解法本身並沒有所謂的好壞,只有適不適合使用的情況.通常來說,難的問題若要有好的執行結果,通常那個解法不見得簡單,就算是簡單,也絕非容易可以想的出來.這也許就是演算法美妙的地方,或許可以說是邏輯之美.廣泛地也可以說成是數學之美,都是宇宙空間裡所擁有的一些特質.

今天要提的解法是一種貪心 (Greedy) 的 “精神”.若你沒念過演算法這門課,恭喜你可以免除這個宇由特質的迫害,可以遠離那種整晚埋頭寫作業的崩潰時光.我想我是比較笨的,所以我以前寫演算法和計算理論的作業時,常常抱著頭在燒.如今,回頭看看,這些都是人生裡蠻有趣且值得回憶的時光.演算法課本裡,前面一半的內容中主要是提到一般市面上對問題的 “解法” 有那些.一個問題可以有多種不同的解法,就像你的工作上要達成某一個任務,可以用不同的技巧或手法來達成該任務.因此,解法可以說是一種邏輯思考的過程,也可以說是一種寫程式的過程.基本上,寫程式就是一種邏輯思考的具體呈現.因此,演算法的課程裡前面一半就是在教你如何 “邏輯思考” 來解決問題,其中最簡單的思考方式就是 "貪心" (Greedy).

貪心的精神在於在解決問題的過程中選擇一個 "當下" 最好的決定來繼續往下執行程式.這是什麼意思呢 ? 舉一個相當簡單的例子.假設你對台北的街道並不熟悉,而你現在位於台灣大學的校園裡,你接到一個任務是要找出徒步走路到陽明山的路徑.想一想,你會如何思考來解決這個問題呢 ? 別忘了,前提是你對台北的街道並不熟悉,但是你知道陽明山在北邊,因為天氣好時你能看到陽明山.”貪心” 的精神就在於,位於所在位置,在此時那一條路是最好的選擇就走那一條路.由於不熟悉台北街道,你只好依照陽明山的方向前進,可能沿著敦化南北路一直往北走後,結果你發現松山機場卡在前面,不僅如此,機場旁邊還有一條基隆河.只好在機場前做出往右走或往左走的決定,來找到橋讓你渡過基隆河,然後再一直依著陽明山的方向前進.這種邏輯思考就是每走到一個路口,再來決定下一個方向要如何走.如果運氣不好,剛好走到沒有橋能跨越基隆河的路口,那只好再依當下的情況做出最好的決定.往左走或往右走不代表一定會有橋可以過,所以你也可以感受到這種 “貪心” 的解決方法似乎有點風險. 因為 "貪心" 提供的解答通常不會是最好的答案,所謂最好的答案像是最短路徑,最省時的路徑等.除此之外,你也能感受到依照 "貪心" 方法,要寫出這方法的程式還蠻直覺和容易的. 因此,不同方法都有不同的優缺點.要決定用什麼方法之前就必須對你的問題有完整的了解.

再舉另外一個例子,在前面的文章裡曾提到 #48 老鼠走迷宮 .在這文章所提供的程式碼就是一種 "貪心" 的解法,因為從這一步走到下一步時,只單純考慮是否可以通行,不會考慮其他因素.因此,經由 "貪心" 得到的路徑是一條 "可以走" 的路,但不一定是 "最短" 或 "最省力" 的路.如果你找到的路剛好是最短或最省力,那只是說明你當下的運氣好,並不代表 "貪心" 解法能帶給你最佳值.

你可以想一想,在你的工作中,是不是用了很多 "貪心" 的方式來寫程式呢 ? 我相信大部份朋友們的程式碼一定讓 "貪心" 佔據了大部份,因為 "貪心" 並不需要人類特別去想像才能發明出來的方法,它本身就是最單純的思考方式.如果有一個問題連 "貪心" 都無法解決時,那這問題應該真的可以稱上是超級難題了.

完全沒寫到任何程式碼來解釋 "貪心",不知道這樣效果如何 ?

Hope it helps,



Share:

0 意見:

張貼留言