狀態(tài)空間搜索策略

狀態(tài)空間搜索策略第1頁，課件共45頁，創(chuàng)作于2023年2月

從問題表示到問題的解決，有一個(gè)求解的過程。常見的AI問題求解技術(shù)有兩種，即“搜索”（Search）和“推理”（Reasoning）方法。

邏輯推理，是通過構(gòu)造一個(gè)邏輯系統(tǒng)，由它可以從已有的斷言（公理）推導(dǎo)出新的斷言。并用邏輯形式語言描述的一組公理來表達(dá)問題域。用這種方法來解決問題就是通過推理來積聚越來越多的斷言，直到獲得問題的解答。雖然問題求解可通過搜索方法，也可用邏輯推理，但二者的側(cè)重點(diǎn)是不一樣的。前者著重于尋求問題解答的過程，而后者強(qiáng)調(diào)前提（初始）問題空間（公理集合）與問題解答間連接的邏輯正確性。或者簡(jiǎn)單地講，搜索著重于發(fā)現(xiàn)（Discovery），而推理強(qiáng)調(diào)證明（Proof）。第2頁，課件共45頁，創(chuàng)作于2023年2月搜索在狀態(tài)圖中尋找目標(biāo)或路徑的基本方法從初始節(jié)點(diǎn)，沿著與之相連的邊，尋找目標(biāo)節(jié)點(diǎn)的過程搜索樹搜索過程中經(jīng)過的節(jié)點(diǎn)和邊，按照原圖的連接關(guān)系，便形成一個(gè)樹形的有向圖第3頁，課件共45頁，創(chuàng)作于2023年2月盲目搜索無向?qū)阉?窮舉式搜索從初始節(jié)點(diǎn)，沿連接邊逐一考察各個(gè)節(jié)點(diǎn)，或反向進(jìn)行啟發(fā)式(heuristic)搜索利用“啟發(fā)性信息”引導(dǎo)的搜索啟發(fā)式信息是與問題有關(guān)的有利于盡快找到問題解的信息或知識(shí)第4頁，課件共45頁，創(chuàng)作于2023年2月3.1

圖搜索策略圖（狀態(tài)圖）搜索控制策略

一種在圖中尋找路徑的方法。

圖中每個(gè)節(jié)點(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à)于求得圖中的一條路徑問題。第5頁，課件共45頁，創(chuàng)作于2023年2月圖組成節(jié)點(diǎn)有向邊圖分類或圖（直接圖、狀態(tài)圖）與或圖圖搜索過程圖第6頁，課件共45頁，創(chuàng)作于2023年2月圖（狀態(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表第7頁，課件共45頁，創(chuàng)作于2023年2月開始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針修改指針方向重排OPEN表失敗成功圖3.1

圖搜索過程框圖是是否否第8頁，課件共45頁，創(chuàng)作于2023年2月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à)搜索，但若有解存在，則必能找到它。

算法第9頁，課件共45頁，創(chuàng)作于2023年2月廣度（寬度）優(yōu)先搜索

(Breadth-firstsearch,BFS)優(yōu)先在同一級(jí)節(jié)點(diǎn)中考察，只有當(dāng)同一級(jí)節(jié)點(diǎn)考察完畢之后，才考察下一級(jí)節(jié)點(diǎn)自頂向下一層一層逐漸生成的第10頁，課件共45頁，創(chuàng)作于2023年2月寬度優(yōu)先搜索算法步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表中回溯，得到求解路徑第11頁，課件共45頁，創(chuàng)作于2023年2月開始把S放入OPEN表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)先算法框圖是否是否第12頁，課件共45頁，創(chuàng)作于2023年2月

例子

