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

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

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

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

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

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

圖中每個節(jié)點對應一個狀態(tài)，每條連線對應一個操作符。這些節(jié)點和連線(即狀態(tài)與操作符)又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫和規(guī)則來標記。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。第5頁，課件共45頁，創(chuàng)作于2023年2月圖組成節(jié)點有向邊圖分類或圖（直接圖、狀態(tài)圖）與或圖圖搜索過程圖第6頁，課件共45頁，創(chuàng)作于2023年2月圖（狀態(tài)圖）搜索策略CLOSED表：用來記錄考察過的節(jié)點對樹形搜索，存儲的是搜索樹對線式搜索，存儲的是折線OPEN表：記錄待考察的節(jié)點排序方式不同，對應的搜索算法不同節(jié)點父節(jié)點編號編號節(jié)點父節(jié)點編號CLOSED表OPEN表第7頁，課件共45頁，創(chuàng)作于2023年2月開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表n為目標節(jié)點嗎？把n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針修改指針方向重排OPEN表失敗成功圖3.1

圖搜索過程框圖是是否否第8頁，課件共45頁，創(chuàng)作于2023年2月3.2

盲目搜索特點：不需重排OPEN表種類：寬度優(yōu)先、深度優(yōu)先、等代價搜索等。3.2.1

寬度優(yōu)先搜索

定義

以接近起始節(jié)點的程度逐層擴展節(jié)點的搜索方法。特點：一種高代價搜索，但若有解存在，則必能找到它。

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

(Breadth-firstsearch,BFS)優(yōu)先在同一級節(jié)點中考察，只有當同一級節(jié)點考察完畢之后，才考察下一級節(jié)點自頂向下一層一層逐漸生成的第10頁，課件共45頁，創(chuàng)作于2023年2月寬度優(yōu)先搜索算法步1：把初始節(jié)點So放入OPEN表中。步2：若OPEN表為空,則搜索失敗,退出。步3：取OPEN表中前面第一個節(jié)點N放在CLOSED表中,并冠以順序編號n。步4：若目標節(jié)點Sg=N,則搜索成功,結束。步5：若N不可擴展,則轉步2。步6：擴展N,將mj子節(jié)點配上指向N的指針依次放入OPEN表尾部,轉步2。注解：OPEN表是一個隊列CLOSED表是一個順序表，表中各節(jié)點按順序標號，正在被考察的節(jié)點在表中編號最大如果問題有解，目標點Sg必出現(xiàn)在OPEN表中，算法結束根據(jù)返回指針，在CLOSED表中回溯，得到求解路徑第11頁，課件共45頁，創(chuàng)作于2023年2月開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表是否有后繼節(jié)點為目標節(jié)點？擴展n，把n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針失敗成功圖3.2寬度優(yōu)先算法框圖是否是否第12頁，課件共45頁，創(chuàng)作于2023年2月

例子

八數(shù)碼難題（8-puzzleproblem）

1238456712384567（目標狀態(tài)）規(guī)定：將牌移入空格的順序為：從空格左邊開始順時針旋轉。不許斜向移動，也不返回先輩節(jié)點。從圖可見，要擴展26個節(jié)點，共生成46個節(jié)點之后才求得解（目標節(jié)點）。第13頁，課件共45頁，創(chuàng)作于2023年2月123845671238412384567412385671238412384567123845671238456767891011121312384567567567112384567123845671238456712384567234513456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567圖3.4八數(shù)碼難題的寬度優(yōu)先搜索樹第14頁，課件共45頁，創(chuàng)作于2023年2月寬度優(yōu)先搜索算法寬度優(yōu)先/橫向搜索優(yōu)點策略是完備的如果有解，肯定找到解，且找到的解是最優(yōu)解(最短路徑)缺點效率低第15頁，課件共45頁，創(chuàng)作于2023年2月節(jié)點深度：根節(jié)點深度=0其它節(jié)點深度=父節(jié)點深度+13.2.2

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

