人工智能之搜索培訓(xùn)講義

人工智能導(dǎo)論

第二章：搜索、問題求解與博弈人工智能之搜索培訓(xùn)講義第1頁第二章搜索、問題求解與博弈問題求解能力是人類智能基本組成部分，研究并實現(xiàn)問題求解是人工智能主要研究內(nèi)容之一。知識（問題）表示是問題求解基礎(chǔ)，兩種普遍采取問題表示方法：狀態(tài)空間表示與或圖表示搜索（優(yōu)化）：在問題表示基礎(chǔ)上，在合理時間范圍內(nèi)，從問題全部可能解中找到一個最優(yōu)解或可行解，是問題求解中關(guān)鍵技術(shù)。啟發(fā)式搜索----人工智能本質(zhì)特征之一。計算機(jī)博弈包括問題表示、搜索技術(shù)等AI關(guān)鍵問題，現(xiàn)有計算機(jī)博弈本質(zhì)上是將博弈問題轉(zhuǎn)變?yōu)橐粋€與或圖搜索問題進(jìn)行處理。人工智能之搜索培訓(xùn)講義第2頁主要內(nèi)容2.1搜索概述2.2問題求解2.2.1狀態(tài)空間2.2.2與或圖2.3搜索技術(shù)圖搜索2.4機(jī)器博弈人工智能之搜索培訓(xùn)講義第3頁一些例子搭積木智力游戲：有一個農(nóng)夫帶一條狼、一只羊和一筐菜要從河左岸乘船到右岸，但受以下條件限制：船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河沒有農(nóng)夫看管，則狼要吃羊，羊要吃菜請設(shè)計一個過河方案，使得農(nóng)夫、狼、羊、菜都不能受損地過河。類似問題：野人和傳教士問題下棋（撲克、西洋跳棋、國際象棋、象棋等）（屬于博弈）人工智能之搜索培訓(xùn)講義第4頁2.1搜索概述人工智能多個研究領(lǐng)域從求解現(xiàn)實問題過程來看，都可抽象為一個“問題求解”過程問題求解過程實際上就是一個搜索過程最優(yōu)性和計算法復(fù)雜性是搜索中一對矛盾，搜索必須考慮三個問題：采取盲目搜索還是啟發(fā)式搜索盲目搜索：不考慮問題本身特征，經(jīng)過遍歷問題解集合來尋找可行解或最優(yōu)解。啟發(fā)式搜索：利用與問題相關(guān)啟發(fā)式信息來確定搜索方向，以加緊搜索過程。進(jìn)行局部搜索還是全集搜索搜索可行解還是最優(yōu)解人工智能之搜索培訓(xùn)講義第5頁2.1搜索概述評價一個搜索算法原因：完備性：假如問題有解，一定能找到一個解最優(yōu)性：假如問題存在最優(yōu)解，則一定能找到這個最優(yōu)解復(fù)雜性：時間和空間復(fù)雜性，在確保最優(yōu)性和完備性前提下，算法復(fù)雜性越小越好。當(dāng)前搜索算法還不能同時滿足以上三個要求。為了進(jìn)行搜索，首先必須用某種形式把問題表示出來：狀態(tài)空間表示法和與或圖表示法就是用來表示問題及其搜索過程兩種慣用方法。人工智能之搜索培訓(xùn)講義第6頁2.2問題求解狀態(tài)空間表示法和與或圖表示法不但是問題表示方法，也分別代表了兩種問題求解思緒狀態(tài)空間將問題求解所包括每個可能步驟表示成一個狀態(tài)，全部狀態(tài)以及狀態(tài)之間全部轉(zhuǎn)換組成一個以圖形式表示狀態(tài)空間。問題求解過程是在狀態(tài)空間中搜索一條最優(yōu)或可行從初始狀態(tài)到目標(biāo)狀態(tài)路徑過程。與或圖表示法基礎(chǔ)是問題歸約，經(jīng)過一系列分解或變換，將復(fù)雜問題逐步轉(zhuǎn)化為比較簡單問題，直至能夠直接求解本原問題。與或圖求解過程是在與或圖中搜索一個將原始問題變換為簡單問題在變換為本原問題、最優(yōu)或可行歸約步驟過程。人工智能之搜索培訓(xùn)講義第7頁2.2.1狀態(tài)空間表示法狀態(tài)空間表示法是用“狀態(tài)”和“算子”來表示問題一個方法狀態(tài)：用來描述問題求解過程中不一樣時刻情況算子：表示對狀態(tài)操作，算子每次使用就使問題由一個狀態(tài)變換為另一個狀態(tài)當(dāng)?shù)竭_(dá)目標(biāo)狀態(tài)時，由初始狀態(tài)到目標(biāo)狀態(tài)所用算子序列就是問題一個解人工智能之搜索培訓(xùn)講義第8頁2.2.1狀態(tài)空間表示法狀態(tài)狀態(tài)是描述問題求解過程中任一時刻情況數(shù)據(jù)結(jié)構(gòu)，普通用一組變量有序組合表示：SK(SK0,SK1,…)當(dāng)給每一分量以確定值時，就得到一個詳細(xì)狀態(tài)算子引發(fā)狀態(tài)中一些分量發(fā)生改變，從而使問題由一個狀態(tài)變?yōu)榱硪粋€狀態(tài)操作稱為算子。產(chǎn)生式系統(tǒng)中，每一條產(chǎn)生式規(guī)則就是一個算子狀態(tài)空間由問題全部狀態(tài)及一切可用算符所組成集合稱為問題狀態(tài)空間，普通用三元組表示:(S,F,C,I,G)S:全部狀態(tài)組成集合F:用于狀態(tài)轉(zhuǎn)換算子集合C:狀態(tài)轉(zhuǎn)換代價聚合I:初始狀態(tài)集合G:目標(biāo)狀態(tài)集合人工智能之搜索培訓(xùn)講義第9頁例:二階HanoiTower（梵塔）問題設(shè)有三根柱子，在1號柱于上穿有A、B兩個盤片，盤A小于盤B，盤A位于盤B上面。要求把這兩個盤片全部移到另一根柱子上，而且要求每次只能移動一片，任何時刻都不能使盤B位于盤A上面。設(shè)SK=(SK0,SK1)表示問題狀態(tài)，SK0

表示盤片A所在柱號，SK1