八數(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)）。第13頁，課件共45頁，創(chuàng)作于2023年2月123845671238412384567412385671238412384567123845671238456767891011121312384567567567112384567123845671238456712384567234513456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567圖3.4八數(shù)碼難題的寬度優(yōu)先搜索樹第14頁，課件共45頁，創(chuàng)作于2023年2月寬度優(yōu)先搜索算法寬度優(yōu)先/橫向搜索優(yōu)點(diǎn)策略是完備的如果有解，肯定找到解，且找到的解是最優(yōu)解(最短路徑)缺點(diǎn)效率低第15頁，課件共45頁，創(chuàng)作于2023年2月節(jié)點(diǎn)深度：根節(jié)點(diǎn)深度=0其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+13.2.2

深度優(yōu)先搜索第16頁，課件共45頁，創(chuàng)作于2023年2月3.2.2

深度優(yōu)先搜索

定義

首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。

算法

防止搜索過程沿著無益的路徑擴(kuò)展下去，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度——深度界限。與寬度優(yōu)先搜索算法最根本的不同在于：將擴(kuò)展的后繼節(jié)點(diǎn)放在OPEN表的前端。（算法框圖見教材）第17頁，課件共45頁，創(chuàng)作于2023年2月深度優(yōu)先搜索（Depth-firstsearch，DFS）在搜索樹的每一層始終只擴(kuò)展一個(gè)子結(jié)點(diǎn)，不斷地向縱深前進(jìn)直到不能再前進(jìn)（到達(dá)葉子結(jié)點(diǎn)或深度限制），才從當(dāng)前節(jié)點(diǎn)返回上一級(jí)節(jié)點(diǎn)，沿另一方向又繼續(xù)前進(jìn)從樹根開始一枝一枝逐漸生成的第18頁，課件共45頁，創(chuàng)作于2023年2月路徑節(jié)點(diǎn)序列為(n0,n1,…,nk)對(duì)于i=1,…,k，若節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni，該序列稱為從n0到nk的路徑n0nkn1nk-1n3n2第19頁，課件共45頁，創(chuàng)作于2023年2月深度優(yōu)先搜索算法縱向搜索缺點(diǎn)如果一個(gè)有解的問題樹可能有無窮分支，如果誤入無窮分支（即深度無限），則不可能找到目標(biāo)節(jié)點(diǎn)策略不是完備的找到的解是不一定最優(yōu)解最短路徑)第20頁，課件共45頁，創(chuàng)作于2023年2月3.2.3

等代價(jià)搜索

定義

是寬度優(yōu)先搜索的一種推廣，不是沿著等長(zhǎng)度路徑斷層進(jìn)行擴(kuò)展，而是沿著等代價(jià)路徑斷層進(jìn)行擴(kuò)展。搜索樹中每條連接弧線上的有關(guān)代價(jià),表示時(shí)間、距離等花費(fèi)。

算法

若所有連接弧線具有相等代價(jià)，則簡(jiǎn)化為寬度優(yōu)先搜索算法。第21頁，課件共45頁，創(chuàng)作于2023年2月開始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節(jié)點(diǎn)i從OPEN表移至CLOSED表是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？失敗成功圖3.2等代價(jià)搜索算法框圖是否是否S是否目標(biāo)節(jié)點(diǎn)？是成功擴(kuò)展i，計(jì)算其后繼節(jié)點(diǎn)j的g(j)，并把后繼節(jié)點(diǎn)放入OPEN表否令g(s)=0第22頁，課件共45頁，創(chuàng)作于2023年2月國(guó)際象棋對(duì)弈程序:深藍(lán)開發(fā)者:IBM的MurryCampbell,Feng-HsiungHsu和JosephHoane采用30個(gè)IBMRS/6000處理器來運(yùn)行軟件搜索使用480個(gè)定制VLSI國(guó)際象棋處理器執(zhí)行生成行棋的功能﹑樹的最后幾層的”硬件搜索”以及對(duì)葉節(jié)點(diǎn)的評(píng)價(jià).每秒平均搜索12.6億種走法，峰值時(shí)每秒鐘搜索33億個(gè)節(jié)點(diǎn).每走一步至多能夠預(yù)先計(jì)算300億種個(gè)棋局,常規(guī)搜索深度是14步.機(jī)器的核心算法是使用調(diào)換表的標(biāo)準(zhǔn)迭代深入α-β搜索,而且對(duì)關(guān)鍵的點(diǎn)具備產(chǎn)生超越搜索深度的擴(kuò)展能力,在某些情況下可以達(dá)到40層的深度.評(píng)價(jià)函數(shù)采用了超過8000個(gè)特征;使用一本有4000個(gè)棋局的”開局手冊(cè)”以及一個(gè)存有70萬個(gè)大師級(jí)比賽棋譜的數(shù)據(jù)庫;使用一個(gè)大型殘局?jǐn)?shù)據(jù)庫保存已解決的棋局.第23頁，課件共45頁，創(chuàng)作于2023年2月Video/v_show/id_XMzk1MzQ0ODYw.htmlDeepBlue15years/v_show/id_XMTEyOTU5MjQ0.html