深度優(yōu)先搜索

定義

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

算法

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

等代價搜索

定義

是寬度優(yōu)先搜索的一種推廣，不是沿著等長度路徑斷層進行擴展，而是沿著等代價路徑斷層進行擴展。搜索樹中每條連接弧線上的有關代價,表示時間、距離等花費。

算法

若所有連接弧線具有相等代價，則簡化為寬度優(yōu)先搜索算法。第21頁，課件共45頁，創(chuàng)作于2023年2月開始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節(jié)點i從OPEN表移至CLOSED表是否有后繼節(jié)點為目標節(jié)點？失敗成功圖3.2等代價搜索算法框圖是否是否S是否目標節(jié)點？是成功擴展i，計算其后繼節(jié)點j的g(j)，并把后繼節(jié)點放入OPEN表否令g(s)=0第22頁，課件共45頁，創(chuàng)作于2023年2月國際象棋對弈程序:深藍開發(fā)者:IBM的MurryCampbell,Feng-HsiungHsu和JosephHoane采用30個IBMRS/6000處理器來運行軟件搜索使用480個定制VLSI國際象棋處理器執(zhí)行生成行棋的功能﹑樹的最后幾層的”硬件搜索”以及對葉節(jié)點的評價.每秒平均搜索12.6億種走法，峰值時每秒鐘搜索33億個節(jié)點.每走一步至多能夠預先計算300億種個棋局,常規(guī)搜索深度是14步.機器的核心算法是使用調(diào)換表的標準迭代深入α-β搜索,而且對關鍵的點具備產(chǎn)生超越搜索深度的擴展能力,在某些情況下可以達到40層的深度.評價函數(shù)采用了超過8000個特征;使用一本有4000個棋局的”開局手冊”以及一個存有70萬個大師級比賽棋譜的數(shù)據(jù)庫;使用一個大型殘局數(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)空間很小的簡單問題大空間無法勝任：組合爆炸組合爆炸64階梵塔：節(jié)點：364=0.94*1030理論最短路徑：264-1=2*1019博弈一字棋：9！=3.6*105西洋棋：1078國際象棋：10120（極限并行速度10-104秒/步，需1016年）圍棋：107613.3

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

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

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

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

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

有序搜索實質

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

例子八數(shù)碼難題（8-puzzleproblem）12384567（目標狀態(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ā)信息來引導搜索，達到減少搜索范圍，降低問題復雜度的目的在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率啟發(fā)信息強降低搜索工作量，但可能導致找不到最優(yōu)解弱產(chǎn)生式系統(tǒng)在找到一條路徑之前將擴展過多的節(jié)點，一般導致工作量加大極限情況下盲目搜索，但可能可以找到最優(yōu)解3.3.3A*算法第33頁，課件共45頁，創(chuàng)作于2023年2月A*算法評價函數(shù)

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

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

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

——g是g*的估計，h是h*的估計A*算法的定義：

定義1

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

定義2

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

定義3

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

第35頁，課件共45頁，創(chuàng)作于2023年2月評價函數(shù)的計算g（n）根據(jù)已搜索的結果，按照從初始結點s到結點n的路徑，計算其耗散值即可g(n)對g*(n)作出估計，有g(n)≥g*(n)h(n)依賴于啟發(fā)信息，稱為啟發(fā)函數(shù)對未來擴展的方向作出估計f(n)按f(n)遞增的順序來排列OPEN表的節(jié)點，優(yōu)先擴展f(n)值小的節(jié)點，體現(xiàn)了好的優(yōu)先搜索思想3.3.3A*算法第36頁，課件共45頁，創(chuàng)作于2023年2月八數(shù)碼2831647512384765初始狀態(tài)第37頁，課件共45頁，創(chuàng)作于2023年2月八數(shù)碼評價函數(shù)f(n)=g(n)+h(n)g(n)：從初始節(jié)點到當前節(jié)點的耗散值h(n)：當前節(jié)點“不在位”的將牌數(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