表示盤片B所在柱號全部可能狀態(tài):S0=(1,1),S1=(1,2),S2=(1,3),S3=(2,1),S4=(2,2),S5=(2,3),S6=(3,1),S7=(3,2),S8=(3,3).問題初始狀態(tài)集合S={S0},目標(biāo)集合為G={S4,S8}算子分別用A(i,j),B(i,j)表示A(i,j):盤片A從柱i移到柱j；B(i,j):盤片B從柱i移到柱j全部可能算子：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2),B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)人工智能之搜索培訓(xùn)講義第10頁例:二階HanoiTower（梵塔）問題9種狀態(tài)，12種算子組成狀態(tài)空間轉(zhuǎn)移圖：人工智能之搜索培訓(xùn)講義第11頁2.2.1狀態(tài)空間表示法總結(jié)：用狀態(tài)空間方法表示問題時，首先必須定義狀態(tài)描述形式，經(jīng)過使用這種描述形式可把問題一切狀態(tài)都表示出來。其次，還安定義一組算符，經(jīng)過使用算符可把問題由一個狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€狀態(tài)。問題求解過程是一個不停把算符作用于狀態(tài)過程。假如在使用某個算符后得到新狀態(tài)是目標(biāo)狀態(tài)，就得到問題一個解：從初始狀態(tài)到目標(biāo)狀態(tài)所用算符組成序列。算符一次使用，就使問題由一個狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€狀態(tài)。可能有多個算特序列都可使問題從初始狀態(tài)變到目標(biāo)狀態(tài)，這就得到了多個解。把使用算符最少解稱為最優(yōu)解。對任何一個狀態(tài)，可使用算符可能不止一個，因而由一個狀態(tài)所生成后繼狀態(tài)就可能有多個。當(dāng)對這些后繼狀態(tài)使用算子生成更深入狀態(tài)時，首先應(yīng)對哪一狀態(tài)進(jìn)行操作呢？這取決于搜索策略，不一樣搜索策略操作次序是不相同。人工智能之搜索培訓(xùn)講義第12頁2.2.1狀態(tài)空間表示法基于狀態(tài)空間表示問題求解算法Step1：確定問題狀態(tài)計算機(jī)描述形式，將全部可能狀態(tài)表示出來，并確定其中初始狀態(tài)和目標(biāo)狀態(tài)。Step2：確定促使?fàn)顟B(tài)發(fā)生轉(zhuǎn)換操作，并在計算機(jī)中將其表示為對應(yīng)算符。Step3：以狀態(tài)為頂點，狀態(tài)之間所允許操作為有向邊，取得‘圖’形式狀態(tài)空間。Step4：應(yīng)用圖搜索方法，在狀態(tài)空間中搜索從初始狀態(tài)到目標(biāo)狀態(tài)最優(yōu)路徑或可行路徑。人工智能之搜索培訓(xùn)講義第13頁例:三階HanoiTower（梵塔）問題人工智能之搜索培訓(xùn)講義第14頁例:三階HanoiTower（梵塔）問題人工智能之搜索培訓(xùn)講義第15頁例:三階HanoiTower（梵塔）問題人工智能之搜索培訓(xùn)講義第16頁2.2.2與或圖表示法也稱為問題歸約方法：把初始問題經(jīng)過一系列交換最終變?yōu)橐粋€子問題集合，而這些于問題解能夠直接得到，從而解答了初始問題。分解：把一個復(fù)雜問題分解為若干個較為簡單子問題，每個子問題又可繼續(xù)分解為若干個更為簡單子問題。重復(fù)此過程，直到不需要再分解或者不能再分解為止。然后對每個子問題分別進(jìn)行求解，最終把各子問題解復(fù)合起來就得到了原問題解。問題分解能夠用圖表示出來，稱為與樹。比如，把問題P分解為三個子問題P1、P2和P3，能夠表示為下列圖：人工智能之搜索培訓(xùn)講義第17頁2.2.2與或圖表示法等價變換：利用同構(gòu)或同態(tài)等價變換，把它變換成若干個較輕易求解新問題。若新問題中有一個可求解，則就得到了原問題解。問題等價變換過程也可用一個圖表示出來，稱為“或”樹。與或樹結(jié)合稱為與或圖（樹）。人工智能之搜索培訓(xùn)講義第18頁2.2.2與或圖表示法本原問題：不能再分解或變換，而且直接可解子問題稱為本原問題。端節(jié)點與終止節(jié)點：在與／或樹中，沒有子節(jié)點節(jié)點稱為端節(jié)點；本原問題所對應(yīng)節(jié)點稱為終止節(jié)點。顯然，終止節(jié)點一定是端節(jié)點，但端節(jié)點不一定是終止節(jié)點?？山夤?jié)點：在與／或樹今，滿足以下條件之一節(jié)點：1)它是一個終止節(jié)點。2)它是一個“或”節(jié)點，且其子節(jié)點最少有一個是可解節(jié)點。3)它是一個“與”節(jié)點，且其子節(jié)點全部是可解節(jié)點。不可解節(jié)點：上面三個條件全不滿足節(jié)點。解樹：由可解節(jié)點所組成，而且由這些可解節(jié)點可推出初始節(jié)點(它對應(yīng)于原始問題)為可解節(jié)點子樹稱為解樹。在解樹中’定包含初始節(jié)點。人工智能之搜索培訓(xùn)講義第19頁例:三階HanoiTower（梵塔）問題設(shè)有A、B、C三個盤片以及三根柱子，三個盤片按從小到大次序穿在1號柱上，要求把它們?nèi)恳频?號柱上，而且每次只能移動一個盤片，任何時刻都不能把大盤片壓在小盤片上面，如圖所表示。人工智能之搜索培訓(xùn)講義第20頁例:三階HanoiTower（梵塔）問題分析：1)為了把三個盤片全部移到3號柱上，必須先把盤片C移到3號柱上。2)為了移盤片C，必須先把盤片A及B移到2號柱上。3)當(dāng)把盤片C移到3號盤上后，就可把A、B從2號柱移到3號柱上，以完成問題求解。把原問題分解為三個子問題：1)把盤片A及B移到2號柱雙盤片問題。2)把盤片C移到3號柱單盤片問題。3)把盤片A及B移到3號柱雙盤片問題。其中，子問題1)與子問題3)又分別可分解為三個子問題人工智能之搜索培訓(xùn)講義第21頁例:三階HanoiTower（梵塔）問題定義問題狀態(tài)表示：設(shè)三元組(i,j,k)表示狀態(tài)，其中i表示盤片C所在柱號,j表示盤片B所在柱號；k表示盤片A所在柱號。初始問題可表示為：(1、1．1)(3，3，3)與／或樹表示如圖所表示。(把圖中7個終止節(jié)點(本原問題)按從左至右排列，得到了初始問題解)人工智能之搜索培訓(xùn)講義第22頁2.2.2與或圖表示法基于與或圖表示問題求解算法Step1：確定單個問題描述形式，可采取狀態(tài)空間表示法。Step2：從原始問題開始，逐步進(jìn)行分解和變換，直到本原問題，然后將全部分解和變換過程表示為與或圖。Step3：從端頂點開始，逐步向上回溯，標(biāo)注各頂點為可解或不可解頂點，直到標(biāo)注原始頂點為可解頂點或不可解頂點為止Step4：當(dāng)原始頂點被確定為可解頂點時，輸出對應(yīng)解圖為問題解。人工智能之搜索培訓(xùn)講義第23頁2.3搜索技術(shù)