卡斯帕羅夫/v_show/id_XMzU4NzY0NzE2.htmlWindows8/v_show/id_XMzE4MzM5OTA0.htmlKinect第24頁，課件共45頁，創(chuàng)作于2023年2月問題的提出窮舉算法可以解決狀態(tài)空間很小的簡(jiǎn)單問題大空間無法勝任：組合爆炸組合爆炸64階梵塔：節(jié)點(diǎn)：364=0.94*1030理論最短路徑：264-1=2*1019博弈一字棋：9！=3.6*105西洋棋：1078國(guó)際象棋：10120（極限并行速度10-104秒/步，需1016年）圍棋：107613.3

啟發(fā)式搜索第25頁，課件共45頁，創(chuàng)作于2023年2月啟發(fā)性信息按其用途劃分,啟發(fā)性信息可分為以下三類：用于擴(kuò)展節(jié)點(diǎn)的選擇,即用于決定應(yīng)先擴(kuò)展哪一個(gè)節(jié)點(diǎn),以免盲目擴(kuò)展。用于生成節(jié)點(diǎn)的選擇,即用于決定應(yīng)生成哪些后續(xù)節(jié)點(diǎn),以免盲目地生成過多無用節(jié)點(diǎn)。用于刪除節(jié)點(diǎn)的選擇,即用于決定應(yīng)刪除哪些無用節(jié)點(diǎn),以免造成進(jìn)一步的時(shí)空浪費(fèi)。第26頁，課件共45頁，創(chuàng)作于2023年2月3.3

啟發(fā)式搜索特點(diǎn)：重排OPEN表，選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展種類：有序搜索、A*算法等3.3.1啟發(fā)式搜索策略和估價(jià)函數(shù)盲目搜索可能帶來組合爆炸啟發(fā)式信息

用來加速搜索過程的有關(guān)問題領(lǐng)域的特征信息。第27頁，課件共45頁，創(chuàng)作于2023年2月啟發(fā)函數(shù)啟發(fā)函數(shù)是用來估計(jì)搜索樹上節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)Sg接近程度的一種函數(shù),通常記為h(x)定義一個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的某種距離或差異的度量一個(gè)節(jié)點(diǎn)處于最佳路徑上的概率根據(jù)經(jīng)驗(yàn)的主觀打分第28頁，課件共45頁，創(chuàng)作于2023年2月估價(jià)函數(shù)

為獲得某些節(jié)點(diǎn)“希望”的啟發(fā)信息，提供一個(gè)評(píng)定侯選擴(kuò)展節(jié)點(diǎn)的方法，以便確定哪個(gè)節(jié)點(diǎn)最有可能在通向目標(biāo)的最佳路徑上。

f(n)——表示節(jié)點(diǎn)n的估價(jià)函數(shù)值應(yīng)用節(jié)點(diǎn)“希望”程度（估價(jià)函數(shù)值）重排OPEN表3.3.2

有序搜索實(shí)質(zhì)

