#94 演算法的 Backtracking 策略

 Backtracking 是一種演算法的策略，可用來解決三種面向的問題，分別是 Decision problem, Optimization problem, 以及 Enumeration problem．有關 Optimization problem 在前面的文章裡已經談過不少，這裡不多說明．一個 Decision problem 可能會有至少一個或一個以上的解答，這種問題我們通常只要找一個可用的解答．Enumeration problem 和 Optimization problem 蠻相近，就是要將所有解答找出來．舉個例子，之前講過的老鼠走迷宮是一種問題，如果我們要找一條可行的路，那麼老鼠走迷宮將是 Decision problem．如果我們要找出一條最短的路，此時便是 Optimization problem．如果要將所有可行的路找出來，這便是 Enumeration problem．不同的問題需要不同的解決策略．Backtracking 就這麼巧地可以用來做為這三種問題的解決策略．

以西洋棋裡 n-Queen 問題來說明，一般以 n = 8 為市面上較為熱門的題目，現在我們把 input size 縮小一點，將 n=4. 而棋盤和其中一個可行的解答如下:

Source: https://www.geeksforgeeks.org/backtracking-introduction/

n-Queen 問題的解決策略如果用最直覺的暴力法來做，其解法如下

1. 列出所有 Queen 的排列座標，例如

    Answer candidate 1: (0,0) (0,1) (0,2) (0,3)

    Answer candidate 2: (0,0) (0,1) (0,2) (1,3)

    Answer candidate 3: (0,0) (0,1) (0,2) (2,3)

    Answer candidate 4: (0,0) (0,1) (0,2) (3,3)

    Answer candidate 5: (0,0) (0,1) (1,2) (0,3)

    .... 以此類推， 一共有 4x4x4x4 = 256 種位置．

2. 然後將每一個候選答案放到一個檢查器．這個檢查器就是題目要求的，要讓每個皇后所在的位置不會影響到其他的皇后．這個檢查器要執行的程式碼就是問題本身所給出的限制．你我都知道，暴力法簡單粗暴，保證一定讓你能找到答案，但不保證能快速找到答案．這個問題的 "限制" 本身就是一個有點複雜的運算了．如果你忘了西洋棋的皇后走法，你需要複習一下才能知道這裡所說有點複雜運算的意思了．

如果是用 Backtracking 的策略，該怎麼做呢 ?

Backtracking 的策略在我看來和暴力法是有一點接近的．只是差別在於 Backtracking 不會一開始將所有可能列出來，然後再進行對每個輸入一一地檢查．Backtracking 的策略是在產生所有可能的排序方式過程中，就直接檢查了．如果在過程中不符合 "限制" 時，則中斷這條路，然後跳到下一組排列來做.

以上述的答案候選為例子:

一開始，第一個皇后放在 (0,0)，然後試著將第二個皇后放在 (0,1)，執行檢查器，這樣檢查器會回傳 false，因為棋盤上同一行只能有一個皇后．於是，後面答案候選裡面只要是 (0,0) (0,1) 開頭的組合便可跳過．前面兩個皇后的位置已經不合法了，所以後面的皇后也不用浪費時間檢查．若以程式的角度來看，某一層次的 for loop 將可以整個跳過去而不執行．所以，下一個要檢查的便是從 (0,0) (1,1) 開頭的答案. 

以上的過程的解題思考就是 Backtracking．

看到這裡，雖然我們沒有寫出細節的程式碼，但我相信你能感受到 Backtracking 的解題策略的精神是什麼了．Backtracking 適合用在需要 recursion 來解決的問題．在我們試著將所有的可能答案窮舉出來的過程中，就執行著 "檢查器"，一旦發現檢查器不通過，就直接跳開這一個層次的答案，直接轉往下一個層次，這就是 Backtracking 能夠省出時間的方式．上述的 n-Queen 是一個常見的例子，Sudoku 也是一個常見的例子. 我相信在你的工作中 Backtracking 能派上用場的時機點是很多的．

底下的程式碼是我小徒弟在數個月前練習解決 Sudoku 題目的程式碼，其解決策略是 Backtracking.