搜索技術(shù)是人工智能基本技術(shù)之一,在人工智能各應(yīng)用領(lǐng)域中被廣泛地使用。早期人工智能程序與搜索技術(shù)聯(lián)絡(luò)就更為緊密，幾乎全部早期人工智能程序都是以搜索為基礎(chǔ)。比如，A.Newell(艾倫·紐厄爾)和H·A·Simon(西蒙)等人編寫LT(LogicTheorist)程序,J.Slagle寫符號積分程序SAINT,A·Newell和H·A·Simon寫GPS(GeneralProblemSolver)程序,H·Gelernter(格倫特爾)寫Geometrytheorem-provingmachine程序,R.Fikes(菲克斯)和N.Nilsson(尼爾遜)寫STRIPS(StanfordResearchInstituteProblemSolver)程序以及A.Samuel(塞繆爾)寫Chechers程序等,都使用了各種搜索技術(shù)。現(xiàn)在,搜索技術(shù)滲透在各種人工智能系統(tǒng)中,能夠說沒有哪一個人工智能應(yīng)用不用搜索方法,在教授系統(tǒng)、自然語言了解、自動程序設(shè)計、模式識別、機(jī)器人學(xué)、信息檢索和博弈都廣泛使用搜技術(shù)。人工智能之搜索培訓(xùn)講義第24頁2.3搜索技術(shù)

搜索問題是AI關(guān)鍵理論問題之一普通一個問題能夠用好幾個搜索技術(shù)處理,選擇一個好搜索技術(shù)對處理問題效率很相關(guān)系,甚至關(guān)系到求解問題有沒有解。搜索方法好標(biāo)準(zhǔn),普通認(rèn)為有兩個：(1)搜索空間小;(2)解最正確。人工智能之搜索培訓(xùn)講義第25頁2.3搜索技術(shù)

搜索從問題性質(zhì)上來看,可分為普通搜索和博奕搜索,從處理方法上來看,可分為盲目搜索和啟發(fā)式搜索。還能夠分得更細(xì)。當(dāng)所給定問題用狀態(tài)空間表示時,則求解過程可歸結(jié)為對狀態(tài)空間搜索。當(dāng)問題有解時,使用不一樣搜索策略,找到解搜索空間范圍是有區(qū)分。普通來說,對大空間問題,搜索策略是要處理組合爆炸問題人工智能之搜索培訓(xùn)講義第26頁人工智能之搜索培訓(xùn)講義第27頁2.3搜索策略

通常搜索策略主要任務(wù)是確定怎樣選取規(guī)則方式。有兩種基本方式:一個是不考慮給定問題所含有特定知識,系統(tǒng)依據(jù)事先確定好某種固定排序,依次調(diào)用規(guī)則或隨機(jī)調(diào)用規(guī)則,這實際上是盲目搜索方法,普通統(tǒng)稱為無信息引導(dǎo)搜索策略。另一個是考慮問題領(lǐng)域可應(yīng)用知識,動態(tài)地確定規(guī)則排序,優(yōu)先調(diào)用較適當(dāng)規(guī)則使用,這就是通常稱為啟發(fā)式搜索策略或有信息引導(dǎo)搜索策略。人工智能之搜索培訓(xùn)講義第28頁AI領(lǐng)域搜索方法(1)求任一解路搜索策略回溯法(Backtracking)爬山法(HillClimbing)寬度優(yōu)先法(Breadth-first)深度優(yōu)先法(Depth-first)限定范圍搜索法(BeamSearch)最正確優(yōu)先法(Best-first)(2)求最正確解路搜索策略大英博物館法(BritishMuseum)分枝界限法(BranchandBound)動態(tài)規(guī)劃法(DynamicProgramming)最正確圖搜索法(A*)人工智能之搜索培訓(xùn)講義第29頁AI領(lǐng)域搜索方法(3)求與或關(guān)系解圖搜索法普通與或圖搜索法(AO*)

極小極大法(Minimax)剪枝法(Alpha-betaPruning)

啟發(fā)式剪枝法(HeuristicPruning)人工智能之搜索培訓(xùn)講義第30頁搜索策略分類人工智能之搜索培訓(xùn)講義第31頁盲目搜索方法盲目搜索是不利用問題相關(guān)信息,而依據(jù)事先確定好某種固定搜索方法進(jìn)行搜索。經(jīng)典盲目搜索方法是深度優(yōu)先搜索和寬度優(yōu)先搜索(亦稱廣度優(yōu)先搜索),這是兩處基本搜索方法人工智能之搜索培訓(xùn)講義第32頁回溯策略例：皇后問題在一個4×4國際象棋棋盤上,一次一個地擺布四枚皇后棋子,擺好后要滿足每行、每列和對象線上只允許出現(xiàn)一枚棋子,即棋子間不許相互俘獲人工智能之搜索培訓(xùn)講義第33頁()人工智能之搜索培訓(xùn)講義第34頁()Q((1,1))人工智能之搜索培訓(xùn)講義第35頁()QQ((1,1))((1,1)(2,3))人工智能之搜索培訓(xùn)講義第36頁()Q((1,1))((1,1)(2,3))人工智能之搜索培訓(xùn)講義第37頁()QQ((1,1))((1,1)(2,3))((1,1)(2,4))人工智能之搜索培訓(xùn)講義第38頁()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))人工智能之搜索培訓(xùn)講義第39頁()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))人工智能之搜索培訓(xùn)講義第40頁()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))人工智能之搜索培訓(xùn)講義第41頁()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))人工智能之搜索培訓(xùn)講義第42頁()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))人工智能之搜索培訓(xùn)講義第43頁()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))人工智能之搜索培訓(xùn)講義第44頁()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))人工智能之搜索培訓(xùn)講義第45頁()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))人工智能之搜索培訓(xùn)講義第46頁遞歸思想從前有座山……

