本質(zhì)上所有的人工智能程序都使用某種形式的搜索來找到想要的結(jié)果。事實上，人工智能的一個領域?qū)ｉT研究不同的搜索算法。抽象地看，所有的搜索算法都是在探索一個具有不同的可能狀態(tài)的空間，以找到一些能夠滿足搜索目標的狀態(tài)。舉例來說，在一個下國際象棋的程序中，一個狀態(tài)就表示下棋過程中的第一個棋盤局面。而目標就是要找到一個狀態(tài)，使得下棋程序能夠?qū)κ謱⑺?。要搜索一個贏的狀態(tài)，程序要使用一種轉(zhuǎn)換函數(shù)，根據(jù)輸入的一個狀態(tài)生成另一個狀態(tài)。在下棋的程序中，這個轉(zhuǎn)換函數(shù)可以定義為棋子的移動。給定一個狀態(tài)，程序根據(jù)一個可能的移動計算出一個新的狀態(tài)。典型地，程序需要根據(jù)所有可能的移動來考慮產(chǎn)生的狀態(tài)集合。這些狀態(tài)被稱為后繼狀態(tài)。

國際象棋是一種非常復雜的游戲，會產(chǎn)生相當復雜的搜索空間。這里，我們先討論一個非常簡單的例子。假設你想找到一個朋友的密碼鎖的數(shù)字組合。你可以隨機地嘗試各種組合并且希望有好運氣，但是如果你想要系統(tǒng)地考慮所有的可能，則應該決定一種專門的搜索策略。我們可以按照下面的方式將這個問題形式化為一個狀態(tài)空間搜索問題。這里，“狀態(tài)”表示你已經(jīng)處理過的數(shù)字的一個列表。當你撥另一個數(shù)字時，就完成了一次“移動”，并產(chǎn)生了一個新的狀態(tài)，表現(xiàn)為在原來的狀態(tài)尾部加入這個新的數(shù)字。假設我們并不知道需要撥多少數(shù)字。為了使這個例子保持在可控制的范圍內(nèi)，我們還假設密碼鎖只有兩個數(shù)字1和2。圖B.1給出了涉及最多3個數(shù)字的狀態(tài)空間。從初始狀態(tài)()開始，我們撥數(shù)字1或者2，這樣就有了兩個后繼狀態(tài)(1)和(2)，如圖所示。從這兩個狀態(tài)開始，我們可以撥第二個數(shù)字，這樣每個狀態(tài)又有兩個后繼狀態(tài)，這樣一直繼續(xù)下去。很多搜索策略的研究都可以在一個一般性的框架下進行，這個框架需要維護一個還需要嘗試的狀態(tài)列表。假設TODO就是一個你需要考慮的狀態(tài)列表。

圖B.1簡單密碼鎖的搜索空間

1. 將TODO初始化為僅包含初始狀態(tài)的(())的列表；

2. 重復下面的操作直至找到目標狀態(tài)：

   2.1 從TODO中移出一個狀態(tài)；

   2.2 檢查它是否是目標狀態(tài)（是否能開鎖?）；

   2.3 如果不能，生成所有后繼狀態(tài)，并將其加入到TODO列表中。

根據(jù)選擇下一個要處理的狀態(tài)的策略的不同，產(chǎn)生了不同的搜索策略。有兩種基本的策略。第一種是深度優(yōu)先策略，使用一個棧作為TODO列表。這樣，它總是選擇最后一個加到棧中的狀態(tài)做進一步的處理。考慮在密碼鎖問題的處理中采用這種策略，假設實際的組合是（211)。一開始，TOD0中只有初始狀態(tài)()。兩個后繼狀態(tài)被加入到列表中，也就是(1)和(2)。加入這兩個狀態(tài)后，TOD0值為((1)(2))。下一步選擇狀態(tài)(1)。發(fā)現(xiàn)它不是目標狀態(tài)（也就是說，它不能開鎖），因此兩個后繼狀態(tài)，(11)和(12)，產(chǎn)生并加到了TOD0列表中，這時TOD0列表變成了((11)(12)(2))。下面選擇狀態(tài)(11)，發(fā)現(xiàn)鎖依然無法打開后，兩個后繼狀態(tài)(111)和(112)產(chǎn)生出來，并被加入到TOD0列表中，這時TOD0列表變成了((111)(112)(12)(2))。知道(111)不是密碼后，后繼狀態(tài)(1111)和(1112)被加入到TOD0列表中?，F(xiàn)在你也許注意到了，除非給這個算法規(guī)定一個需要產(chǎn)生的數(shù)字位數(shù)的上限，否則這個策略永遠不會找到答案。

另外一種基本的策略稱為廣度優(yōu)先搜索，將TOD0當做隊列而不是棧。這樣，后繼狀態(tài)被添加到TOD0列表的末尾。還是從狀態(tài)()開始，TOD0列表在算法運行過程中依次取下面這些值：

((1)(2)）

((2)(1 1)(1 2))

((1 1)(1 2)(21)(2 2))

((12)(2 1)(22)(11 1)(1 12))

((21)(22)(111)(112)(121)(122))

等等

可以看到這兩種策略以很不一樣的順序探索這個空間。如果在圖B.1所示的表示這個搜索空間的樹中依據(jù)這兩種策略來跟蹤搜索到的狀態(tài)，會看到深度優(yōu)先策略在這棵樹上快速向下移動，不斷地在更深的層次上探索狀態(tài)。另一方面，廣度優(yōu)先策略總是系統(tǒng)地探索樹的某一個層次上所有可能的狀態(tài)，然后才考慮下一個層次的狀態(tài)。

對于有限的搜索空間[舉例來說，我們可以指定密碼最多只有4位，因此類似(1111)的狀態(tài)就沒有后繼狀態(tài)]，通常深度優(yōu)先策略會更快地找到答案。不過，對于無限的搜索空間，就像對于不限長度的密碼鎖問題一樣，深度優(yōu)先策略不能保證會找到答案，因為它可能會沿著一條具有無限后繼狀態(tài)但又不包含答案的鏈搜索下去。廣度優(yōu)先策略可以保證如果存在一個答案就一定能夠找到。

很多其他搜索策略也是可能的。一種稱為迭代深化的策略類似于深度優(yōu)先策略，不過它在到達一個特定的深度后就會停下來。如果在特定的深度上沒有找到答案，它就增加深度并重復上述操作。雖然這會導致重復勞動，不過人們發(fā)現(xiàn)它總體上要好于純粹的深度優(yōu)先或廣度優(yōu)先策略。作為選擇，你也可以使用啟發(fā)式搜索，這種策略采用某種啟發(fā)式信息來選擇下一個狀態(tài)。舉例來說，如果你認為不包含相同數(shù)字反復出現(xiàn)的序列更有可能是密碼，你也許總是盡可能選擇一個不包含重復數(shù)字的狀態(tài)，只有在不存在這種狀態(tài)時才考慮其他的可能性。你可能將包含重復數(shù)字的狀態(tài)加入到TOD0列表的末尾，而將其他狀態(tài)加入到前面。

((1)（2))

((1 2)(2)(1 1))

((121)(2)(11)(122))

等等

啟發(fā)式搜索的一種一般化的形式描述稱為最佳優(yōu)先搜索。這種策略使用一個函數(shù)，為每一個狀態(tài)返回一個啟發(fā)式的值。在搜索的每一步，你都選擇值最高的狀態(tài)。

責任編輯：admin