閱讀全文

#90 淺談 Dynamic Programming (2)

 前面說過 dynamic programming 的應用很多，這一篇文章來說明其中一種應用，Maximun subarray sum．這個問題是在一個整數的 array 裡找一個連續空間的元素，其元素的總和的值是最大的．如下圖:

source: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

從 index 2 到 index 6 之間的元素總和等於 7，這個區間是這個 array 裡最大的區間總和. 要解決這個問題其實不難，因為用最直接的暴力法就可以解決了，其程式結構如下:

這一個暴力法的時間複雜度是 O(n*n*n) ，n 是 array 的長度. 如果 n 很小，影嚮不大，但若 n 很大，這一個運算雖然在空間複雜度很表現的很好，但浪費許多 CPU 的運算資源，因為許多加法的計算是重覆了. 將這個問題的時間複雜度降低的方法不只一種，在這篇文章裡，我們用 dynamic programming 的策略來試著降低時間複雜度．如前一篇文章提過的內容，dynamic programming 的策略在於用空間換取時間，所以我們必須找出在什麼地方可以減少重覆的計算．要減少重覆計算之前，我們可以先從暴力法來看到底真正的計算是花在什麼地方了. 從上述的程式碼，你可以看到決定 subarray 的總和值是從最裡面的迴圈來運算的，所以第一圈會計算 start = 0 , end = 0 的總和值，第二圈會計算 start = 0, end = 1 的總和值, 第三圈會計算 start = 0, end = 2 的總和值，以此類推下去．透過觀察，你便能發現第二圈要計算的內容在第一圈已經算過了部份答案，第三圈要計算的內容在第二圈已經算過了部份的答案，因此，最裡面的迴圈其實是重覆了做了許多相加.

Loop 1: -2 

Loop 2: -2 + -3 = -5  (Loop 1 + -3)

Loop 3: -2 + -3 + 4 = -1 (Loop 2 + 4)

Loop 4: -2 + -3 + 4 + -1 = -2 (Loop 3 -1)

因此，透過以上的運算呈現，便能知道最後一個迴圈是可以去除的．我們只要將上一圈計算後的內容先暫存起來，留到下一圈時便能拿出來用，直接做一次加法就可以得到這一圈的答案了．因此，那個查表法的 "表" 也只不是一個臨時的變數，在空間複雜度上並沒有增加，而時間複雜度卻降了一階變成了 O(n*n)，如下列的程式碼.

接著，或許你還會問，空間複雜度還仍再降嗎 ? 剛好這一個題目是可以的，它的名字是 Kadane's algorithm，這個演算法在許多讀者還沒出生之前就已經發明了，這演算法能用 O(n) 的時間複雜度解決這問題，而發明人是一位教授，現在已經非常高齡了. 若你晚些才看到這篇文章, Kadane 教授也許不在人世了，我們大家都是站在巨人的肩膀上.

最後，你可能會問這個演算法我們該用在那裡．這完全取決於你是否會遇到類似的題目．如果你遇到一個問題，而這問題剛好可以 Reduce 成 maximum subarray sum 時，Kadane's algorithm 便能幫助你寫一個超快速的程式來解決問題，例如，你老闆要你找出過去十年裡，那幾個連續的月份其營業額是最好的．

Dynamic programming 的策略確實應用在許多地方，未來介紹更多的主題時，一定都還會碰到 dynamic programming 策略所產生的解法.

閱讀全文

#89 淺談 Dynamic Programing (1)

Dynamic programming 是大學部演算法課程裡相當重要的一個主題，也是典型用空間換取時間的策略．但奇怪的是，這個策略一點也不 dynamic ，一點也不 programming．老實說，我不知道為何這個策略叫 dynamic prograaming，我倒覺得它比較適合叫 "查表法". 接著就來看看為何說它是查表法.

Fibonacci number 是許多演算法課本用來解釋 dynamic programming 最簡單的例子．Fibonacci number 是以數學多項式來表達的數字集合，以數學式來表達就可以寫成如下:

F(n) = F(n-1) + F(n-2) 