從前有座山……

從前有座山……人工智能之搜索培訓(xùn)講義第47頁Fibonacci數(shù)列12，意大利家斐波那契在提出了一個關(guān)于兔子繁殖問題：

假如一對兔子每個月能生一對小兔（一雄一雌），而每對小兔在它出生後第三個月里，又能開始生一對小兔，假定在

不發(fā)生死亡情況下，由一對出生小兔開始，50個月后會有多少對兔子？人工智能之搜索培訓(xùn)講義第48頁當(dāng)n＞1時，F(xiàn)n+2=Fn+1+Fn，而F0=F1=1。人工智能之搜索培訓(xùn)講義第49頁遞歸思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g人工智能之搜索培訓(xùn)講義第50頁回溯搜索算法 BACKTRACK（DATA）

DATA：當(dāng)前狀態(tài)。 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)路徑 （以規(guī)則表形式表示） 或FAIL。人工智能之搜索培訓(xùn)講義第51頁回溯搜索算法遞歸過程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;2, IFDEADEND(DATA)RETURNFAIL;3, RULES:=APPRULES(DATA);4, LOOP:IFNULL(RULES)RETURNFAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R,DATA);8, PATH:=BACKTRACK(RDATA);9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);人工智能之搜索培訓(xùn)講義第52頁存在問題及處理方法問題：深度問題死循環(huán)問題處理方法：對搜索深度加以限制統(tǒng)計從初始狀態(tài)到當(dāng)前狀態(tài)路徑人工智能之搜索培訓(xùn)講義第53頁回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：從初始到當(dāng)前狀態(tài)表（逆向） 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)路徑 （以規(guī)則表形式表示） 或FAIL。人工智能之搜索培訓(xùn)講義第54頁回溯搜索算法11, DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL;

3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;6, RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);人工智能之搜索培訓(xùn)講義第55頁回溯搜索算法1（續(xù)）9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);人工智能之搜索培訓(xùn)講義第56頁一些深入問題失敗原因分析、多步回溯QQ人工智能之搜索培訓(xùn)講義第57頁一些深入問題（續(xù)）回溯搜索中知識利用 基本思想： 盡可能選取劃去對角線上位置數(shù)最少。QQQQ4334人工智能之搜索培訓(xùn)講義第58頁

圖搜索策略問題引出回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)一條路徑。圖搜索：保留全部已經(jīng)搜索過路徑。

人工智能之搜索培訓(xùn)講義第59頁一些基本概念節(jié)點深度： 根節(jié)點深度=0

其它節(jié)點深度=父節(jié)點深度+10123人工智能之搜索培訓(xùn)講義第60頁一些基本概念（續(xù)1）路徑 設(shè)一節(jié)點序列為(n0,n1,…,nk)，對于i=1,…,k，若節(jié)點ni-1含有一個后繼節(jié)點ni，則該序列稱為從n0到nk路徑。路徑耗散值 一條路徑耗散值等于連接這條路徑各節(jié)點間全部耗散值總和。用C(ni,nj)表示從ni到nj路徑耗散值。人工智能之搜索培訓(xùn)講義第61頁一些基本概念（續(xù)1）擴(kuò)展一個節(jié)點 生成出該節(jié)點全部后繼節(jié)點，并給出它們之間耗散值。這一過程稱為“擴(kuò)展一個節(jié)點”。人工智能之搜索培訓(xùn)講義第62頁圖搜索普通過程(1)建立一個只含有起始節(jié)點S搜索圖G，把S放到一個叫做OPEN未擴(kuò)展節(jié)點表中（簡稱OPEN表）。(2)建立一個叫做CLOSED已擴(kuò)展節(jié)點表（簡稱CLOSED表），其初始為空表。(3)LOOP：若OPEN表是空表，則失潰退出。(4)選擇OPEN表上第一個節(jié)點，把它從OPEN表移出并放進(jìn)CLOSED表中。稱此節(jié)點為節(jié)點n，它是CLOSED表中節(jié)點編號。(5)若n為一目標(biāo)節(jié)點，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到(指針將在第7步中設(shè)置)。人工智能之搜索培訓(xùn)講義第63頁

(6)擴(kuò)展節(jié)點n，同時生成不是n祖先那些后繼節(jié)點集合M。把M這些組員作為n后繼節(jié)點添入圖G中。(7)對那些未曾在G中出現(xiàn)過(既未曾在OPEN表上或CLOSED表上出現(xiàn)過)M組員設(shè)置一個通向n指針。把M這些組員加進(jìn)OPEN表。對已經(jīng)在OPEN或CLOSED表上每一個M組員，確定是否需要更改通到n指針方向。對已在CLOSED表上每個M組員，確定是否需要更改圖G中通向它每個后代節(jié)點指針方向。(8)按某一任意方式或按某個探試值，重排OPEN表。(9)GOLOOP。人工智能之搜索培訓(xùn)講義第64頁OPEN表節(jié)點父節(jié)點CLOSED表標(biāo)號節(jié)點父節(jié)點OPEN表節(jié)點父節(jié)點編號CLOSED表編號節(jié)點父節(jié)點編號人工智能之搜索培訓(xùn)講義第65頁例子例子：從某王姓家族四代中找王A后代且其壽命為X人。

