搬運工問題的啟示重慶外語學(xué)校劉汝佳-狀態(tài)空間搜尋基本學(xué)問.狀態(tài)空間(statespace)對于一個實際的問題，我們可以把它進行肯定的抽象。通俗的說，狀態(tài)(state)是對問題在某一時刻的進展?fàn)顩r的數(shù)學(xué)描述，狀態(tài)轉(zhuǎn)移(state-transition)就是問題從一種狀態(tài)轉(zhuǎn)移到另一種(或幾種)狀態(tài)的操作。假如只有一個智能體(Agent)可以實施這種狀態(tài)轉(zhuǎn)移，則我們的目的是單一的，也就是從確定的起始狀態(tài)(startstate)經(jīng)過一系列狀態(tài)轉(zhuǎn)移而到達一個(或多個)目標(biāo)狀態(tài)(goalstate)假如不止一個智能體可以操縱狀態(tài)轉(zhuǎn)移(例如下棋)，那么它們可能會朝不同的，甚至是對立的目標(biāo)進行狀態(tài)轉(zhuǎn)移。這樣的題目不在本文爭論范圍之內(nèi)。我們知道，搜尋的過程實際是在遍歷一個隱式圖，它的結(jié)點是全部的狀態(tài)，有向邊對應(yīng)于狀態(tài)轉(zhuǎn)移。一個可行解就是一條從起始結(jié)點動身到目標(biāo)狀態(tài)集中任意一個結(jié)點的路徑。這個圖稱為狀態(tài)空間(statespace),這樣的搜尋就是狀態(tài)空間搜尋(Single-AgentSearch).盲目搜尋(UninformedSearch)盲目搜尋主要包括以下幾種：純隨機搜尋(RandomGenerationandRandomWalk)聽起來比較“傻”，但是當(dāng)深度很大，可行解比較多，解的深度又不重要的時候還是有用的，而且改進后的隨機搜尋可以應(yīng)付解分布比較有規(guī)律(相對密集或平均，或按黃金分割比例分布等)的題目。一個典型的例子是：你在慌亂中找東西的時候，往往都是進行隨機搜尋。廣度優(yōu)先搜尋(BFS)和深度優(yōu)先搜尋(DFS)大家都很熟識它們的時間效率，空間效率和特點了吧。廣度優(yōu)先搜尋的例子是你的眼鏡掉在地上以后，你趴在地板上找：)-你總是先摸最接近你的地方，假如沒有，在摸遠一點的地方…深度優(yōu)先搜尋的典型例子是走迷宮。它們還有逆向和雙向的搜尋方式，但是不再本文爭論范圍之內(nèi)。重復(fù)式搜尋這些搜尋通過對搜尋樹擴展式做一些限制，用逐步放寬條件的方式進行重復(fù)搜尋。這些方法包括：重復(fù)式深度優(yōu)先(IterativeDeepening)限制搜尋樹的最大深度Dmax,然后進行搜尋。假如沒有解就加大Dmax再搜尋。雖然這樣進行了許多重復(fù)工作，但是由于搜尋的工作量與深度成指數(shù)關(guān)系，因此上一次(重復(fù)的)工作量比起當(dāng)前的搜尋量來是比較小的。這種方法適合搜尋樹總的來說又寬又深，但是可行解卻不是很深的題目(一般的深度優(yōu)先可能陷入很深的又沒有解的地方，廣度優(yōu)先的話空間又不夠)重復(fù)式廣度優(yōu)先(IterativeBroadening)它限制的是從一個結(jié)點擴展出來的子節(jié)點的最大值Bmax,但是由于優(yōu)點不是很明顯，應(yīng)用并不多，爭論得也比較少。柱型搜尋(BeamSearch)它限制的是每層搜尋樹節(jié)點總數(shù)的最大值Wmax。明顯這樣搜尋樹大小與深度成正比，但是可能錯過很接近起點的解，而增加Wmax的時候保留哪些節(jié)點,Wmax增加多少是當(dāng)前正在爭論的問題。.啟發(fā)式搜尋(InformedSearch)我們覺得一些問題很有“想頭”，主要是由于啟發(fā)信息比較多，思索起來簡潔入手，但是卻不簡潔找到解。我們不情愿手工一個一個盲目的試驗，同樣也不情愿我們的程序機械的搜尋。也就是說,我們盼望盡可能的挖掘題目自身的特點,讓搜尋智能化。下面介紹的啟發(fā)式搜尋就是這樣的一種智能化搜尋方法。在剛才的那些算法中，我們沒有采用狀態(tài)本身的信息，只是采用了狀態(tài)轉(zhuǎn)移來進行搜尋。事實上，我們自己在解決問題的時候經(jīng)常會估量狀態(tài)離目標(biāo)究竟有多接近，進而對多種方案進行選擇。把這種方法用到搜尋中來，我們可以用一個狀態(tài)的估價函數(shù)來估量它到目標(biāo)狀態(tài)的距離。這個估價函數(shù)是和問題息息相關(guān)的，體現(xiàn)了肯定的智能。為了以后敘述便利，我們先介紹一些記號：S問題的任何一種狀態(tài)H*(s)s到目標(biāo)的實際(最短)距離-惋惜事先不知道：)H(s)S的啟發(fā)函數(shù)-S到目標(biāo)距離的下界,也就是h(s)<=h*(s),假如h函數(shù)對任意狀態(tài)si和s2,還滿意h(sl)v=h(s2)+c(sl,s2)(其中c(sl,s2)代表狀態(tài)si轉(zhuǎn)移到s2的代價)，也就是狀態(tài)轉(zhuǎn)移時，下界h的削減值最多等于狀態(tài)轉(zhuǎn)移的實際代價，我們說h函數(shù)是相容(consistent)的。(其實就是要求h不能削減得太快)G(s)到達s狀態(tài)之前的代價，一般就采納s在搜尋樹中的深度。F(s)s的估價函數(shù)，也就是到達目標(biāo)的總代價的估量。直觀上，應(yīng)當(dāng)有f(s)=g(s)+h(s),即已經(jīng)付出的和將要付出的代價之和。假如g是相容的，對于si和它的后輩節(jié)點，有h(sl)<=h(s2)+c(sl,s2)兩邊同時加上g(sl),有h(sl)+g(sl)<=h(s2)+g(sl)+c(sl,s2),也就是f(sl)<=f(s2)o因此f函數(shù)單調(diào)遞增。表1啟發(fā)式搜尋用到的符號貪心搜尋(Best-FirstSearch)象廣度優(yōu)先搜尋一樣用一個隊列儲存待擴展，但是根據(jù)h函數(shù)值從小到大排序(其實就是優(yōu)先隊列)。明顯由于h估量的不精確性，貪心搜尋不能保證得到的第一個解最優(yōu)，而且可能很久都找不到一個解。A*算法和貪心搜尋很類似，不過是根據(jù)f函數(shù)值進行排序。但是這樣會多出一個問題：新生成的狀態(tài)可能已經(jīng)遇到過了的。為什么會這樣呢？由于貪心搜尋是根據(jù)h函數(shù)值排序，而h只與狀態(tài)有關(guān)，因此不會消失重復(fù)，而f值不僅狀態(tài)有關(guān)，還與狀態(tài)轉(zhuǎn)移到s的方式有關(guān)，因此可能消失同一個狀態(tài)有不同的f值。解決方式也很簡潔，假如新狀態(tài)si與已經(jīng)遇到的狀態(tài)s2相同，保留f值比較小的一個就可以了。(假如s2是待擴展結(jié)點，是有可能消失f(s2)〉f(sl)的狀況的，只有已擴展結(jié)點才保證f值遞增)。A*算法保證得到最優(yōu)解，但是所用的空間是很大的,難以適應(yīng)我們的搬運工問題。IDA*算法既然A*算法存在空間問題，那么我們能不能借用深度優(yōu)先搜尋的空間優(yōu)勢，用重復(fù)式搜尋的方式來緩解危機呢？經(jīng)過爭論，Korf于1985年提出了一個IternativeDeepeningA*(IDA*)算法，比較好的解決了這一問題。一開頭，我們把深度最大值Dmax設(shè)為起始結(jié)點的h值，開頭進行深度優(yōu)先搜尋，忽視全部f值大于Dmax的結(jié)點，削減了許多搜尋量。假如沒有解，再加大Dmax的值，直到找到一個解。簡潔證明這個解肯定是最優(yōu)的。由于改成了深度優(yōu)先的方式，與A*比較起來，IDA*更加有用：