也就是說求第 10 項 (n=10) 的答案時，你必須要先算出來第 9 項和第 8 項. 如果要求第 1 項呢 ? 難道要找出第 0 項和第 -1 項嗎 ? 在 Fibonacci number 上，我們會為這個 number 定義起始點，也就是說第 1 項和第 2 項的值是早被確定的，往後的項次皆由這兩項為基礎而算出來，所以不會有第 -1 項的情況. 假設, F(0) = 0, F(1) = 1 ，那麼數列的答案如下:

F(2) = F(1) + F(0) = 1 + 0 = 1

F(3) = F(2) + F(1) = 1 + 1 = 2

F(4) = F(3) + F(2) = 2 + 1 = 3 

F(5) = F(4) + F(3) = 3 + 2 = 5 

F(6) = F(5) + F(4) = 5 + 3 = 8  以此類推

當你要算第 n 項時，就按以上的方法一直算到第 n 項就能得到答案. 接著，數學公式 F(n) = F(n-1) + F(n-2) 寫出來了，那麼寫程式碼就變得相當簡單.

透過一個 recursive function 就能快速完成  Fibonacci number 第 n 項的計算程式．這一個程式碼沒有使用額外的記憶體空間，所以 space complexity 是 O(1)，但仔細看一下 time complexity，卻發現超乎想像的大，因為有許多重覆的步驟:

            F(5)  
          /     \
       F(4)      F(3)
      /    \    /    \
   F(3)   F(2) F(2)  F(1)
   /  \
 F(2) F(1)

上圖是整個 recursive 的關係. 意思就是，當程式在 F(5) 那一個層次要往下呼叫時，程式會呼叫自己兩次，並傳送 4 和 3 為輸入參數，當第一個 recursive call 再進去時，又會再呼叫自己，並傳入 3 和 2 為輸入參數，以此類推．所以你可以看的出來，有許多重覆的計算在這 recursive 的過程中一直發生．以上圖來說，F(3) 發生了 2 次，F(2) 發生了 3 次．當 n 是一個大的數字時，你就可以發現比 n 越小的數字，重覆計算的次數越多，並且是以指數趨勢來增加．上述的程式碼雖然很簡單，但是 time complexity 卻是很可怕的．上述的程式碼是由上而下計算下來的，假設我們繼續用由上而下的計算方式，改良此程式碼的方法就是將 "重覆" 的計算步驟讓它不要重覆計算．如上圖，如果 F(3) 只真正地被計算了一次，而 F(2) 只真正地被計算了一次，那麼就不會有重覆計算的事情了．為了達成這目標，最簡單的方法便是把計算後的結果儲存下來，等到要計算一樣的內容時，去 "查表" 即可．也就是說第一次 F(3) 計算的結果儲存下來，當程式遇到第二次的 F(3) 時，直接去查詢，若有答案，直接將答案拿來使用，這樣就不用計算了．同時，為了確保不會造成過多的 time complexity，我們也需要確認答案的儲存和查詢所花費的 time complexity 要非常小，如 O(1)．這種 "查表" 的精神也是 dynamic programming 所代表的策略．

若將上述的程式碼加入 "查表" 的功能，它將看起來如下:

或是直接改成由下往上計算

以上兩個程式碼雖然結構有點不太一樣，但都是用了一個 array 來記錄每一個項次計算的答案，因此 time complexity 省下來了，而且 space complexity 也增加了，但這樣的空間增加似乎是值得的．當然也可以再把上述的程式碼繼續改下去讓 space complexity 變的更小，不過這並不是這篇文章的重點．透過以上的簡單例子讓大家方便了解 dynamic programming 的 "查表" 意義是什麼．許多世界上有名的演算法都是基於 dynamic programming 的精神所發展出來的，例如你幾乎每天都在用的字串比對演算法就是基於 dynamic programming 所發明出來．

這篇文章用 Fibonacci number 的例子來說明 dynamic programming 的精神，這是相當簡單的例子，下篇文章我們用較難的例子來說明 dynamic programming 的用法.

閱讀全文

#86 貪心方法是最佳解 ?