王A：壽命47，有兒子王B1、王B3、王B2王B1：壽命77，有兒子王C1、王C2王B3：壽命52，有兒子王D1王B2：壽命65，有兒子王E1、王E2王F1：壽命32王G1：壽命96王C2：壽命87，有兒子王F1王D1：壽命77，沒有兒子王E1：壽命57，有兒子王G1王E2：壽命92，有兒子王H1王C1：壽命27，沒有兒子王H1：壽命51若X=57，怎樣尋找？人工智能之搜索培訓(xùn)講義第66頁問題搜索樹人工智能之搜索培訓(xùn)講義第67頁深度優(yōu)先搜索搜索過程無信息圖搜索過程—深度優(yōu)先人工智能之搜索培訓(xùn)講義第68頁重排九宮深度優(yōu)先只是搜索樹一部分，還未抵達(dá)目標(biāo)節(jié)點，仍需繼續(xù)往下搜索。人工智能之搜索培訓(xùn)講義第69頁有界深度優(yōu)先搜索搜索過程假如問題有解，且其路徑長度<=dm，則上述搜索過程一定能求得解。不過，若解路徑長度>dm，則搜索過程就得不到解。----深度界限選擇很主要。人工智能之搜索培訓(xùn)講義第70頁有界深度優(yōu)先搜索設(shè)深度界度dm=4，有界深度優(yōu)先搜索求解圖以下，解路徑為S020252628(Sg)人工智能之搜索培訓(xùn)講義第71頁深度優(yōu)先搜索性質(zhì)普通不能確保找到最優(yōu)解當(dāng)深度限制不合理時，可能找不到解，能夠?qū)⑺惴ǜ臑榭勺兩疃认拗谱顗那闆r時，搜索空間等同于窮舉與回溯法差異：圖搜索是一個通用與問題無關(guān)方法人工智能之搜索培訓(xùn)講義第72頁無信息圖搜索過程—寬度優(yōu)先寬度優(yōu)先搜索過程：(1)把起始節(jié)點放到OPEN表中(假如該起始節(jié)點為一目標(biāo)節(jié)點，則求得一個解答)。(2)假如OPEN是個空表，則沒有解，失潰退出；不然繼續(xù)。(3)把OPEN表中第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED擴(kuò)展節(jié)點表中。(4)考查節(jié)點n是否為目標(biāo)節(jié)點，若是則求得問題解，退出，(5)若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第(2)步。(6)擴(kuò)展節(jié)點n。將其全部后繼節(jié)點放到OPEN表末端，并為每個后續(xù)節(jié)點都配置指向n指針。然后轉(zhuǎn)向第(2)步。人工智能之搜索培訓(xùn)講義第73頁寬度優(yōu)先人工智能之搜索培訓(xùn)講義第74頁重排九宮寬度優(yōu)先解路徑：S0381626人工智能之搜索培訓(xùn)講義第75頁寬度優(yōu)先搜索性質(zhì)只要問題有解，一定能找到解，而且得到是路徑最短解。盲目性較大，當(dāng)目標(biāo)節(jié)點距離初始節(jié)點較遠(yuǎn)時將會產(chǎn)生許多無用節(jié)點，所以搜索效率低。方法與問題無關(guān)，含有通用性屬于圖搜索方法人工智能之搜索培訓(xùn)講義第76頁非啟發(fā)式搜索按照事先要求路線進(jìn)行搜索廣度優(yōu)先搜索是按“層”進(jìn)行搜索，先進(jìn)入OPEN表節(jié)點先被考查深度優(yōu)先搜索是沿著縱深方向進(jìn)行搜索，后進(jìn)入OPEN表節(jié)點先被考查按已經(jīng)付出代價決定下一步要搜索節(jié)點（為樹中每條邊賦予代價，廣度及深度優(yōu)先搜索實質(zhì)是每條邊代價都為1）代價樹廣度優(yōu)先代價樹深度優(yōu)先人工智能之搜索培訓(xùn)講義第77頁代價樹寬度憂先搜索邊上標(biāo)有代價(或費用)樹稱為代價樹。在代價樹中，若用g(x)表示從初姑節(jié)點S0到節(jié)點x代價，用c(xl,x2)表示從父節(jié)點x1到子節(jié)點x2代價，則有：g(x2)=g(x1)+c(x1,x2)

代價樹寬度優(yōu)先搜索基本思想是：OPEN表中節(jié)點在任一時刻都是按其代價從小到大排序，每次擴(kuò)展時總是從OPEN表中選取代價最小節(jié)點進(jìn)行擴(kuò)展。其搜索過程以下：人工智能之搜索培訓(xùn)講義第78頁五城市間交通路線圖，A城市是出發(fā)地，E城市是目標(biāo)地，兩城市間交道費用(代價)如左圖小數(shù)字所表示。求從A到E最小費用交通路線。交通代價樹如右圖，解為ACDE代價樹寬度優(yōu)先搜索舉例人工智能之搜索培訓(xùn)講義第79頁代價樹深度憂先搜索代價樹寬度優(yōu)先搜索中，每次擴(kuò)展時總是從OPEN表中選取代價最小節(jié)點進(jìn)行擴(kuò)展。而代價樹深度優(yōu)先搜索是從剛擴(kuò)展出子節(jié)點中選一個代價最小節(jié)點送入CLOSE表中進(jìn)行考查。其搜索過程以下：解也為ACDE人工智能之搜索培訓(xùn)講義第80頁啟發(fā)式圖搜索利用知識來引導(dǎo)搜索，到達(dá)降低搜索范圍，降低問題復(fù)雜度目標(biāo)。啟發(fā)性信息用于指導(dǎo)搜索過程，且與詳細(xì)問題求解相關(guān)控制性信息稱為啟發(fā)性信息啟發(fā)信息強(qiáng)度強(qiáng)：降低搜索工作量，但可能造成找不到最 優(yōu)解弱：普通造成工作量加大，極限情況下變?yōu)?盲目搜索，但可能能夠找到最優(yōu)解人工智能之搜索培訓(xùn)講義第81頁希望：引入啟發(fā)知識，在確保找到最正確解情況下，盡可能降低搜索范圍，提升搜索效率。人工智能之搜索培訓(xùn)講義第82頁基本思想定義一個評價函數(shù)f，對當(dāng)前搜索狀態(tài)進(jìn)行評定，找出一個最有希望節(jié)點來擴(kuò)展。人工智能之搜索培訓(xùn)講義第83頁1，啟發(fā)式搜索算法A（A算法）評價函數(shù)格式：

f(n)=g(n)+h(n) f(n)：評價函數(shù)

g(n):實際已經(jīng)付出代價函數(shù)

h(n)：啟發(fā)函數(shù)人工智能之搜索培訓(xùn)講義第84頁符號意義g*(n)：從s(初始狀態(tài)S0)到n(當(dāng)前狀態(tài)Sn)最短路徑耗散值h*(n)：從n到g(目標(biāo)狀態(tài)Sg)最短路徑耗散值f*(n)=g*(n)+h*(n)：從s經(jīng)過n到g最短路徑耗散值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)預(yù)計值人工智能之搜索培訓(xùn)講義第85頁一個A算法例子定義評價函數(shù)：

f(n)=g(n)+h(n) g(n)為從初始節(jié)點到當(dāng)前節(jié)點耗散值,即頂點Sn在狀態(tài)空間中深度(從根頂點到Sn所經(jīng)歷層次數(shù))。

h(n)為當(dāng)前節(jié)點“不在位”將牌數(shù) 2831647512384765人工智能之搜索培訓(xùn)講義第86頁h計算舉例 h(n)=42

831

647512345768人工智能之搜索培訓(xùn)講義第87頁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)目標(biāo)123456g=0,h=4f=0+4=4g=1,h=5f=1+5=6g=0g=1g=2g=3人工智能之搜索培訓(xùn)講義第88頁最正確圖搜索算法A*（A*算法）在A算法中，假如滿足條件：

