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

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

1、三、搜索策略3.1圖搜索策略3.2盲目搜索3.3啟發(fā)式搜索從問題表示到問題的解決，有一個(gè)求解的過程。常見的AI問題求解技術(shù)有兩種，即“搜索”（Search）和“推理”（Reasoning）方法。邏輯推理，是通過構(gòu)造一個(gè)邏輯系統(tǒng)，由它可以從已有的斷言（公理）推導(dǎo)出新的斷言。并用邏輯形式語言描述的一組公理來表達(dá)問題域。用這種方法來解決問題就是通過推理來積聚越來越多的斷言，直到獲得問題的解答。雖然問題求解可通過搜索方法，也可用邏輯推理，但二者的側(cè)重點(diǎn)是不一樣的。前者著重于尋求問題解答的過程，而后者強(qiáng)調(diào)前提（初始）問題空間（公理集合）與問題

2、解答間連接的邏輯正確性。或者簡單地講，搜索著重于發(fā)現(xiàn)（Discovery），而推理強(qiáng)調(diào)證明（Proof）。搜索在狀態(tài)圖中尋找目標(biāo)或路徑的基本方法從初始節(jié)點(diǎn)，沿著與之相連的邊，尋找目標(biāo)節(jié)點(diǎn)的過程搜索樹搜索過程中經(jīng)過的節(jié)點(diǎn)和邊，按照原圖的連接關(guān)系，便形成一個(gè)樹形的有向圖盲目搜索無向?qū)阉?窮舉式搜索從初始節(jié)點(diǎn)，沿連接邊逐一考察各個(gè)節(jié)點(diǎn)，或反向進(jìn)行啟發(fā)式(heuristic)搜索利用“啟發(fā)性信息”引導(dǎo)的搜索啟發(fā)式信息是與問題有關(guān)的有利于盡快找到問題解的信息或知識(shí)3.1圖搜索策略圖（狀態(tài)圖）搜索控制策略一種在圖中尋找路徑的方法。圖中每個(gè)節(jié)

3、點(diǎn)對(duì)應(yīng)一個(gè)狀態(tài)，每條連線對(duì)應(yīng)一個(gè)操作符。這些節(jié)點(diǎn)和連線(即狀態(tài)與操作符)又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫和規(guī)則來標(biāo)記。求得把一個(gè)數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價(jià)于求得圖中的一條路徑問題。圖組成節(jié)點(diǎn)有向邊圖分類或圖（直接圖、狀態(tài)圖）與或圖圖搜索過程圖圖（狀態(tài)圖）搜索策略CLOSED表：用來記錄考察過的節(jié)點(diǎn)對(duì)樹形搜索，存儲(chǔ)的是搜索樹對(duì)線式搜索，存儲(chǔ)的是折線OPEN表：記錄待考察的節(jié)點(diǎn)排序方式不同，對(duì)應(yīng)的搜索算法不同節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)編號(hào)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)CLOSED表OPEN表開始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OP

4、EN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針修改指針方向重排OPEN表失敗成功圖3.1圖搜索過程框圖是是否否3.2盲目搜索特點(diǎn)：不需重排OPEN表種類：寬度優(yōu)先、深度優(yōu)先、等代價(jià)搜索等。3.2.1寬度優(yōu)先搜索定義以接近起始節(jié)點(diǎn)的程度逐層擴(kuò)展節(jié)點(diǎn)的搜索方法。特點(diǎn)：一種高代價(jià)搜索，但若有解存在，則必能找到它。算法廣度（寬度）優(yōu)先搜索(Breadth-firstsearch,BFS)優(yōu)先在同一級(jí)節(jié)點(diǎn)中考察，只有當(dāng)同一級(jí)節(jié)點(diǎn)考察完畢之后，才考察下一級(jí)節(jié)點(diǎn)自頂向下一層一層逐漸生成的寬度優(yōu)先搜

5、索算法步1：把初始節(jié)點(diǎn)So放入OPEN表中。步2：若OPEN表為空,則搜索失敗,退出。步3：取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放在CLOSED表中,并冠以順序編號(hào)n。步4：若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,結(jié)束。步5：若N不可擴(kuò)展,則轉(zhuǎn)步2。步6：擴(kuò)展N,將mj子節(jié)點(diǎn)配上指向N的指針依次放入OPEN表尾部,轉(zhuǎn)步2。注解：OPEN表是一個(gè)隊(duì)列CLOSED表是一個(gè)順序表，表中各節(jié)點(diǎn)按順序標(biāo)號(hào)，正在被考察的節(jié)點(diǎn)在表中編號(hào)最大如果問題有解，目標(biāo)點(diǎn)Sg必出現(xiàn)在OPEN表中，算法結(jié)束根據(jù)返回指針，在CLOSED表中回溯，得到求解路徑開始把S放入OPE

6、N表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？擴(kuò)展n，把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針失敗成功圖3.2寬度優(yōu)先算法框圖是否是否例子八數(shù)碼難題（8-puzzleproblem）1238456712384567（目標(biāo)狀態(tài)）規(guī)定：將牌移入空格的順序?yàn)椋簭目崭褡筮呴_始順時(shí)針旋轉(zhuǎn)。不許斜向移動(dòng)，也不返回先輩節(jié)點(diǎn)。從圖可見，要擴(kuò)展26個(gè)節(jié)點(diǎn)，共生成46個(gè)節(jié)點(diǎn)之后才求得解（目標(biāo)節(jié)點(diǎn)）。123845671238412384567412385671238412384567123

7、845671238456767891011121312384567567567112384567123845671238456712384567234513456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567圖3.4八數(shù)碼難題的寬度優(yōu)先搜索樹寬度優(yōu)先搜索算法寬度優(yōu)先/橫向搜索優(yōu)點(diǎn)策略是完備的如果有解，肯定找

8、到解，且找到的解是最優(yōu)解(最短路徑)缺點(diǎn)效率低節(jié)點(diǎn)深度：根節(jié)點(diǎn)深度=0其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+13.2.2深度優(yōu)先搜索3.2.2深度優(yōu)先搜索定義首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。算法防止搜索過程沿著無益的路徑擴(kuò)展下去，往往給出一個(gè)