搜索方式

譯 by Lucky Craz

樣例: n 皇后問題 [經(jīng)典問題]

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

深度優(yōu)先搜索 (DFS)

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

 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)開始搜索，由于在每一步中可選擇的節(jié)點較少，該方法可以較快地求解：當一定數(shù)量的皇后被擺放在棋盤上后那些不會被攻擊到的節(jié)點的數(shù)量將迅速減少。

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

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

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

復雜度：

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

樣例：騎士覆蓋問題[經(jīng)典問題]

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

廣度優(yōu)先搜索 (BFS)

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

 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)

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

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

復雜度：

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

迭代加深搜索 (ID)

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

 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 層，則耗時 c^k 。若搜索樹共有 d 層，則一個完整的DFS-ID將耗時 c⁰ + c¹ + c² + ... + c^d 。如果 c = 2 ，那么式子的和是 c^d+1 - 1 ，大約是同效BFS的兩倍。當 c > 2 時（子節(jié)點的數(shù)目大于2），差距將變小：ID的時間消耗不可能大于同效BFS的兩倍。所以，但數(shù)據(jù)較大時，ID-DFS并不比BFS慢，但是空間復雜度卻與DFS相同，比BFS小得多。

算法選擇：

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

簡表：

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

類似問題：

超級質(zhì)數(shù)肋骨[USACO 1994 決賽]

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

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

Betsy的旅行 [USACO 1995 資格賽]

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

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

奶牛運輸 [USACO 1995 決賽]

奶牛運輸公司擁有一輛運輸卡車與牧場 A ，運輸公司的任務是在A，B，C，D，E，F(xiàn)和G七個農(nóng)場之間運輸奶牛。每兩個農(nóng)場之間的路程（可以用floyed改變）已給出。每天早晨，運輸公司都必須確定一條運輸路線，使得運輸?shù)目偩嚯x最短。但必須遵守以下規(guī)則：

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

而你的任務是在上述規(guī)則內(nèi)尋找最短的運輸路線。

在發(fā)現(xiàn)最優(yōu)解時必須比較所有可行解，所以必須遍歷整棵搜索樹。所以，可以用DFS解題．

橫越沙漠 [1992 IOI]

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

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