最佳解? 這種解答是許多問題所追尋的目標．例如，在一個城市裡找到出發點和目的地的最短距離．直覺來看，若你沒有把所有可能的路徑列出來，你怎麼知道那一個才是最短的．再舉例一個例子，在一個 int array 裡面，找出最大值的元素位置．若你沒把所有的元素都拜訪一遍，你怎知道那一個才是最大的．這兩個例子雖然都是在找 "最佳解"，但是解法的思考卻不太一樣．第二個例子的思考是 "一條路"，而第一個例子是 "多條絡"．在 "一條路" 的情況下，對下一個步驟來說沒什麼好選擇的，只能一直往前走．然而，"多條路"的情況下，在什麼路口選擇什麼路，這對答案或執行過程會有很大的影響． 

前面已有兩篇文章簡單地介紹了貪心方法．這篇文章要討論的是利用貪心方法得到的解答會是最佳解嗎 ? 用一個簡單的問題來測試．假設郵局提供的郵票面值如下:

$10, $5, $2, $1, $0.5, $0.2, $0.1 

現在你要寄一封信，它所需的郵資是16.1 元，請問最少要用幾張郵票 ? 這是一個最佳解的問題，目的是要找最少的郵票數量. 使用貪心方法來解這問題，它所需的程式碼如下:

以上的程式範例就是一個貪心方法．從最大的面值一直嘗試到最小的面值，一直湊到超過所需要賺買的郵票面值. 得到的答案是 $10, $5, $1, $0.1，需要四張郵票，面值是 10, 5, 1, 0.1 剛好能湊到 16.1，並且也這麼湊巧，四張郵票剛好是最佳解.

如果把郵票的面值改變，新的郵票面值有 

$5, $3.7, $3.1, $2.9, $2.3, $2, $1.7, $1.3, $1, $0.5, $0.2, $0.1

當我們再用同樣的程式去執行時，得到的答案會是 $5, $5, $5, $1, $0.1 ，需要 5 張郵票．但你認真排列之後，你會發現有一個更好的答案，那就是 $5, $3.7, $.3.7, $3.7，只需要 4 張郵票即可．此時便可發現貪心方法並無法保證我們一定能夠得到最佳解．如果得到最佳解，只能說題目本身的特性剛好能讓貪心方法得到最佳解而己．

從第一個問題來看，最佳解的答案有幾個特性

1. 答案最多一個 $0.1，因為若有兩個以上的 $0.1，便可以用 $0.2 來替代．

2. 答案最多兩個 $0.2，因為若有三個以上的 $0.2，便可以用一個 $0.5 和一個 $0.1 來替代.

3. 答案不會存在兩個 $0.2 和一個 $0.1，因為可以用一個 $0.5 替代.

還有一些其他的特性可以類推而得．同時，第二個問題可以用同樣的方式來找出最佳解的特性．第二個問題的其中一個特性就是，不該出現兩個 $5, 一個 $1 和一個 $0.1，因為可以用三個 $3.7 來替代，所以我們用貪心方法所得到的答案便不會是最佳解．

閱讀全文

#82 K個最近鄰居演算法 (k-nearest neighbor algorithm, KNN)

在大部份的科學領域裡都蠻注重分類 (Classification) 這件事．透過分類，它能幫助我們整理問題，也能整理答案，甚至在不同的問題集合裡找出通用的答案．在人工智慧的領域裡，有一門科目叫模式辨認 (pattern recognition)，它應用在影像辨識，人臉辨識，語言辨識等的範圍，其中需要一個重要的技能就是將所要辦認的物件做分類，然後在該分類裡找出合適的對應結果．在這過程中，k-nearest neighbor (KNN) 是一種相對古老且直覺的方法．方法簡單而且能有高準確率，並且不需要所謂的 “訓練”．在人工智慧的領域裡，簡單而言，做的事情就是收集資料，然後依這些資料整理出一個數學模型，未來有新資料出現時，就可以丟入這數學模型加以運算，得出來的結果就是此模型的預測結果．KNN 這方法並不需要所謂的 “訓練” ，也就是說你並不需要從舊資料裡整理出一個數學模型．

KNN 利用資料本身所具備的一些 “自然” 特性來達成辨認的目的．在網路上能找到最常見用來說明 KNN 的範例就是房價． 房價的資料本身就是一個許多資訊的綜合結果，例如包含了環境好壞，面積大小，學區優劣，交通便利，文化觀點等等的因素所綜合起來的結果．想像一下，當你有一份房價資料，裡頭記錄了每一條街某一棟建築物的價格．當你用地圖的方式來呈現時，這在城市的地圖上你可以為已知道建築物標上價格標籤，然後還有許多的建築物尚未知道價格．即便你不懂房地產，當任意從城市的地圖上找到一棟建築物來猜測其價格時，你會怎麼做呢 ? 最簡單直覺的做法就是找附近類似條件的房價來做為參考價格．這也就是 KNN 所採用的概念．

在 KNN 的方法裡，K 是一個大於 0 的數字．以上述房價的例子來看，用來代表你要參考附近 (以距離來算) 多少個房價來做為預測新位置房價的對象．接下來，直接從 Wikipedia 上 KNN 例子的圖來做範例:



假設上圖是某個城市的房價分佈圖，用顏色來代表不同等級的房價．若採用 K=1 時的分類方法時，可以將地理區域劃出如下的區域:



這代表該區域內代表 KNN 方法在 K = 1 時所計算出來的房價．如果 K 值不同時，所得到的區域不會一樣．至於 K 值要取多少才能得到較好的預測結果，這需要更多對資料特性有實務經驗，才能找到適合的 K 值．因此，KNN 要用的好，除了找到一個適合算 “距離” 的公式外，還得對資料有許多實務經驗才行．

剛剛所談的算 “距離” 的公式，這是什麼呢 ? 以上述房價的例子而言，所謂的距離就是預測的房子與資料中最近房子的地理位置上的距離．你可以用直線距離或是真實道路距離來計算，完全依你的情境所需來決定．所以，不同的情況下，計算距離的方式是不一樣的．接下來舉個例子，車牌號碼的辨識已經在許多地方都派上用場了，例如高速公路收過路費，停車場進出入的車牌識別等．車牌識別用 KNN 的方法來進行，該怎麼做呢 ? 首先，我們的資料集合裡一定會有車牌會出現的所有符號，包含數字，英文字母或其他符號等．每一個符號都是一張圖案，而每一個符號在這圖案上所佔用的位置一定不一樣．如下圖是車牌數字的 7 :



當我們用一個 2D array 來代表 7 時，你可以把白色區域用 0 ，而黑色區域用 1，這樣一個 2D array 就可以表達出一個數字的 “長相” 了．會不會有其他的符號有一樣的長相呢 ? 在這個例子裡不會發生，因為每個符號都是不一樣，因此 2D array 裡的 0 ,1 也會不同．

接著，當一個欲辨識的符號進入時，我們怎麼算 “距離” 呢 ? 只要把欲辨識的符號用同樣的方式轉換成 2D array，然後再將這個 2D array 跟我們資料裡所有符號的 2D array 做一個 XOR 的運算 (或是檢查兩個值是否相等)．如下面簡單的程式碼 :



只要兩個 2D array 的某個元素不一樣時, diff 就會增加．卻辨識的符號會和所有的符號都進行一次算 “距離” 的運算，最後就選出 diff 最小的，那個就是我們找出的答案．

上述的方法是一個 K = 1 的 KNN 應用，我忽略了許多實作細節，但希望透過這樣簡單的說明能讓沒聽過 KNN 的朋友們知道 KNN 如何應用在車牌辨識上．如前面所說，透過 KNN 方法，我們不需要像 SVM (Support Vector Machine) , CNN (Convolutional Neural Networks) 那樣搞複雜的訓練模型過程就可以得到準確率還蠻高的結果．這樣說並不是說 KNN 比 SVM 或 CNN 強大，只是剛好在簡單的辨識情境裡 (如上述前的車牌辨識) KNN 在 K = 1 時能提供準確率相當高的結果，而且也不用事先訓練模型，也許這能算上是一種數學的奇蹟吧!

閱讀全文

#79 貪心策略 - Greedy (2)

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

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

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

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

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

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

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

Hope it helps,

閱讀全文

#78 貪心策略 - Greedy (1)

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

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

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

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

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

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

Hope it helps,

閱讀全文

#76 演算法裡一個基本的觀念 - Reduction

Reduction 是一個在演算法知識裡基本且簡單的觀念．其實在各位的工作中也一定常用到這觀念，只是你不知道而己．在這文章裡一如往昔，不用學術理論的描述方式，而是用平常寫程式的例子來讓非電腦科系畢業的資訊人了解什麼是 Reduction．

接下來用寫程式的角度來看什麼是 Reduction．假設你需要寫一個影像辨識的程式，這個程式需要辨識一個圖片裡是否含有某個數字，所以你寫的 function 可能會像下列:



以上的程式碼尚未完成，部份內容先暫以文字描述表示．你可能不是一個影像辨識的專家，完全不知道該怎麼做數字辨識．所以你一定會尋找可能的方法來執行這項任務．最後，你找到一個程式可以做這項工作，它的程式碼如下 (數字辨識的內容用文字描述代替):



由於 DetectNumber() 是別人完成的程式，假設你僅知道它是可用的，但無法了解其中的運作內容．你可以將它視為一個黑盒子．至於黑盒子裡面是怎麼運作的，由於能力與知識不及，所以暫時無法了解．但不了解也不代表不能使用，你只要知道這個黑盒子需要的輸入和輸出是什麼資料型別，就可以將它套用到你的程式裡．

接下來，我們將 DetectNumber() 套用到 ContainNumber() 裡面，所以完成後的 ContainNumber() 如下:



如此一來， ContainNumber() 就能做到它需要的功能了．從寫程式的角度來看，你會覺得這不就是每天工作在做的事情嗎 ? 是的，你每天寫程式所做的事情都是讓程式呼叫東呼叫西，在這一連串呼叫的過程完成自己所需要達成的功能．當一個演算法呼叫另外一個演算法來達成某項功能時，這就是一個 Reduction．也就是說，ContainNumber() 要做的事情，其實 DetectNumber() 也能做的到，差別只是輸入輸出的資料型別不同而己．將 ContainNumber() 的輸入型別轉換一下，就能形成 DetectNumber() 的輸入型別，然後將 DetectNumber() 的輸出型別轉換一下，就能變成 ContainNumber() 的輸出型別．再換個角度想，ContainNumber() 和 DetectNumber() 要處理的問題核心其實是同一個，只是問法和要求的答案有點小差別而己．在演算法的世界裡，某些問題的解法能變成另一些問題的解法，靠的就是這種 Reduction 的技巧．只要你能找出問題的本質是一樣時，解法就很接近了．

Hope it helps,

閱讀全文

#75 將問題和演算法分類

學習基礎的演算法過程中，許多課本最常用的方式是將問題分類好，然後對每一類問題進行討論並給出一些著名的演算法來解決這一類的問題．因此，要了解自己面對的問題屬於那一類型的問題便是件重要的課題．在這一系列的文章中，我的目的並不是要告訴你大學課程的演算法內容，而是希望用一種比較實際工作上會遇到的普遍情況來說明在工作中可能會碰到跟演算法課本內容有關係的課題．就像上一篇文章提過的，演算法的內容就像是你寫的程式裡某一個 function，每一個 function 一定有一個特定的目的．因此，你可以想像世界上存在許多的演算法，每一個演算法都有一個目的．當你認識了許多演算法時，有一個簡單的方法來分類演算法的種類，就是按照目的來分類．只要你知道你的問題是屬於那一類，這樣你就知道該去找那一類的演算法．例如，你的工作裡某一個任務需要將資料庫中的訂單做排序，因此，你就可以在市面上找到許多的排序演算法，挑一個適合用在你的工作裡．排序是一個相當簡單的例子，你甚至不用找演算法，因為這類基礎的演算法都已被實做在許多產品裡．另外一個例子，你的工作是做一個檢查文章裡的英文字是否拼錯，如果拼錯的話，必須列出一些建議清單來讓使用者選擇．這一類的演算法通常不會在一般的 class library 裡面內建好，因此你得自行尋找可用的演算法．這類的演算法比較像在算字和字之間的相似度，或稱為字和字之間的距離，如 nprth 是使用者誤打的字，可能正確的字是 north，因為 o , p 在鍵盤位置上就是隔壁而己．有一個演算法能幫你計算字和字之間的距離，請參考 https://en.wikipedia.org/wiki/Levenshtein_distance