h(n)≤h*(n)

則A算法稱為A*算法。其中h*(n)是從頂點Sn到Sg最小代價。因為h*(n)最小代價通常不知道，所以用h(n)（不在位將牌數(shù)）進(jìn)行代價預(yù)計，所以可得h(n)<h*(n),所以上例是A*算法。人工智能之搜索培訓(xùn)講義第89頁A*條件舉例8數(shù)碼問題h(n)=“不在位”將牌數(shù)=f1h(n)=將牌“不在位”距離和=f2采取f2算法效率會高于f1算法，因為f2>=f12

831

647512345768將牌1：1將牌2：1將牌6：1將牌8：2人工智能之搜索培訓(xùn)講義第90頁A*算法性質(zhì)定理1： 對有限圖，假如從初始節(jié)點s到目標(biāo)節(jié)點t有路徑存在，則算法A一定成功結(jié)束。人工智能之搜索培訓(xùn)講義第91頁AO*算法是A*算法在與或圖上擴(kuò)展算法。AO*算法中因為與節(jié)點存在，解對應(yīng)不是一條路徑，而是一個子圖，所以對頂點評定實際上是對局部解圖評價。與節(jié)點代價計算：最大代價和代價或節(jié)點代價計算：最小代價AO*算法人工智能之搜索培訓(xùn)講義第92頁AO*算法舉例7=3+1(左樹)+2+18=3+1+3+18=min(8+1,7+1)人工智能之搜索培訓(xùn)講義第93頁與或樹寬度優(yōu)先與深度優(yōu)先搜索寬度優(yōu)先：12345深度優(yōu)先：13B524人工智能之搜索培訓(xùn)講義第94頁問題圖搜索是針對什么知識表示方法問題求解方法？什么是圖搜索?其中，重排OPEN表意味著什么，重排標(biāo)準(zhǔn)是什么?寬度優(yōu)先搜索方法中OPEN表需要按什么方式進(jìn)行操作 A．先進(jìn)后出B．先進(jìn)先出有界深度優(yōu)先搜索方法能夠確保在搜索樹中找到一條通向目標(biāo)節(jié)點最短路徑嗎？試比較各種盲目搜索搜索方法效率，找出影響算法效率原因試比較寬度優(yōu)先搜索、有界深度優(yōu)先搜索及有序搜索搜索效率，并以實例數(shù)據(jù)加以說明人工智能之搜索培訓(xùn)講義第95頁啟發(fā)式搜索必要性

現(xiàn)實困難迫使人們轉(zhuǎn)而求援于啟發(fā)式算法。這種算法本質(zhì)是部分地放棄算法“普通化,通用化”概念,把所要解問題詳細(xì)領(lǐng)域知識加進(jìn)算法中去,以提升算法效率。如,廣度優(yōu)先法幾乎能夠用于解一切搜索問題：九宮圖(八數(shù)碼難題),hanoi塔(焚塔問題),旅行推銷員,華容道,以至魔方等等。但實際使用時,效率可能低得驚人,甚至根本解不出來(比如魔方問題)。假如我們?yōu)槊款悊栴}找出一些特殊規(guī)則,和廣度優(yōu)先法配合起來使用,那結(jié)果就可能完全不一樣了。人工智能之搜索培訓(xùn)講義第96頁啟發(fā)式搜索必要性依據(jù)啟發(fā)信息,在生成各種搜索樹時能夠考慮種種可能選擇,如:1.下一步展開哪個節(jié)點?2.是部分展開還是完全展開?3.使用哪個規(guī)則(或算子)?4.怎樣決定舍棄還是保留新生成節(jié)點?5.怎樣決定舍棄還是保留一棵子樹?6.怎樣決定停頓或繼續(xù)搜索?7.怎樣定義啟發(fā)函數(shù)(評價函數(shù))?8.怎樣決定搜索方向?……

因為這些選擇不一樣,就得到了不一樣啟發(fā)式算法人工智能之搜索培訓(xùn)講義第97頁*解路徑如粗線所標(biāo)左、上、右、下**S、A、B、…、L、M等為狀態(tài)空間圖中各個節(jié)點名,其后小括號中數(shù)字表示該節(jié)點評價函數(shù)f(n)預(yù)計值,比如S(4)、L(5)等。

***圖中標(biāo)識"▲"節(jié)點為被擴(kuò)節(jié)點,標(biāo)識"■"節(jié)點為生成節(jié)點。

九宮重排問題人工智能之搜索培訓(xùn)講義第98頁搜索效率比較人工智能之搜索培訓(xùn)講義第99頁啟發(fā)式搜索策略

人工智能問題求解者在兩種基本情況下利用啟發(fā)式策略:一個問題因為在問題陳說和數(shù)據(jù)獲取方面固有含糊性可能使它沒有一個確定解。醫(yī)療診療即是一例。所給出一系列癥狀可能有多個原因,醫(yī)生利用啟發(fā)式搜索來選擇最有可能論斷并依此產(chǎn)生治療計劃。一個問題可能有確定解,不過求解過程中計算機(jī)代價令人難以接收。在很多問題(如國際象棋)中,狀態(tài)空間增加尤其快,可能狀態(tài)數(shù)伴隨搜索深度呈指數(shù)級增加、分解。在這種情況下,窮盡式搜索策略諸如深度優(yōu)先或廣度優(yōu)先搜索,在一個給定較實際時空內(nèi)很可能得不到最終解和創(chuàng)造創(chuàng)造全部規(guī)則一樣,啟發(fā)式策略也是極易犯錯人工智能之搜索培訓(xùn)講義第100頁圖搜索策略圖搜索策略定義圖搜索策略可看作一個在圖中尋找路徑方法。初始節(jié)點和目標(biāo)節(jié)點分別代表初始數(shù)據(jù)庫和滿足終止條件數(shù)據(jù)庫。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫規(guī)則序列問題就等價于求得圖中一條路徑問題。研究圖搜索普通策略，能夠給出圖搜索過程普通步驟。圖搜索算法中幾個主要名詞術(shù)語（1）OPEN表與CLOSE表（2）搜索圖與搜索樹人工智能之搜索培訓(xùn)講義第101頁你可曾聽說過“深藍(lán)”？1997年5月11日，IBM開發(fā)“深藍(lán)”擊敗了國際象棋冠軍卡斯帕羅夫。1980年他取得世界少年組冠軍

1982年他并列奪得蘇聯(lián)冠軍

1985年22歲卡斯帕羅夫成為歷史上最年輕國際象棋冠軍積分是2849，這一分?jǐn)?shù)是有史以來最高分。遠(yuǎn)遠(yuǎn)領(lǐng)先于第二位克拉姆尼克2770

卡氏何許人也？人工智能之搜索培訓(xùn)講義第102頁人工智能之搜索培訓(xùn)講義第103頁電腦棋手：永不停歇挑戰(zhàn)！1988年“深思”擊敗了丹麥特級大師拉森。1993年“深思”第二代擊敗了丹麥?zhǔn)澜鐑?yōu)異女棋手小波爾加。人工智能之搜索培訓(xùn)講義第104頁電腦棋手：永不停歇挑戰(zhàn)！“更弗里茨”擊敗了除了克拉姆尼克之外全部排名世界前十位棋手。年10月“更弗里茨”與世界棋王克拉姆尼克在巴林交手，雙方以4比4戰(zhàn)平。201至2月“更年少者”與卡斯帕羅夫在紐約較量，3比3戰(zhàn)平。人工智能之搜索培訓(xùn)講義第105頁許多人在努力

人工智能之搜索培訓(xùn)講義第106頁機(jī)器博弈20世紀(jì)50年代，有些人構(gòu)想利用機(jī)器智能來實現(xiàn)機(jī)器與人對弈。1997年IBM“深藍(lán)”戰(zhàn)勝了國際象棋世界冠軍卡斯帕羅夫，驚動了世界。加拿大阿爾伯塔大學(xué)奧賽羅程序Logistello和西洋跳棋程序Chinook也相繼成為確定、二人、零和、完備信息游戲世界冠軍西洋雙陸棋這么存在非確定原因棋類也有了美國卡內(nèi)基梅隆大學(xué)西洋雙陸琪程序BKG這么世界冠軍。對圍棋、中國象棋、橋牌、撲克等許各種其它種類游戲博弈研究也正在進(jìn)行中。人工智能之搜索培訓(xùn)講義第107頁機(jī)器博弈基本思想機(jī)器博弈關(guān)鍵思想就是對博弈樹節(jié)點估值過程和對博弈樹搜索過程結(jié)合人工智能之搜索培訓(xùn)講義第108頁博弈樹在博弈任何一個中間階段，站在博弈雙方其中一方立場上，能夠構(gòu)想一個博弈樹。這個博弈樹根節(jié)點是當(dāng)前時刻棋局，它兒子節(jié)點是假設(shè)再行棋一步以后各種棋局，孫子節(jié)點是從兒子節(jié)點棋局再行棋一步各種棋局，以這類推，結(jié)構(gòu)整棵博弈樹，直到能夠分出勝敗棋局。人工智能之搜索培訓(xùn)講義第109頁機(jī)器博弈系統(tǒng)組成知識表示規(guī)則集，產(chǎn)生機(jī)制，構(gòu)建博弈樹搜索技術(shù)估值技術(shù)人工智能之搜索培訓(xùn)講義第110頁博弈搜索博弈搜索基本思想已經(jīng)提出半個多世紀(jì)，當(dāng)前廣泛研究是確定、二人、零和、完備信息博弈搜索。沒有隨機(jī)原因博弈在兩個人之間進(jìn)行，在任何一個時刻，一方失去利益即為另一方得到利益，不會出現(xiàn)“雙贏”局面，而且在任何時刻，博弈雙方都明確知道每一個棋子是否存在和存在于哪里。二人、零和、完備信息博弈搜索理論已經(jīng)很系統(tǒng)。極大極小算法是全部搜索算法基礎(chǔ)。一類是作為主流深度優(yōu)先alpha-beta搜索及其系列增強(qiáng)算法另一類是最正確優(yōu)先系列算法。人工智能之搜索培訓(xùn)講義第111頁解謎：電腦是怎樣下棋

——人機(jī)博弈程序普通設(shè)計方法以中國棋為例人工智能之搜索培訓(xùn)講義第112頁（1）第一步該做什么？數(shù)據(jù)結(jié)構(gòu)選取——棋盤表示占用空間-〉少操作速度-〉快是否方便-〉方便在機(jī)器中表示棋局，讓程序知道博弈狀態(tài)。人工智能之搜索培訓(xùn)講義第113頁九列十行十四種不一樣棋子三十二個棋子人工智能之搜索培訓(xùn)講義第114頁幾個棋盤表示方式二維數(shù)組——直觀

緊湊數(shù)據(jù)結(jié)構(gòu)——省空間，不直觀，速度?

比特棋盤——用于8*8棋盤（國際象棋），64位主機(jī)人工智能之搜索培訓(xùn)講義第115頁（2）接下來怎么辦？產(chǎn)生正當(dāng)走步規(guī)則，使博弈能公正進(jìn)行，而且能夠判斷對手是否亂走。依賴于詳細(xì)棋類特征。是一段將局面全部可能正確走法羅列出來程序。稱之為走法產(chǎn)生。人工智能之搜索培訓(xùn)講義第116頁幾個走法產(chǎn)生實現(xiàn)方式普通做法

建立小型數(shù)據(jù)庫

位運(yùn)算人工智能之搜索培訓(xùn)講義第117頁位運(yùn)算走法產(chǎn)生之例尋找象可走步人工智能之搜索培訓(xùn)講義第118頁位運(yùn)算走法產(chǎn)生之要求一個基于比特棋盤完善數(shù)據(jù)庫該數(shù)據(jù)庫應(yīng)位于內(nèi)存中人工智能之搜索培訓(xùn)講義第119頁（3）終于到關(guān)鍵了從全部走法中找出最正確走法，也就是——搜索人工智能之搜索培訓(xùn)講義第120頁博弈概述諸以下棋、打牌、競技、戰(zhàn)爭等一類競爭性智能活動稱為博弈。博弈有很各種，我們討論最簡單"二人零和、全信息、非偶然"博弈，其特征以下：

(1)對壘MAX、MIN雙方輪番采取行動，博弈結(jié)果只有三種情況：MAX方勝，MIN方敗；MIN方勝，MAX方??；和局。

(2)在對壘過程中，任何一方都了解當(dāng)前格局及過去歷史。

(3)任何一方在采取行動前都要依據(jù)當(dāng)前實際情況，進(jìn)行得失分析，選取對自已為最有利而對對方最為不利對策，不存在擲骰子之類"碰運(yùn)氣"原因。即雙方都是很理智地決定自己行動。

人工智能之搜索培訓(xùn)講義第121頁博弈概述在博弈過程中，任何一方都希望自己取得勝利。所以，當(dāng)某一方當(dāng)前有多個行動方案可供選擇時，他總是挑選對自己最為有利而對對方最為不利那個行動方案。此時，假如我們站在MAX方立場上，則可供MAX方選擇若干行動方案之間是"或"關(guān)系，因為主動權(quán)操在MAX方手里，他或者選擇這個行動方案，或者選擇另一個行動方案，完全由MAX方自已決定。當(dāng)MAX方選取任一方案走了一步后，MIN方也有若干個可供選擇行動方案，此時這些行動方案對MAX方來說它們之間則是"與"關(guān)系，因為這時主動權(quán)操在MIN方手里，這些可供選擇行動方案中任何一個都可能被MIN方選中，MAX方必須應(yīng)付每一個情況發(fā)生。人工智能之搜索培訓(xùn)講義第122頁博弈概述這么，假如站在某一方(如MAX方，即MAX要取勝)，把上述博弈過程用圖表示出來，則得到是一棵"與或樹"。描述博弈過程與或樹稱為博弈樹，它有以下特點：

(1)博弈初始格局是初始節(jié)點。

(2)在博弈樹中，"或"節(jié)點和"與"節(jié)點是逐層交替出現(xiàn)。自己一方擴(kuò)展節(jié)點之間是"或"關(guān)系，對方擴(kuò)展節(jié)點之間是"與"關(guān)系。雙方輪番地擴(kuò)展節(jié)點。

(3)全部自己一方獲勝終局都是本原問題，對應(yīng)節(jié)點是可解節(jié)點；全部使對方獲勝終局都認(rèn)為是不可解節(jié)點。

我們假定MAX先走，處于奇數(shù)深度級節(jié)點都對應(yīng)下一步由MAX走，這些節(jié)點稱為MAX節(jié)點，對應(yīng)地偶數(shù)級為MIN節(jié)點。

人工智能之搜索培訓(xùn)講義第123頁搜索算法極大極小值算法

負(fù)極大值搜索深度優(yōu)先alpha-beta搜索渴望搜索（AspirationSearch）極小窗口搜索（MinimalWindowSearch）遍歷深化（IterativeDeepening）歷史啟發(fā)搜索（HistoryHeuristic）殺手啟發(fā)搜索(KillerHeuristic)

MTD(f)算法（Memory–enhancedTestDriverwithfandn）人工智能之搜索培訓(xùn)講義第124頁極大極小法基本思想或算法：(1)設(shè)博弈雙方中一方為MAX，另一方為MIN。然后為其中一方(比如MAX)尋找一個最優(yōu)行動方案。(2)為了找到當(dāng)前最優(yōu)行動方案，需要對各個可能方案所產(chǎn)生后果進(jìn)行比較,詳細(xì)地說，就是要考慮每一方案實施后對方可能采取全部行動，并計算可能得分。(3)為計算得分，需要依據(jù)問題特征信息定義一個估價函數(shù)，用來估算當(dāng)前博弈樹端節(jié)點得分。此時估算出來得分稱為靜態(tài)估值。(4)當(dāng)端節(jié)點估值計算出來后，再推算出父節(jié)點得分，推算方法是：對“或”節(jié)點，選其子節(jié)點中一個最大得分作為父節(jié)點得分，這是為了使自己在可供選擇方案中選一個對自己最有利方案；對“與”節(jié)點，選其子節(jié)點中一個最小得分作為父節(jié)點得分，這是為了立足于最壞情況。這么計算出父節(jié)點得分稱為倒推值。(5)假如一個行動方案能取得較大倒推值，則它就是當(dāng)前最好行動方案。人工智能之搜索培訓(xùn)講義第125頁極大極小倒推值計算A是與節(jié)點，從下往上能夠倒推出S0預(yù)計值人工智能之搜索培訓(xùn)講義第126頁一字棋游戲極小極大分析法設(shè)有九個空格，由MAX，MIN二人對弈，輪到誰走棋誰就往空格上放一只自己棋子，誰先使自己棋子組成“三子成一線”(同一行或列或?qū)蔷€全是某人棋子)，誰就取得了勝利。用叉號表示MAX，用圓圈代表MIN。人工智能之搜索培訓(xùn)講義第127頁一字棋游戲極小極大分析法為了不致于生成太大博弈樹，假設(shè)每次僅擴(kuò)展兩層。估價函數(shù)定義以下設(shè)棋局為P，估價函數(shù)為e(P)(1)若P對任何一方來說都不是獲勝位置，則e(P)=e(那些仍為MAX空著完全行、列或?qū)蔷€總數(shù))-e(那些仍為MIN空著完全行、列或?qū)蔷€總數(shù))(2)若P是MAX必勝棋局，則e(P)＝+∞。(3)若P是B必勝棋局，則e(P)＝-∞。

人工智能之搜索培訓(xùn)講義第128頁一字棋游戲極小極大分析法集中經(jīng)典棋局得分值h(n)計算：(a)h(n)=4-2=2(b)是和局，h(n)=0(c)×方獲勝，h(n)=+∞(d)○方獲勝，h(n)=-∞人工智能之搜索培訓(xùn)講義第129頁一字棋游戲極小極大分析法第一回合擴(kuò)展深度為2人工智能之搜索培訓(xùn)講義第130頁人工智能之搜索培訓(xùn)講義第131頁一字棋極大極小法第一階段人工智能之搜索培訓(xùn)講義第132頁一字棋極大極小法第二階段人工智能之搜索培訓(xùn)講義第133頁一字棋極大極小法第三階段人工智能之搜索培訓(xùn)講義第134頁Alpha-Beta剪枝技術(shù)極大極小搜索要求先生成與／或樹，然后再計算各節(jié)點估值，需要生成要求深度內(nèi)全部節(jié)點，所以搜索效率較低。基本思想或算法是，邊生成博弈樹邊計算評定各節(jié)點倒推值，而且依據(jù)評定出倒推值范圍，及時停頓擴(kuò)展那些已無必要再擴(kuò)展子節(jié)點，即相當(dāng)于剪去了博弈樹上一些分枝，從而節(jié)約了機(jī)器開銷，提升了搜索效率。人工智能之搜索培訓(xùn)講義第135頁Alpha-Beta剪枝技術(shù)(1)對于一個與節(jié)點MIN，若能預(yù)計出其倒推值上確界β，而且這個β值小于MIN父節(jié)點(一定是或節(jié)點)預(yù)計倒推值下確界α，即α≥β，則就無須再擴(kuò)