《狀態(tài)空間搜索》PPT課件

《《狀態(tài)空間搜索》PPT課件》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、狀態(tài)空間搜索狀態(tài)空間搜索策略數(shù)據(jù)驅(qū)動和目標(biāo)驅(qū)動的搜索圖搜索的實(shí)現(xiàn)深度和廣度優(yōu)先搜索有界深度優(yōu)先搜索謂詞演算推理的狀態(tài)空間表示法邏輯的狀態(tài)空間描述與/或圖討論基于遞歸的搜索遞歸遞歸搜索模式驅(qū)動搜索產(chǎn)生式系統(tǒng)定義與歷史產(chǎn)生式系統(tǒng)示例產(chǎn)生式系統(tǒng)搜索的控制產(chǎn)生式系統(tǒng)的優(yōu)點(diǎn)狀態(tài)空間搜索策略數(shù)據(jù)驅(qū)動和目標(biāo)驅(qū)動的搜索狀態(tài)空間可以從兩個方向進(jìn)行搜索：從實(shí)際問題的給定數(shù)據(jù)向目標(biāo)搜索或者從目標(biāo)到數(shù)據(jù)進(jìn)行搜索。數(shù)據(jù)驅(qū)動搜索，也稱為正向推理。搜索的過程是應(yīng)用規(guī)則從給定的條件產(chǎn)生新的條件，再用規(guī)則從新的條件產(chǎn)生更多的新條

2、件。這個過程持續(xù)到有一條滿足目標(biāo)要求的路徑產(chǎn)生為止。另一種求解方法是：先從欲想達(dá)到的目標(biāo)開始，看哪些規(guī)則或合法移動能產(chǎn)生該目標(biāo)以及應(yīng)用這些規(guī)則產(chǎn)生目標(biāo)時需要哪些條件。這些條件就成為我們要達(dá)到的新目標(biāo)，即子目標(biāo)。搜索就通過反向的、連續(xù)的子目標(biāo)不斷地進(jìn)行，一直到找到問題給定的條件為止。這樣就找到了一條從數(shù)據(jù)到目標(biāo)的移動或規(guī)則組成的鏈，盡管搜索方向和它正好相反。這種方法稱為目標(biāo)驅(qū)動的推理或反向推理。在實(shí)際的搜索系統(tǒng)中可能兩種方法同時使用，即一方面從數(shù)據(jù)驅(qū)動向目標(biāo)進(jìn)行，可能搜索到某一個子目標(biāo)；另一方面又

3、從目標(biāo)向數(shù)據(jù)方面進(jìn)行搜索，剛好也搜索到該子目標(biāo)，這時推理也結(jié)束，即假設(shè)的目標(biāo)正確。圖搜索的實(shí)現(xiàn)無論是目標(biāo)還是數(shù)據(jù)驅(qū)動的搜索，其求解問題都是要在狀態(tài)空間圖中找到從初態(tài)到目標(biāo)狀態(tài)的路徑。而路徑上弧的序列就對應(yīng)解題的先后步驟。若在選擇解題路徑時能給出絕對可靠的預(yù)言或絕對正確的機(jī)制，那就不需要搜索了，求解時會一次成功地穿過空間到達(dá)目標(biāo)，構(gòu)造出一條求解路徑來。但實(shí)際問題中沒有絕對可靠的預(yù)言，求解時必須嘗試多條路徑直到找到目標(biāo)為止。回溯是一種經(jīng)常使用的技術(shù)。圖搜索的實(shí)現(xiàn)（續(xù)）帶回溯的搜索從初始狀態(tài)出發(fā)，不停

