電腦科學 ^ IT人生 ^ 公益課程

#78 演算法裡的貪心方法

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

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

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

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

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

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

Hope it helps,



Share:

#77 部落格的原始動機與人生所需的財務智商

這篇文章來分享二個主題,第一是為何我開始寫這個部落格,第二是人生所需的財務智商.

我在 "大毛電腦科學筆記" 裡從 2015 年 3 月開始寫下第一篇文章到現在已經有三年半的時間了.剛開始的第一年,由於我沒有設計任何的讀者回饋方式,因此第一年並不知道寫的內容是否有用.後來第二年開始加入 Google Form 讓讀者們可以留下回饋資訊,並且也為網站上加入 Google Analytics 用來查看網站的流量資訊.大約一年前成立了 Facebook 社團以及舉辦公益課程來做為另一種推廣此部落格的管道.從去年 (2017) 開始,我陸陸續續收到一些讀者們的回饋,有些是單純地謝謝我寫這些淺顯易懂的內容,也有些是來問我一些工作上的問題.謝謝大家的捧場和問題讓我知道這個部落格已經發揮了一些作用.其實,我最早的想法並不是寫部落格,而是打算把所有的資訊匯集成冊出版用.早在十年前,我收集了以前在台灣和美國念的上課筆記,打算將這些內容寫成書來出版.但可惜,後來因為搬家緣故,那一大本的筆記已下落不明,所以把筆記匯集成書的想法便中斷了.但我並沒有忘記要分享電腦科學的基礎知識這件事.後來心想,匯集成冊需要大量時間並且有出版時程的壓力,於是 2015 年初便改用部落格的方式進行分享.這樣一來,沒有時間壓力,可以一篇一篇慢慢寫.最主要的想法是要將電腦科學裡的基礎知識分享給在資訊界裡非本科系畢業的資訊人.與其說是分享,也可以說是一種對自己人生中某幾段求學和工作過程的記錄.誠如我在 "有關作者" 的頁面裡所寫的,我自己在大學時念的是機械工程,但因緣際會的人生巧合,我轉換跑道到電腦科學,在台灣待過一般的軟體專案公司,然後也在美國待過所謂的大型軟體公司進行軟體產品的開發工作.這一路走來,像我這樣在大學時學非所用然後因好運氣而進入到大公司參與軟體產品開發的人應該是相當少見,也因此更激勵我把許多知識和心得分享出來.一方面希望能幫助或鼓舞其他人,另一方面也為自己的 IT 人生留下一些深刻而明確的記錄.在這三年半的時間裡,記錄了文章大致上有資料結構,資料庫系統,些許的程式設計,以及正在撰寫的演算法.後續的內容還會有更多的程式設計,作業系統,分散式系統,甚至影像處理,人工智慧,以及其他大家有興趣的內容.我自己並未設限要寫到什麼情況下才算結束,就一切隨緣吧! 根據這一年來的網站流量資料,每個月大約有二百個連線拜訪這個部落格,若以網站經營的角度來看,這是一個流量超級低的網站.不過,這部落格不是以營利為出發的網站,除了 domain name 要花些錢註冊以外,其他都是免費資源,因此沒有營利需求.大部份拜訪到此部落格的使用者都是經由 Google search 而來的.這些網路上來的使用者都是經由關鍵字搜尋而找到此部落格,例如搜尋 Heap file, database B-tree 等等.因此,有緣來拜訪此部落格的朋友都會對這裡的文章感到興趣,也是這樣的情況,我才會從去年開始陸續收到網站拜訪者的留言與回饋.若你有任何建議,也別忘了留言告訴我.

之前我曾在 IT人生 的系列文章中提到一個與銀行戶頭有關的文章.簡單地講就是 "錢".這也是一般年輕人比較容易忽略的事情,但這件事情卻又是如此地重要.對我自己而言,錢能提供的不是成就感,而是一種安全感.在你依照自己的目標追尋自己的成就感時,有點錢在身邊是一種安全的保障,能幫助你應付一些緊急的狀況.也許你可能會覺得找份工資高的工作不就好了,我也希望事情有這麼簡單就好了.以許多進步的國家來看,來自國家所設計的保障在未來都是有倒閉破產的風險,像是台灣的勞工保險 (非勞工退休金),在未來某一天也會因繳的人少且領的人多而面臨入不敷出的情況,既便是像美國的 Social Security 在未來的十幾二十年後也是會面臨同樣的問題,這樣的問題在許多國家都存在.因此,只想要依靠當初政府所設計的保險制度來領取退休金的人們要小心了,因為錢不一定領的到.我相信大部份的讀者都是二三十歲的人,離退休還有很長的一段路.因此,要讓自己保有良好的 "財務智商" 是相當重要的事情.不論你從事什麼樣的工作或是領多少薪水,財務計畫和規畫是每一個人都不該錯過的課題.自己的退休金最好還是要自己先準備好.所以,我才會特別強調這件事情讓還沒準備的讀者們要想一想這件事.如果你願意花假日的時間去上課學習一些新的軟體產品與開發技術,那何不也花一些時間讓自己學習有關 "錢" 的事情.你花時間學了一個新的產品或技術,頂多只能用個三四年,然後就有新的版本或新的技術需要學習,成本是很高的.若你學習有關 "錢" 的事情,那是一輩子受用的事情,不會有什麼每隔幾年得重新學習的情況.最近,我在 YouTube 上看到兩個年輕的台灣網紅 (柴鼠兄弟),他們錄製了許多的短片,每一個短片都用淺顯易懂的方式來說明與投資理財有關的內容,這就像我喜歡用淺顯易懂的方式來描述許多電腦科學裡的知識一樣,因此我非常喜歡他們的影片.我強烈建議對 "錢" 還沒什麼概念的讀者們可以看看他們的影片來增加自己的財務智商,為你未來的生活增加財務上的安全感.

Hope it helps,


Share: