#94 演算法的 Backtracking 策略

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

閱讀全文

#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 裡最大的區間總和. 要解決這個問題其實不難，因為用最直接的暴力法就可以解決了，其程式結構如下: ...

閱讀全文

#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...

閱讀全文

#86 貪心方法是最佳解 ?

最佳解? 這種解答是許多問題所追尋的目標．例如，在一個城市裡找到出發點和目的地的最短距離．直覺來看，若你沒有把所有可能的路徑列出來，你怎麼知道那一個才是最短的．再舉例一個例子，在一個 int array 裡面，找出最大值的元素位置．若你沒把所有的元素都拜訪一遍，你怎知道那一個才是最大的．這兩個例子雖然都是在找 "最佳解"，但是解法的思考卻不太一樣．第二個例子的思考是 "一條路"，而第一個例子是 "多條絡"．在 "一條路" 的情況下，對下一個步驟來說沒什麼好選擇的，只能一直往前走．然而，"多條路"的情況下，在什麼路口選擇什麼路，這對答案或執行過程會有很大的影響． 前面已有兩篇文章簡單地介紹了貪心方法．這篇文章要討論的是利用貪心方法得到的解答會是最佳解嗎 ? 用一個簡單的問題來測試．假設郵局提供的郵票面值如下:$10,...

閱讀全文

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

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

閱讀全文

#79 貪心策略 - Greedy (2)

上一篇文章談了貪心策略的基本想法，但並沒有提到任何的程式碼來說明貪心策略是怎麼進行的．其實貪心策略並沒有一個很明顯程式碼撰寫方式，如果硬是要湊出一個程式碼外型的話，我覺得它的長相可能如下: while ( 依問題條件來決定是否要繼續下一步 ) { // 1. 依照問題，在這一個步驟裡取得最佳解 // 2. 根據步驟一得到的最佳解來決定程式的下一個狀態 // 3. 將程式目前的狀態移動到下一個狀態，下一個狀態將會更接近最終的答案 } 老鼠走迷宮是很典型資料結構 Stack 作業，它的內容是假設一個方形的土地，這土地用畫分成許多面積相等的小格子，就像棋盤那樣．每一個格子都是一種地形，如山，河，平地．老鼠只能走平地，不能爬山也不能過河．老鼠將從起點走到終點，起點是在這土地的左上角，而終點是在右下角．這個作業就是要讓老鼠能走出一條路從起點到終點．如果沒有路存在，則最後的答案是...

閱讀全文

#78 貪心策略 - Greedy (1)

前面的文章曾提過，在這世界上有很多不同類型的問題，基本上我們太不可能找到一個方法來解決所有的問題．所以，不同類型的問題就會有不同的解法．有的解法很好理解並且單純，有的解法不易理解．解法本身並沒有所謂的好壞，只有適不適合使用的情況．通常來說，難的問題若要有好的執行結果，通常那個解法不見得簡單，就算是簡單，也絕非容易可以想的出來．這也許就是演算法美妙的地方，或許可以說是邏輯之美．廣泛地也可以說成是數學之美，都是宇宙空間裡所擁有的一些特質． 今天要提的解法是一種貪心 (Greedy) 的 “精神”．若你沒念過演算法這門課，恭喜你可以免除這個宇由特質的迫害，可以遠離那種整晚埋頭寫作業的崩潰時光．我想我是比較笨的，所以我以前寫演算法和計算理論的作業時，常常抱著頭在燒．如今，回頭看看，這些都是人生裡蠻有趣且值得回憶的時光．演算法課本裡，前面一半的內容中主要是提到一般市面上對問題的...

閱讀全文

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

Reduction 是一個在演算法知識裡基本且簡單的觀念．其實在各位的工作中也一定常用到這觀念，只是你不知道而己．在這文章裡一如往昔，不用學術理論的描述方式，而是用平常寫程式的例子來讓非電腦科系畢業的資訊人了解什麼是 Reduction． 接下來用寫程式的角度來看什麼是 Reduction．假設你需要寫一個影像辨識的程式，這個程式需要辨識一個圖片裡是否含有某個數字，所以你寫的 function 可能會像下列: This file contains bidirectional Unicode text that may be interpreted...

閱讀全文

#75 將問題和演算法分類

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

閱讀全文

#74 演算法從零開始

資料結構和演算法算是最基礎而且重要的知識．若沒有這兩個科目的足夠知識的話是很難在其他電腦科學領域有所進步的，其中也包括程式設計這一條路．基本上來說，程式設計這條路需要強大的邏輯基礎，除了你得對 if .. else .. for loop 用的很熟練外，你還得了解你所用的 SDK, framework 的優缺點，這樣使用起來，你才知道你的 SDK, framework 為你的程式做了什麼事情．除此之外，你便需要知道資料結構和演算法的基本知識，這兩個學科是能幫助你寫出好程式的關鍵． 從前面的文章裡，我談了許多資料結構及其應用，也談了許多面試考題．當你看完那些文章後，你應該能抓到一個重點，這重點就是儘量地省時間 (省運算步驟)，不然的話，就得用空間來換時間 (提高空間複雜度來降低時間複雜度)．雖然每一種問題的情況都不一樣，不見得都能用空間換時間，但至少這是一個讓你思考的方向．演算法在這過程中扮演了重要角色，因為這門學問能幫助你辨別問題，知道什麼樣的問題...

閱讀全文