4、地尋找路徑一直到它到達(dá)目標(biāo)或“不可解端點(diǎn)”。若找到目標(biāo)，就退出搜索，返回解題路徑，若遇到不可解結(jié)點(diǎn)，就回溯到路徑中最近的父結(jié)點(diǎn)上，查看是否有當(dāng)前結(jié)點(diǎn)的兄弟結(jié)點(diǎn)未擴(kuò)展，并沿這些分支繼續(xù)搜索。算法在每個結(jié)點(diǎn)上的檢查過程遵循下面的遞歸方式：圖搜索的實(shí)現(xiàn)（續(xù)）若當(dāng)前狀態(tài)S未到達(dá)目標(biāo)的要求，就對它的第一子狀態(tài)Schild1遞歸調(diào)用回溯過程。如果在以Schild1為根的子圖中沒有找到目標(biāo)，就對它的兄弟Schild2調(diào)用此過程。此過程重復(fù)進(jìn)行到某個結(jié)點(diǎn)的后裔是目標(biāo)或者所有子結(jié)點(diǎn)都搜索完為止。圖搜索的實(shí)現(xiàn)（續(xù)）

5、算法就是以這種方式執(zhí)行直到找到目標(biāo)或遍歷了狀態(tài)空間為止。下圖給出的是一個假設(shè)的狀態(tài)空間的深度優(yōu)先回溯搜索。1A2B8C10DE36F9GHIJ457一個假設(shè)狀態(tài)空間的深度優(yōu)先回溯搜索圖搜索的實(shí)現(xiàn)（續(xù)）下面定義一個回溯搜索的算法：算法使用3張表保存狀態(tài)空間中的結(jié)點(diǎn)。SL狀態(tài)表列出了當(dāng)前路徑上的狀態(tài)。如果找到了目標(biāo)，SL就是解題路徑上狀態(tài)的有序集。NSL新狀態(tài)表，包含了等待評估的結(jié)點(diǎn)，其后裔結(jié)點(diǎn)還未被擴(kuò)展。DE不可解端點(diǎn)集,列出了找不到解題路徑的狀態(tài)。如果在搜索中再遇到它們，就會檢測到它們是DE中的

6、成分而立即將其排除。為了在最普遍的情況下（是圖而不是樹）定義回溯算法，有必要檢測并刪除多次出現(xiàn)的某些狀態(tài)，以避免造成路徑循環(huán)。檢測可以通過對每一個新生成的狀態(tài)判斷它是否在上述3張表中來實(shí)現(xiàn)，如果它屬于某一張表，就說明它已被搜索過不必再考慮。圖搜索的實(shí)現(xiàn)（續(xù)）當(dāng)前正在搜索的結(jié)點(diǎn)叫CS，即當(dāng)前狀態(tài)。CS總是等于最近加入SL中的狀態(tài)，是當(dāng)前正在探尋的解題路徑的“前鋒”。博弈中走步用的推理規(guī)則或者其他合適的問題求解操作都可應(yīng)用于CS，得到一些新狀態(tài)，即CS的子狀態(tài)的有序集，重新視該集合中第一個狀態(tài)為當(dāng)前

7、狀態(tài)，其余的按次序放入NSL中，用于以后的搜索。新的CS加入SL中，搜索就這樣繼續(xù)進(jìn)行。若CS沒有子狀態(tài)，就要從SL，NSL中刪除它，將其加入DE，然后回溯查找NSL中的下一個狀態(tài)。圖搜索的實(shí)現(xiàn)（續(xù)）Functionbacktrack(回溯算法）beginSL:=[Start];NSL:=[Start];DE:=[];CS:=Start;/*初始化*/whileNSL?[]/*還有未檢查的狀態(tài)*/dobeginifCS=目標(biāo)（或符合目標(biāo)的要求）thenreturn(SL);/*成功，返回路徑狀態(tài)

8、的表*/ifCS沒有子狀態(tài)（不包括DE，SL和NSL中已有的狀態(tài)）thenbeginwhile((SL非空）and(CS=SL中第一個元素))圖搜索的實(shí)現(xiàn)（續(xù)）dobegin將CS加入DE；/*標(biāo)明此狀態(tài)不可解*/從SL中刪除第一個元素；/*回溯*/從NSL中刪去第一個元素；CS：=NSL中第一個元素；end;將CS加入SL；endelsebegin將CS子狀態(tài)（不包括DE、SL、NSL中有的）加入NSL；圖搜索的實(shí)現(xiàn)（續(xù)）CS：=NSL中第一個元素；將CS加入SL；endend;returnF