搬運(yùn)工問題的啟示狀態(tài)空間搜索基本知識

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