透過上述的說明，你可以明白若進入一個自己不懂的領域，要針對該領域的問題找出適合的演算法來解決問題，這是需要花費時間學習．另外還有一個簡單的分類方式是用實做的方法來進行分類．例如，你的工作安排工廠裡產線的機器，每個機器會有不同的維修周期，不同種類的機器也會有不同的處理量，而產線上機器之間的順序是不會變的，就像一定得先把模具做出來，才能做各式機械加工處理，完成後才能噴塗料等等的程序．你老闆希望你能設計一個機器運作方式讓機器運作的情況是最佳的，也就是說產線的產量是最大的．像這樣看起來就是一個 “最佳化” 的問題，在演算法課本裡面會談到許多最佳化的問題．以這問題來說，採用 linear programming (未來文章會介紹) 是一個可能的解法之一．但要注意的是，並不是所有 “最佳化” 的問題都能用 linear programming 來找到最佳值，上述問題的限制給的很多，因此無形中幫你把問題的範圍縮小，解法也相對變簡單．如果問題的限制變少了，如加工製程的順序是不重要的，拿掉就個限制就讓整個問題變得很難用一個簡單的演算法找到最佳解，難的不是找不到答案，而是一旦問題的輸入量變大 (機器變多)，找出解答的時間 (演算法內的步驟) 就會以不成比例的方式往上增加，也就是說演算法的 Big O 變大．用寫程式的角度來看，一旦限制條件變少，程式就必須做更多的步驟來尋找各種可能以得到最佳值，這相當於 for loop 會變多了．Big O 漸漸變大時，此時你就得思考其他的解法方法，如果你的情境不需要最佳解，則採用一些近似解法來尋找接近最佳解的解答，而且通常近似值解法的速度都會比最佳值解法的速度來得快很多．

分類的情況實在太多了，無法一一描述．在這邊希望帶給非電腦科系畢業的資訊人一個觀念就是學習演算法的過程中，要先了解把問題分類，並且也知道一些常見問題分類裡一些著名的演算法．我們不需要發明什麼了不起的演算法，以我個人的經驗是，能夠善用許多聰明人為解決某些問題而想出來的演算法，這就已經夠利害了，同時也能幫助你寫出好程式．畢竟，對非本科畢業的資訊人來說，不是遇到一個不會的問題就用暴力法來解決．即便是一個看似很簡單的工作人員排班表的事情，用暴力法，它的 Big O 可是很大的．又比如你是做地圖導航的工程師，你要安排一個最短路徑從某一個點到另一個點，若沒有好的演算法，你能想像你用暴力法來解決，那將是什麼程度的 Big O 嗎 ?

最後，你可能會問，你明白分類的重要性，則到底有那些分類呢 ? 老實說，我回答不出來有那些分類．通常我的方法是看問題的資料輸入類型和問題的重點來決定．例如，問題是一個最佳化問題，例如找出成績最好的前十名學生，或是訂單金額最高的前十名，資料輸入類型是一個 List 或 Array，一堆資料庫來的訂單或學生清單，而問題的重點是在最佳解，像最大值，最小值，或某些子項目是符合某個條件，這一類的解法通常像之前一些 Coding面試文章的解法那樣．再困難一點，問題是一個觀光路徑排列的問題，資料輸入類型是一個 Tree 或 Graph，像一個地圖，而問題的重點是依照某個條件做排序，例如觀光景點參觀順序從低海拔排到高海拔，此時除了要了解基本的 Tree, Graph 的資料結構運作之外，最後還得讓排序演算法派上用場．不論怎麼分類，其實你都能感受到問題都是傾向某一種 “最佳” 的方向靠近，而且善用好的演算法就是希望結果能快速地被運算出來，也就是 Big O 盡可能低．如果問題不需要傾向某一種 “最佳” 的方向靠近，那麼程式隨便亂寫，最後能跑出答案就行了．