選擇OPEN表上具有最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。第29頁，課件共45頁，創(chuàng)作于2023年2月開始把S放入OPEN表，計(jì)算估價(jià)函數(shù)f(s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點(diǎn)i放入CLOSED表i為目標(biāo)節(jié)點(diǎn)嗎？擴(kuò)展i，得后繼節(jié)點(diǎn)j，計(jì)算f(j)，提供返回節(jié)點(diǎn)i的指針，利用f(j)對(duì)OPEN表重新排序，調(diào)整親子關(guān)系及指針失敗成功圖3.9有序搜索算法框圖是否是否算法第30頁，課件共45頁，創(chuàng)作于2023年2月

例子八數(shù)碼難題（8-puzzleproblem）12384567（目標(biāo)狀態(tài)）12384567（初始狀態(tài)）八數(shù)碼難題的有序搜索樹見下圖：第31頁，課件共45頁，創(chuàng)作于2023年2月123845671238456712384567（4）（6）（6）123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）圖3.10八數(shù)碼難題的有序搜索樹123846（4）7第32頁，課件共45頁，創(chuàng)作于2023年2月啟發(fā)式搜索利用問題擁有的啟發(fā)信息來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率啟發(fā)信息強(qiáng)降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解弱產(chǎn)生式系統(tǒng)在找到一條路徑之前將擴(kuò)展過多的節(jié)點(diǎn)，一般導(dǎo)致工作量加大極限情況下盲目搜索，但可能可以找到最優(yōu)解3.3.3A*算法第33頁，課件共45頁，創(chuàng)作于2023年2月A*算法評(píng)價(jià)函數(shù)

f(n)=g(n)+h(n)n是被評(píng)價(jià)的結(jié)點(diǎn)f(n)評(píng)價(jià)函數(shù)從s經(jīng)過n到g的路徑的耗散值g(n)代價(jià)函數(shù)從s到n的路徑的耗散值h(n)啟發(fā)函數(shù)從n到g的路徑的耗散值第34頁，課件共45頁，創(chuàng)作于2023年2月3.3.3A*算法估價(jià)函數(shù)的定義：

對(duì)節(jié)點(diǎn)n定義f*(n)=g*(n)+h*(n),表示從S開始約束通過節(jié)點(diǎn)n的一條最佳路徑的代價(jià)。

希望估價(jià)函數(shù)f定義為：f(n)=g(n)+h(n)

——g是g*的估計(jì)，h是h*的估計(jì)A*算法的定義：

定義1

在GRAPHSEARCH過程中，如果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，則稱該過程為A算法。

定義2

在A算法中，如果對(duì)所有的x存在h(x)≤h*(x),則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計(jì)。

定義3

采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當(dāng)h=0時(shí)，A*算法就變?yōu)橛行蛩阉魉惴ā?/p>

第35頁，課件共45頁，創(chuàng)作于2023年2月評(píng)價(jià)函數(shù)的計(jì)算g（n）根據(jù)已搜索的結(jié)果，按照從初始結(jié)點(diǎn)s到結(jié)點(diǎn)n的路徑，計(jì)算其耗散值即可g(n)對(duì)g*(n)作出估計(jì)，有g(shù)(n)≥g*(n)h(n)依賴于啟發(fā)信息，稱為啟發(fā)函數(shù)對(duì)未來擴(kuò)展的方向作出估計(jì)f(n)按f(n)遞增的順序來排列OPEN表的節(jié)點(diǎn)，優(yōu)先擴(kuò)展f(n)值小的節(jié)點(diǎn)，體現(xiàn)了好的優(yōu)先搜索思想3.3.3A*算法第36頁，課件共45頁，創(chuàng)作于2023年2月八數(shù)碼2831647512384765初始狀態(tài)第37頁，課件共45頁，創(chuàng)作于2023年2月八數(shù)碼評(píng)價(jià)函數(shù)f(n)=g(n)+h(n)g(n)：從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值h(n)：當(dāng)前節(jié)點(diǎn)“不在位”的將牌數(shù)2831647512345768h(n)=4第38頁，課件共45頁，創(chuàng)作于2023年2月2831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465S(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)124356g=0h=4f=4g=1h=5f=6g=1h=3f=4g=1h=5f=6g=2h=3f=5g=2h=3f=5g=2h=4f=6g=3h