搜尋演算法 Search Algorithm
搜尋演算法在很多地方都能應用, 在這個主題會提到的搜尋演算法有五種:
- Depth-first search (DFS) 深度優先搜尋法
- Depth-limited search (DLS) 深度限制搜尋法
- Iterative deepening search (IDS) 加深式搜尋法
- Breadth-first search (BFS) 廣度優先搜尋法
- A* search A*搜尋法
首先來看一個Tree，這個Tree將用來做整個主題的範例。
- 樹根：Root，就是上圖的A，也就是樹的最起始位置。資訊科學裡的樹很少有根長在下面的，都是倒著長的比 較多，習慣就好。
- 節點：也就是node，上面那棵樹的每一個泡泡就是一個節點，有時候就只寫「點」囉，打太多字手很痠的。
- 中間點：Internal node，也就是A、B、C、D、E、F、G、I與K；什麼意思呢？如果有一個泡泡，它的底下還連著 一個以上的泡泡，底下的泡泡叫做子節點（Child node），那麼有孩子的泡泡就叫做父節點（Parent node）。
- 樹葉：也就是沒孩子的點啦，即J、O、L、M、H和N。
- 展開：也就是一個節點「發現自己孩子」的動作，例如我們說「把A展開」，就是指B、C與D被「看到了」； 這裡有個觀念要先清楚，搜尋時，我們要當做自己從最開始的地方開始去「找」，也就是我們除了自己目前站的 點之外，我們是「看不見未來的點」的，所以如果記者目前位置在A，我們要當做沒看到B、C與D，除非進行一次 「展開」的動作。
- 返回：樹的箭號一直往下，表示方向是往下嘛，如果現在要回頭，就是返回囉，例如J->E就是一次返回。
- 深度：Depth，樹根的地方是第0層，然後往下是第1層，以此類推。不管最下面的點有幾個，只要有泡泡存在 ，深度照算，所以上圖的深度是4。
Depth-first search 深度優先搜尋法
深度優先搜尋法的基本精神，就是不管橫的，只管直的，一股腦的往下找，找不到再回頭旁邊的路，所以叫深
度優先。舉個例子就懂了：
我們現在的位置是A，看一下A是不是我們要找的，如果不是，就把A展開，然後看到有三個點B、C與D。
這個時候，我們先把C與D放著不管（不檢查是不是我們要的），看看B是不是我們要的，若B也不是，
就再把B給展開，然後發現E與F。
這時F還是一樣放著不看，然後檢查E，若E也不是，就把E展開，看到J。
檢查J是不是我們要的答案。如果J不是呢？這時就要回頭啦，從J回頭後，看到E。
E除了J這個孩子外，也沒別的了，所以只好再返回一次，回到B。
B的另一個兒子F我們還沒檢查過，這時檢查F是不是答案。
若F還不是我們要的，就再往下走，看到K。
檢查K，依然不是？那就展開K，看到O。
檢查O，如果這時O也不是答案呢？再返回，發現K沒別的孩子了，再返回，F也沒有別的孩子，只好再返回
到B。
可是B也沒別的兒子了，只好再返回到A。
A的孩子剛才看到了有B、C與D，這時B的孩子們都走完了，就從C開始走，重覆剛才的觀念，一直到走到N為止。
如果一直都找不到我們要的解答，就宣告失敗。
所以整棵樹的走法就是A->B->E->J->F->K->O->C->G->L->M->D->H->I->N
DFS的好處在那裡？好處是在走的時候，我們只要「記住目前路徑的點」即可，假設我們現在從A走到J，我們 只需記往ABCDEF即可（J是要處理的點，不用記），較正式的說法是，若這棵樹的分支數是b（以二元樹來說，b=2，但是以上圖來看，我 們假設b=3），目的地的深度是d，則我們需要記住的點的數目是bd，J在第3層，所以是3×3=9，意思是 最多不會超過9個點。然而，時間上倒是和其它的搜尋法沒什麼分別，最慘最慘就是整棵樹找完嘛，也就是最多 要找bd個點。
DFS被視為非Complete，也就是即使答案存在，它也不一定找的到答案，聽起來很玄嗎？找不到答案是因為 無窮路徑的問題。樹是圖(Graph)的一種，我們必須回到比較廣的定義去看。想像一下，如果J的下面畫個箭頭 指到B去，那麼會變成什麼樣子？A->B->E->J->B->E->J->B...永遠不會停，也永遠不會去走其它的路了！所以 說DFS是非Complete的。
還有一個是Optimal的問題，就是DFS能不能保證能找到最佳解？答案是不能的，因為它笨笨的一直往下挖， 就算答案在它隔壁，它也要挖完這一條路以後返回才知道。
Worst case分析：
Time complexity: O(bd) d: depth, b: number of branches
Space complexity: O(bd)
Complete: No
Optimal: No
Mick's pseudocode
每個新的node都是由特定的operator所「產生(generate)」的，因為在面對未知的問題時，我們不知道現在的 點的孩子長什麼樣子，上面的圖是假設我們都知道點長什麼樣子了，但是我們在設計程式時，是不會知道的。 所以，我們要這樣想，B、C與D是由A「generate」出來的，怎麼去generate呢？就是執行某些特定的operator， 舉個例子好了，把operator想像成「往上走」、「往下走」、「往左走」、「往右走」，這四個operator會 generate四個新的節點，這樣子懂了嗎？所以前面說的「展開」也是這個意思，本來一個點，變成四個點，當然 叫做展開囉。