雖然每個演算法都有特定目的用來解決特定問題，不同的問題之間有可能用相同的演算法來解決嗎 ? 答案是有可能的，這是下一篇文章的重點．

Hope it helps,

閱讀全文

#74 演算法從零開始

資料結構和演算法算是最基礎而且重要的知識．若沒有這兩個科目的足夠知識的話是很難在其他電腦科學領域有所進步的，其中也包括程式設計這一條路．基本上來說，程式設計這條路需要強大的邏輯基礎，除了你得對 if .. else .. for loop 用的很熟練外，你還得了解你所用的 SDK, framework 的優缺點，這樣使用起來，你才知道你的 SDK, framework 為你的程式做了什麼事情．除此之外，你便需要知道資料結構和演算法的基本知識，這兩個學科是能幫助你寫出好程式的關鍵．

從前面的文章裡，我談了許多資料結構及其應用，也談了許多面試考題．當你看完那些文章後，你應該能抓到一個重點，這重點就是儘量地省時間 (省運算步驟)，不然的話，就得用空間來換時間 (提高空間複雜度來降低時間複雜度)．雖然每一種問題的情況都不一樣，不見得都能用空間換時間，但至少這是一個讓你思考的方向．演算法在這過程中扮演了重要角色，因為這門學問能幫助你辨別問題，知道什麼樣的問題 “應該” 要用什麼樣的解法．如果沒有好的解法時，也可以得到盡可能好的解法．

你可能會覺得，有這麼神奇嗎? 基本上是的，大學裡學的演算法只是一個開始，並不是包山包海．這門學問可幫助我們辨別問題，同時提供好的解法．許多特定領域的問題，如人工智慧，資料庫等領域，都是需要演算法的基礎知識才能繼續在該領域裡研究和學習．常常也會發現類似的演算法或想法被用在不同的系統中．例如，資料庫常用 B-tree 來幫助快速搜尋資料，相同的做法也能放在作業系統中用來快速尋找檔案．這是典型的用空間換時間的做法，同時也是演算法中 Divide & Conqure 的概念．

說了這一些，到底演算法是什麼 ? 在演算法的課本裡你可以找到正式的學術說明來定義什麼是演算法．以下是我用不學術的方式來簡單定義演算法: 演算法是一連串的運算，這運算會有輸入端 (你的問題)，然後會有輸出端 (問題的答案)．演算法也可以視為一段程式碼，既然是一段程式碼，之前在資料結構裡提到的空間複雜度和時間複雜度也同樣適合在這裡做分析用途．但有一個重點，演算法裡這一連串的運算應該是有盡頭的，也就是能夠跑的完，而不是一直無窮迴圈跑下去．所以，每個演算法的目的就是解決問題 (輸入端)，然後產生解答 (輸出端)．如果用你工作上的專案來看的話，在你程式裡的大部份的 method 都是一個演算法，因為這些 method 都接收輸入然後產生輸出，這些都是在你專案裡用來解決特定的問題或是達成特定的目標．

當你看到這裡時，你可能會認為演算法就像是一般的程式一樣，這樣想也沒什麼不可．但為什麼演算法常給人一種好像是個高深學問或是很難的感覺，我只能說你可能從網路上看到的先進應用都是需要特別的演算法，這些特別演算法不是那麼容易可以想的出來的，自然而然給你一些既定印象認為演算法好像很難．如前面所提的，大學課程裡面教的演算法並非是為了解決特定問題，而是把世界上常見的問題做分類，並且介紹每一個分類裡一些著名的演算法用來解決這些問題．

把這篇文章做為介紹演算法的第一篇文章，正式開啟演算法之路．

閱讀全文