Search Techniques

搜索方式

譯 by Lucky Craz

樣例: n 皇后問題 [經典問題]

將 n 個皇后擺放在一個 n x n 的棋盤上，使得每一個皇后都無法攻擊到其他皇后。

深度優先搜索 (DFS)

顯而易見，最直接的方法就是把皇后一個一個地擺放在棋盤上的合法位置上，枚舉所有可能尋找可行解。可以發現在棋盤上的每一行（或列）都存在且僅存在一個皇后，所以，在遞歸的每一步中，只需要在當前行(或列）中尋找合法格，選擇其中一個格擺放一個皇后。

 1 search(col)
 2     if filled all columns
 3         print solution and exit 

 4   for each row
 5       if board(row, col) is not attacked
 6            place queen at (row, col)
 7            search(col+1)
 8            remove queen at (row, col)

從search(0)開始搜索，由于在每一步中可選擇的節點較少，該方法可以較快地求解：當一定數量的皇后被擺放在棋盤上后那些不會被攻擊到的節點的數量將迅速減少。

這是深度優先搜索的一個經典例題，該算法總是能盡可能快地抵達搜索樹的底層：當 k 個皇后被擺放到棋盤上時，可以馬上確定如何在棋盤上擺放下一個皇后，而不需要去考慮其他的順序擺放皇后可能造成的影響（如當前情況是否為最優情況），該方法有時可以在找到可行解之前避免復雜的計算，這是十分值得的。

深度優先搜索具有一些特性，考慮下圖的搜索樹：



該算法用逐步加層的方法搜索并且適當時回溯，在每一個已被訪問過的節點上標號，以便下次回溯時不會再次被搜索。繪畫般地，搜索樹將以如下順序被遍歷：



復雜度：

假設搜索樹有 d 層（在樣例中 d=n ，即棋盤的列數）。再假設每一個節點都有 c 個子節點（在樣例中，同樣 c=n ，即棋盤的行數，但最后一層沒有子節點，除外）。那么整個搜索花去的時間將與 cd 成正比，是指數級的。但是其需要的空間較小，除了搜索樹以外，僅需要用一個棧存儲當前路徑所經過的節點，其空間復雜度為 O(d) 。

樣例：騎士覆蓋問題[經典問題]

在一個 n x n 的棋盤中擺放盡量少的騎士，使得棋盤的每一格都會被至少一個騎士攻擊到。但騎士無法攻擊到它自己站的位置.

廣度優先搜索 (BFS)

在這里，最好的方法莫過于先確定 k 個騎士能否實現后再嘗試 k+1 個騎士，這就叫廣度優先搜索。通常，廣度優先搜索需用隊列來幫助實現。

 1 process(state)
 2     for each possible next state from this one
 3         enqueue next state 

 4 search()
 5     enqueue initial state
 6     while !empty(queue)
 7         state = get state from queue
 8         process(state)

廣度優先搜索得名于它的實現方式：每次都先將搜索樹某一層的所有節點全部訪問完畢后再訪問下一層, 再利用先前的那顆搜索樹，廣度優先搜索以如下順序遍歷：



首先訪問根節點，而后是搜索樹第一層的所有節點，之后第二層、第三層厖以此類推。

復雜度：

廣度優先搜索所需的空間與深度優先搜索所需的不同（ n 皇后問題的空間復雜度為 O(n) ）,廣度優先搜索的空間復雜取決于每層的節點數。如果搜索樹有 k 層，每個節點有 c 個子節點，那么最后將可能有 c k 個數據被存入隊列，這個復雜度無疑是巨大的。所以在使用廣度優先搜索時，應小心處理空間問題。

迭代加深搜索 (ID)

廣度優先搜索可以用迭代加深搜索代替。迭代加深搜索實質是限定下界的深度優先搜索，即首先允許深度優先搜索搜索 k 層搜索樹，若沒有發現可行解，再將 k+1 后再進行一次以上步驟，直到搜索到可行解。這個?#27169;仿廣度優先搜索?#25628;索法比起廣搜是犧牲了時間，但節約了空間。

 1 truncated_dfsearch(hnextpos, depth)
 2     if board is covered
 3         print solution and exit 

 4     if depth == 0
 5         return 

 6     for i from nextpos to n*n
 7         put knight at i
 8         truncated_dfsearch(i+1, depth-1)
 9         remove knight at i 

10 dfid_search
11     for depth = 0 to max_depth
12        truncated_dfsearch(0, depth)

復雜度：

　

ID時間復雜度與DFS的時間復雜度（O(n)）不同，另一方面，它要更復雜，某次DFS若限界 k 層，則耗時 ck 。若搜索樹共有 d 層，則一個完整的DFS-ID將耗時 c0 + c1 + c2 + ... + cd 。如果 c = 2 ，那么式子的和是 cd+1 - 1 ，大約是同效BFS的兩倍。當 c > 2 時（子節點的數目大于2），差距將變小：ID的時間消耗不可能大于同效BFS的兩倍。所以，但數據較大時，ID-DFS并不比BFS慢，但是空間復雜度卻與DFS相同，比BFS小得多。

算法選擇：

當你已經知道某題是一道搜索題，那么選擇正確的搜索方式是十分重要的。下面給你一些選擇的依據。

簡表：
搜索方式 時間 空間 使用情況
DFS O(c k) O(k) 必須遍歷整棵樹，要求出解的深度或經的過節點，或者你并不需要解的深度最小。
BFS O(c d ) O(c d ) 了解到解十分靠近根節點，或者你需要解的深度最小。
DFS+ID O(c d) O(d) 需要做BFS，但沒有足夠的空間，時間卻很充裕。
d ：解的深度
k ：搜索樹的深度
d <= k

記住每一種搜索法的優勢。如果要求求出最接近根節點的解，則使用BFD或ID。而如果是其他的情況，DFS是一種很好的搜索方式。如果沒有足夠的時間搜出所有解。那么使用的方法應最容易搜出可行解，如果答案可能離根節點較近，那么就應該用BFS或ID，相反，如果答案離根節點較遠，那么使用DFS較好。還有，請仔細小心空間的限制。如果空間不足以讓你使用BFS，那么請使用迭代加深吧！

類似問題：

超級質數肋骨[USACO 1994 決賽]

一個數，如果它從右到左的一位、兩位直到N位（N是）所構成的數都是質數，那么它就稱為超級質數。例如：233、23、2都是質數，所以233是超級質數。要求：讀入一個數N（N <=  9），編程輸出所有有N位的超級質數。

這題應使用DFS，因為每一個答案都有N層（最底層），所以DFS是最好的．

Betsy的旅行 [USACO 1995 資格賽]

一個正方形的小鎮被分成 NxN (2 <= N <= 6）個小方格，Besty 要從左上角的方格到達左下角的方格，并且經過每一次方格都恰好經過一次。編程對于給定的 N 計算出 Besty 能采用的所有的旅行路線的數目。

這題要求求出解的數量，所以整顆搜索樹都必須被遍歷，這就與可行解的位置與出解速度沒有關系了。所以這題可以使用BFS或DFS，又因為DFS需要的空間較少，所以DFS是較好的．

奶牛運輸 [USACO 1995 決賽]

奶牛運輸公司擁有一輛運輸卡車與牧場 A ，運輸公司的任務是在A，B，C，D，E，F和G七個農場之間運輸奶牛。每兩個農場之間的路程（可以用floyed改變）已給出。每天早晨，運輸公司都必須確定一條運輸路線，使得運輸的總距離最短。但必須遵守以下規則：

  • 農場 A 是公司的基地。每天的運輸都必須從這開始并且在這結束。
  • 卡車任何時刻都只能最多承載一頭奶牛。
  • 給出的數據是奶牛的原先位置與運輸結束后奶牛所在的位置。

而你的任務是在上述規則內尋找最短的運輸路線。

在發現最優解時必須比較所有可行解，所以必須遍歷整棵搜索樹。所以，可以用DFS解題．

橫越沙漠 [1992 IOI]

一群沙漠探險者正嘗試著讓他們中的一部分人橫渡沙漠。每一個探險者可以攜帶一定數量的水，同時他們每天也要喝掉一定量的水。已知每個探險者可攜帶的水量與每天需要的水量都不同。給出每個探險者能攜帶的水量與需要的水量與橫渡沙漠所需的天數，請編程求出最多能有幾個人能橫渡沙漠。所有探險者都必須存活，所以有些探險者在中途必須返回，返回時也必須攜帶足夠的水。當然，如果一個探險者返回時有剩余的水（除去返回所需的水以外），他可以把剩余的水送給他的一個同伴，如果它的同伴可以攜帶的話。

這題可以分成兩個小問題，一個是如何為探險者分組，另一個是某些探險者應在何處返回。所以使用ID-DFS是可行的。首先嘗試每一個探險者能否獨自橫渡，然后是兩個人配合，三個人配合。直到結束。