人工智能導(dǎo)論第二章搜索與問第1頁，課件共163頁，創(chuàng)作于2023年2月第二章搜索、問題求解與博弈問題求解能力是人類智能的基本組成部分，研究并實(shí)現(xiàn)問題求解是人工智能的重要研究內(nèi)容之一。知識（問題）的表示是問題求解的基礎(chǔ)，兩種普遍采用的問題表示方法：狀態(tài)空間表示與或圖表示搜索（優(yōu)化）：在問題表示基礎(chǔ)上，在合理的時間范圍內(nèi)，從問題所有可能的解中找到一個最優(yōu)解或可行解，是問題求解中的核心技術(shù)。啟發(fā)式搜索----人工智能的本質(zhì)特征之一。計算機(jī)博弈涉及問題表示、搜索技術(shù)等AI核心問題，現(xiàn)有的計算機(jī)博弈本質(zhì)上是將博弈問題轉(zhuǎn)變?yōu)橐粋€與或圖搜索問題進(jìn)行處理。第2頁，課件共163頁，創(chuàng)作于2023年2月主要內(nèi)容2.1搜索概述2.2問題求解2.2.1狀態(tài)空間2.2.2與或圖2.3搜索技術(shù)圖搜索2.4機(jī)器博弈第3頁，課件共163頁，創(chuàng)作于2023年2月一些例子搭積木智力游戲：有一個農(nóng)夫帶一條狼、一只羊和一筐菜要從河的左岸乘船到右岸，但受下列條件限制：船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河沒有農(nóng)夫看管，則狼要吃羊，羊要吃菜請?jiān)O(shè)計一個過河方案，使得農(nóng)夫、狼、羊、菜都不能受損地過河。類似問題：野人和傳教士問題下棋（撲克、西洋跳棋、國際象棋、象棋等）（屬于博弈）第4頁，課件共163頁，創(chuàng)作于2023年2月2.1搜索概述人工智能的多個研究領(lǐng)域從求解現(xiàn)實(shí)問題的過程來看，都可抽象為一個“問題求解”過程問題求解過程實(shí)際上就是一個搜索過程最優(yōu)性和計算法復(fù)雜性是搜素中的一對矛盾，搜索必須考慮的三個問題：采用盲目搜索還是啟發(fā)式搜索盲目搜索：不考慮問題本身的特性，通過遍歷問題解的集合來尋找可行解或最優(yōu)解。啟發(fā)式搜索：利用與問題有關(guān)的啟發(fā)式信息來確定搜索方向，以加快搜索過程。進(jìn)行局部搜索還是全集搜索搜索可行解還是最優(yōu)解第5頁，課件共163頁，創(chuàng)作于2023年2月2.1搜索概述評價一個搜索算法的因素：完備性：如果問題有解，一定能找到一個解最優(yōu)性：如果問題存在最優(yōu)解，則一定能找到這個最優(yōu)解復(fù)雜性：時間和空間復(fù)雜性，在保證最優(yōu)性和完備性的前提下，算法的復(fù)雜性越小越好。目前的搜索算法還不能同時滿足以上三個要求。為了進(jìn)行搜索，首先必須用某種形式把問題表示出來：狀態(tài)空間表示法和與或圖表示法就是用來表示問題及其搜索過程的兩種常用方法。第6頁，課件共163頁，創(chuàng)作于2023年2月2.2問題求解狀態(tài)空間表示法和與或圖表示法不僅是問題表示的方法，也分別代表了兩種問題求解的思路狀態(tài)空間將問題求解所涉及的每個可能的步驟表示成一個狀態(tài)，全部狀態(tài)以及狀態(tài)之間的所有轉(zhuǎn)換構(gòu)成一個以圖的形式表示的狀態(tài)空間。問題的求解過程是在狀態(tài)空間中搜索一條最優(yōu)的或可行的從初始狀態(tài)到目標(biāo)狀態(tài)的路徑的過程。與或圖表示法的基礎(chǔ)是問題歸約，通過一系列分解或變換，將復(fù)雜問題逐步轉(zhuǎn)化為比較簡單的問題，直至可以直接求解的本原問題。與或圖的求解過程是在與或圖中搜索一個將原始問題變換為簡單問題在變換為本原問題的、最優(yōu)的或可行的歸約步驟的過程。第7頁，課件共163頁，創(chuàng)作于2023年2月2.2.1狀態(tài)空間表示法狀態(tài)空間表示法是用“狀態(tài)”和“算子”來表示問題的一種方法狀態(tài)：用來描述問題求解過程中不同時刻的狀況算子：表示對狀態(tài)的操作，算子的每次使用就使問題由一種狀態(tài)變換為另一種狀態(tài)當(dāng)達(dá)到目標(biāo)狀態(tài)時，由初始狀態(tài)到目標(biāo)狀態(tài)所用算子的序列就是問題的一個解第8頁，課件共163頁，創(chuàng)作于2023年2月2.2.1狀態(tài)空間表示法狀態(tài)狀態(tài)是描述問題求解過程中任一時刻狀況的數(shù)據(jù)結(jié)構(gòu)，一般用一組變量的有序組合表示：SK(SK0,SK1,…)當(dāng)給每一分量以確定的值時，就得到一個具體的狀態(tài)算子引起狀態(tài)中某些分量發(fā)生變化，從而使問題由一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作稱為算子。產(chǎn)生式系統(tǒng)中，每一條產(chǎn)生式規(guī)則就是一個算子狀態(tài)空間由問題的全部狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)空間，一般用三元組表示:(S,F,C,I,G)S:所有狀態(tài)構(gòu)成的集合F:用于狀態(tài)轉(zhuǎn)換的算子的集合C:狀態(tài)轉(zhuǎn)換代價的聚合I:初始狀態(tài)的集合G:目標(biāo)狀態(tài)的集合第9頁，課件共163頁，創(chuàng)作于2023年2月例:二階HanoiTower（梵塔）問題設(shè)有三根柱子，在1號柱于上穿有A、B兩個盤片，盤A小于盤B，盤A位于盤B的上面。要求把這兩個盤片全部移到另一根柱子上，而且規(guī)定每次只能移動一片，任何時刻都不能使盤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)第10頁，課件共163頁，創(chuàng)作于2023年2月例:二階HanoiTower（梵塔）問題9種狀態(tài)，12種算子構(gòu)成的狀態(tài)空間轉(zhuǎn)移圖：第11頁，課件共163頁，創(chuàng)作于2023年2月2.2.1狀態(tài)空間表示法總結(jié)：用狀態(tài)空間方法表示問題時，首先必須定義狀態(tài)的描述形式，通過使用這種描述形式可把問題的一切狀態(tài)都表示出來。其次，還安定義一組算符，通過使用算符可把問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。問題的求解過程是一個不斷把算符作用于狀態(tài)的過程。如果在使用某個算符后得到的新狀態(tài)是目標(biāo)狀態(tài)，就得到問題的一個解：從初始狀態(tài)到目標(biāo)狀態(tài)所用算符構(gòu)成的序列。算符的一次使用，就使問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)?？赡苡卸鄠€算特序列都可使問題從初始狀態(tài)變到目標(biāo)狀態(tài)，這就得到了多個解。把使用算符最少的解稱為最優(yōu)解。對任何一個狀態(tài)，可使用的算符可能不止一個，因而由一個狀態(tài)所生成的后繼狀態(tài)就可能有多個。當(dāng)對這些后繼狀態(tài)使用算子生成更進(jìn)一步狀態(tài)時，首先應(yīng)對哪一狀態(tài)進(jìn)行操作呢？這取決于搜索策略，不同搜索策略的操作順序是不相同的。第12頁，課件共163頁，創(chuàng)作于2023年2月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)為頂點(diǎn)，狀態(tài)之間所允許的操作為有向邊，獲得‘圖’形式的狀態(tài)空間。Step4：應(yīng)用圖搜索方法，在狀態(tài)空間中搜索從初始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)路徑或可行路徑。第13頁，課件共163頁，創(chuàng)作于2023年2月例:三階HanoiTower（梵塔）問題第14頁，課件共163頁，創(chuàng)作于2023年2月例:三階HanoiTower（梵塔）問題第15頁，課件共163頁，創(chuàng)作于2023年2月例:三階HanoiTower（梵塔）問題第16頁，課件共163頁，創(chuàng)作于2023年2月2.2.2與或圖表示法也稱為問題歸約方法：把初始問題通過一系列交換最終變?yōu)橐粋€子問題集合，而這些于問題的解可以直接得到，從而解答了初始問題。分解：把一個復(fù)雜問題分解為若干個較為簡單的子問題，每個子問題又可繼續(xù)分解為若干個更為簡單的子問題。重復(fù)此過程，直到不需要再分解或者不能再分解為止。然后對每個子問題分別進(jìn)行求解，最后把各子問題的解復(fù)合起來就得到了原問題的解。問題的分解可以用圖表示出來，稱為與樹。例如，把問題P分解為三個子問題P1、P2和P3，可以表示為下圖：第17頁，課件共163頁，創(chuàng)作于2023年2月2.2.2與或圖表示法等價變換：利用同構(gòu)或同態(tài)的等價變換，把它變換成若干個較容易求解的新問題。若新問題中有一個可求解，則就得到了原問題的解。問題的等價變換過程也可用一個圖表示出來，稱為“或”樹。與或樹的結(jié)合稱為與或圖（樹）。第18頁，課件共163頁，創(chuàng)作于2023年2月2.2.2與或圖表示法本原問題：不能再分解或變換，而且直接可解的子問題稱為本原問題。端節(jié)點(diǎn)與終止節(jié)點(diǎn)：在與／或樹中，沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為端節(jié)點(diǎn)；本原問題所對應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)。顯然，終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)不一定是終止節(jié)點(diǎn)。可解節(jié)點(diǎn)：在與／或樹今，滿足下列條件之一的節(jié)點(diǎn)：1)它是一個終止節(jié)點(diǎn)。2)它是一個“或”節(jié)點(diǎn)，且其子節(jié)點(diǎn)至少有一個是可解節(jié)點(diǎn)。3)它是一個“與”節(jié)點(diǎn)，且其子節(jié)點(diǎn)全部是可解節(jié)點(diǎn)。不可解節(jié)點(diǎn)：上面三個條件全不滿足的節(jié)點(diǎn)。解樹：由可解節(jié)點(diǎn)所構(gòu)成的，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)(它對應(yīng)于原始問題)為可解節(jié)點(diǎn)的子樹稱為解樹。在解樹中’定包含初始節(jié)點(diǎn)。第19頁，課件共163頁，創(chuàng)作于2023年2月例:三階HanoiTower（梵塔）問題設(shè)有A、B、C三個盤片以及三根柱子，三個盤片按從小到大的順序穿在1號柱上，要求把它們?nèi)恳频?號柱上，而且每次只能移動一個盤片，任何時刻都不能把大的盤片壓在小的盤片上面，如圖所示。第20頁，課件共163頁，創(chuàng)作于2023年2月例:三階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)又分別可分解為三個子問題第21頁，課件共163頁，創(chuàng)作于2023年2月例:三階HanoiTower（梵塔）問題定義問題狀態(tài)表示：設(shè)三元組(i,j,k)表示狀態(tài)，其中i表示盤片C所在的柱號,j表示盤片B所在的柱號；k表示盤片A所在的柱號。初始問題可表示為：(1、1．1)(3，3，3)與／或樹表示如圖所示。(把圖中7個終止節(jié)點(diǎn)(本原問題)按從左至右排列，得到了初始問題的解)第22頁，課件共163頁，創(chuàng)作于2023年2月2.2.2與或圖表示法基于與或圖表示的問題求解算法Step1：確定單個問題描述形式，可采用狀態(tài)空間表示法。Step2：從原始問題開始，逐步進(jìn)行分解和變換，直到本原問題，然后將全部分解和變換過程表示為與或圖。Step3：從端頂點(diǎn)開始，逐步向上回溯，標(biāo)注各頂點(diǎn)為可解或不可解頂點(diǎn)，直到標(biāo)注原始頂點(diǎn)為可解頂點(diǎn)或不可解頂點(diǎn)為止Step4：當(dāng)原始頂點(diǎn)被確定為可解頂點(diǎn)時，輸出相應(yīng)解圖為問題的解。第23頁，課件共163頁，創(chuàng)作于2023年2月2.3搜索技術(shù)搜索技術(shù)是人工智能的基本技術(shù)之一,在人工智能各應(yīng)用領(lǐng)域中被廣泛地使用。早期的人工智能程序與搜索技術(shù)聯(lián)系就更為緊密，幾乎所有的早期的人工智能程序都是以搜索為基礎(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ù)?，F(xiàn)在,搜索技術(shù)滲透在各種人工智能系統(tǒng)中,可以說沒有哪一種人工智能的應(yīng)用不用搜索方法,在專家系統(tǒng)、自然語言理解、自動程序設(shè)計、模式識別、機(jī)器人學(xué)、信息檢索和博弈都廣泛使用搜技術(shù)。第24頁，課件共163頁，創(chuàng)作于2023年2月2.3搜索技術(shù)搜索問題是AI核心理論問題之一一般一個問題可以用好幾種搜索技術(shù)解決,選擇一種好的搜索技術(shù)對解決問題的效率很有關(guān)系,甚至關(guān)系到求解問題有沒有解。搜索方法好的標(biāo)準(zhǔn),一般認(rèn)為有兩個：(1)搜索空間小;(2)解最佳。第25頁，課件共163頁，創(chuàng)作于2023年2月2.3搜索技術(shù)搜索從問題性質(zhì)上來看,可分為一般搜索和博奕搜索,從處理方法上來看,可分為盲目搜索和啟發(fā)式搜索。還可以分得更細(xì)。當(dāng)所給定的問題用狀態(tài)空間表示時,則求解過程可歸結(jié)為對狀態(tài)空間的搜索。當(dāng)問題有解時,使用不同的搜索策略,找到解的搜索空間范圍是有區(qū)別的。一般來說,對大空間問題,搜索策略是要解決組合爆炸的問題第26頁，課件共163頁，創(chuàng)作于2023年2月第27頁，課件共163頁，創(chuàng)作于2023年2月2.3搜索策略通常搜索策略的主要任務(wù)是確定如何選取規(guī)則的方式。有兩種基本方式:一種是不考慮給定問題所具有的特定知識,系統(tǒng)根據(jù)事先確定好的某種固定排序,依次調(diào)用規(guī)則或隨機(jī)調(diào)用規(guī)則,這實(shí)際上是盲目搜索的方法,一般統(tǒng)稱為無信息引導(dǎo)的搜索策略。另一種是考慮問題領(lǐng)域可應(yīng)用的知識,動態(tài)地確定規(guī)則的排序,優(yōu)先調(diào)用較合適的規(guī)則使用,這就是通常稱為啟發(fā)式搜索策略或有信息引導(dǎo)的搜索策略。第28頁，課件共163頁，創(chuàng)作于2023年2月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*)第29頁，課件共163頁，創(chuàng)作于2023年2月AI領(lǐng)域的搜索方法(3)求與或關(guān)系解圖的搜索法一般與或圖搜索法(AO*)

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

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

從前有座山……第47頁，課件共163頁，創(chuàng)作于2023年2月Fibonacci數(shù)列1202年，意大利家斐波那契在提出了一個關(guān)于兔子繁殖的問題：

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

不發(fā)生死亡的情況下，由一對出生的小兔開始，50個月后會有多少對兔子？第48頁，課件共163頁，創(chuàng)作于2023年2月當(dāng)n＞1時，F(xiàn)n+2=Fn+1+Fn，而F0=F1=1。第49頁，課件共163頁，創(chuàng)作于2023年2月遞歸的思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g第50頁，課件共163頁，創(chuàng)作于2023年2月回溯搜索算法

BACKTRACK（DATA）

DATA：當(dāng)前狀態(tài)。 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。第51頁，課件共163頁，創(chuàng)作于2023年2月回溯搜索算法遞歸過程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);第52頁，課件共163頁，創(chuàng)作于2023年2月存在問題及解決辦法問題：深度問題死循環(huán)問題解決辦法：對搜索深度加以限制記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑第53頁，課件共163頁，創(chuàng)作于2023年2月回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向） 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。第54頁，課件共163頁，創(chuàng)作于2023年2月回溯搜索算法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);第55頁，課件共163頁，創(chuàng)作于2023年2月回溯搜索算法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);第56頁，課件共163頁，創(chuàng)作于2023年2月一些深入的問題失敗原因分析、多步回溯QQ第57頁，課件共163頁，創(chuàng)作于2023年2月一些深入問題（續(xù)）回溯搜索中知識的利用 基本思想： 盡可能選取劃去對角線上位置數(shù)最少的。QQQQ4334第58頁，課件共163頁，創(chuàng)作于2023年2月圖搜索策略問題的引出回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。圖搜索：保留所有已經(jīng)搜索過的路徑。

第59頁，課件共163頁，創(chuàng)作于2023年2月一些基本概念節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0

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

(6)擴(kuò)展節(jié)點(diǎn)n，同時生成不是n的祖先的那些后繼節(jié)點(diǎn)的集合M。把M的這些成員作為n的后繼節(jié)點(diǎn)添入圖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é)點(diǎn)的指針方向。(8)按某一任意方式或按某個探試值，重排OPEN表。(9)GOLOOP。第64頁，課件共163頁，創(chuàng)作于2023年2月OPEN表節(jié)點(diǎn)父節(jié)點(diǎn)CLOSED表標(biāo)號節(jié)點(diǎn)父節(jié)點(diǎn)OPEN表節(jié)點(diǎn)父節(jié)點(diǎn)編號CLOSED表編號節(jié)點(diǎn)父節(jié)點(diǎn)編號第65頁，課件共163頁，創(chuàng)作于2023年2月例子例子：從某王姓家族的四代中找王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，如何尋找？第66頁，課件共163頁，創(chuàng)作于2023年2月問題的搜索樹第67頁，課件共163頁，創(chuàng)作于2023年2月深度優(yōu)先搜索的搜索過程無信息圖搜索過程—深度優(yōu)先第68頁，課件共163頁，創(chuàng)作于2023年2月重排九宮深度優(yōu)先只是搜索樹的一部分，尚未到達(dá)目標(biāo)節(jié)點(diǎn)，仍需繼續(xù)往下搜索。第69頁，課件共163頁，創(chuàng)作于2023年2月有界深度優(yōu)先搜索的搜索過程如果問題有解，且其路徑長度<=dm，則上述搜索過程一定能求得解。但是，若解的路徑長度>dm，則搜索過程就得不到解。----深度界限的選擇很重要。第70頁，課件共163頁，創(chuàng)作于2023年2月有界深度優(yōu)先搜索設(shè)深度界度dm=4，有界深度優(yōu)先搜索求解圖如下，解的路徑為S020252628(Sg)第71頁，課件共163頁，創(chuàng)作于2023年2月深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時，可能找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個通用的與問題無關(guān)的方法第72頁，課件共163頁，創(chuàng)作于2023年2月無信息圖搜索過程—寬度優(yōu)先寬度優(yōu)先搜索過程：(1)把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個解答)。(2)如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。(3)把OPEN表中第一個節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED擴(kuò)展節(jié)點(diǎn)表中。(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，若是則求得問題的解，退出，(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第(2)步。(6)擴(kuò)展節(jié)點(diǎn)n。將其所有后繼節(jié)點(diǎn)放到OPEN表的末端，并為每個后續(xù)節(jié)點(diǎn)都配置指向n的指針。然后轉(zhuǎn)向第(2)步。第73頁，課件共163頁，創(chuàng)作于2023年2月寬度優(yōu)先第74頁，課件共163頁，創(chuàng)作于2023年2月重排九宮寬度優(yōu)先解的路徑：S0381626第75頁，課件共163頁，創(chuàng)作于2023年2月寬度優(yōu)先搜索的性質(zhì)只要問題有解，一定能找到解，而且得到的是路徑最短的解。盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時將會產(chǎn)生許多無用節(jié)點(diǎn)，因此搜索效率低。方法與問題無關(guān)，具有通用性屬于圖搜索方法第76頁，課件共163頁，創(chuàng)作于2023年2月非啟發(fā)式搜索按照事先規(guī)定的路線進(jìn)行搜索廣度優(yōu)先搜索是按“層”進(jìn)行搜索的，先進(jìn)入OPEN表的節(jié)點(diǎn)先被考察深度優(yōu)先搜索是沿著縱深方向進(jìn)行搜索的，后進(jìn)入OPEN表的節(jié)點(diǎn)先被考察按已經(jīng)付出的代價決定下一步要搜索的節(jié)點(diǎn)（為樹中的每條邊賦予代價，廣度及深度優(yōu)先搜索實(shí)質(zhì)是每條邊的代價都為1）代價樹的廣度優(yōu)先代價樹的深度優(yōu)先第77頁，課件共163頁，創(chuàng)作于2023年2月代價樹的寬度憂先搜索邊上標(biāo)有代價(或費(fèi)用)的樹稱為代價樹。在代價樹中，若用g(x)表示從初姑節(jié)點(diǎn)S0到節(jié)點(diǎn)x的代價，用c(xl,x2)表示從父節(jié)點(diǎn)x1到子節(jié)點(diǎn)x2的代價，則有：g(x2)=g(x1)+c(x1,x2)

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

f(n)=g(n)+h(n) f(n)：評價函數(shù) g(n):實(shí)際已經(jīng)付出的代價函數(shù) h(n)：啟發(fā)函數(shù)第84頁，課件共163頁，創(chuàng)作于2023年2月符號的意義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)的估計值第85頁，課件共163頁，創(chuàng)作于2023年2月一個A算法的例子定義評價函數(shù)：

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

h(n)為當(dāng)前節(jié)點(diǎn)“不在位”的將牌數(shù) 2831647512384765第86頁，課件共163頁，創(chuàng)作于2023年2月h計算舉例

h(n)=42

831

647512345768第87頁，課件共163頁，創(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)目標(biāo)123456g=0,h=4f=0+4=4g=1,h=5f=1+5=6g=0g=1g=2g=3第88頁，課件共163頁，創(chuàng)作于2023年2月最佳圖搜索算法A*（A*算法）在A算法中，如果滿足條件：

h(n)≤h*(n)

則A算法稱為A*算法。其中h*(n)是從頂點(diǎn)Sn到Sg的最小代價。由于h*(n)最小代價通常不知道，因此用h(n)（不在位的將牌數(shù)）進(jìn)行代價估計，因此可得h(n)<h*(n),所以上例是A*算法。第89頁，課件共163頁，創(chuàng)作于2023年2月A*條件舉例8數(shù)碼問題h(n)=“不在位”的將牌數(shù)=f1h(n)=將牌“不在位”的距離和=f2采用f2算法的效率會高于f1的算法，因?yàn)閒2>=f12

831

647512345768將牌1：1將牌2：1將牌6：1將牌8：2第90頁，課件共163頁，創(chuàng)作于2023年2月A*算法的性質(zhì)定理1： 對有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。第91頁，課件共163頁，創(chuàng)作于2023年2月AO*算法是A*算法在與或圖上的擴(kuò)展算法。AO*算法中由于與節(jié)點(diǎn)的存在，解對應(yīng)的不是一條路徑，而是一個子圖，因此對頂點(diǎn)的評估實(shí)際上是對局部解圖的評價。與節(jié)點(diǎn)代價計算：最大代價和代價或節(jié)點(diǎn)的代價計算：最小代價AO*算法第92頁，課件共163頁，創(chuàng)作于2023年2月AO*算法舉例7=3+1(左樹)+2+18=3+1+3+18=min(8+1,7+1)第93頁，課件共163頁，創(chuàng)作于2023年2月與或樹的寬度優(yōu)先與深度優(yōu)先搜索寬度優(yōu)先：12345深度優(yōu)先：13B524第94頁，課件共163頁，創(chuàng)作于2023年2月問題圖搜索是針對什么知識表示方法的問題求解方法？什么是圖搜索?其中，重排OPEN表意味著什么，重排的原則是什么?寬度優(yōu)先搜索方法中OPEN表需要按什么方式進(jìn)行操作 A．先進(jìn)后出B．先進(jìn)先出有界深度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑嗎？試比較各種盲目搜索搜索方法的效率，找出影響算法效率的原因試比較寬度優(yōu)先搜索、有界深度優(yōu)先搜索及有序搜索的搜索效率，并以實(shí)例數(shù)據(jù)加以說明第95頁，課件共163頁，創(chuàng)作于2023年2月啟發(fā)式搜索的必要性現(xiàn)實(shí)的困難迫使人們轉(zhuǎn)而求援于啟發(fā)式算法。這種算法的本質(zhì)是部分地放棄算法“一般化,通用化”的概念,把所要解的問題的具體領(lǐng)域的知識加進(jìn)算法中去,以提高算法的效率。如,廣度優(yōu)先法幾乎可以用于解一切搜索問題：九宮圖(八數(shù)碼難題),hanoi塔(焚塔問題),旅行推銷員,華容道,以至魔方等等。但實(shí)際使用時,效率也許低得驚人,甚至根本解不出來(例如魔方問題)。如果我們?yōu)槊款悊栴}找出一些特殊規(guī)則,和廣度優(yōu)先法配合起來使用,那結(jié)果就可能完全不一樣了。第96頁，課件共163頁，創(chuàng)作于2023年2月啟發(fā)式搜索的必要性根據(jù)啟發(fā)信息,在生成各種搜索樹時可以考慮種種可能的選擇,如:1.下一步展開哪個節(jié)點(diǎn)?2.是部分展開還是完全展開?3.使用哪個規(guī)則(或算子)?4.怎樣決定舍棄還是保留新生成的節(jié)點(diǎn)?5.怎樣決定舍棄還是保留一棵子樹?6.怎樣決定停止或繼續(xù)搜索?7.如何定義啟發(fā)函數(shù)(評價函數(shù))?8.如何決定搜索方向?……

由于這些選擇的不同,就得到了不同的啟發(fā)式算法第97頁，課件共163頁，創(chuàng)作于2023年2月*解路徑如粗線所標(biāo)左、上、右、下**S、A、B、…、L、M等為狀態(tài)空間圖中各個節(jié)點(diǎn)名,其后的小括號中數(shù)字表示該節(jié)點(diǎn)的評價函數(shù)f(n)的估計值,例如S(4)、L(5)等。

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

九宮重排問題第98頁，課件共163頁，創(chuàng)作于2023年2月搜索效率比較第99頁，課件共163頁，創(chuàng)作于2023年2月啟發(fā)式搜索策略

人工智能問題求解者在兩種基本情況下運(yùn)用啟發(fā)式策略:一個問題由于在問題陳述和數(shù)據(jù)獲取方面固有的模糊性可能使它沒有一個確定的解。醫(yī)療診斷即是一例。所給出的一系列癥狀可能有多個原因,醫(yī)生運(yùn)用啟發(fā)式搜索來選擇最有可能的論斷并依此產(chǎn)生治療計劃。一個問題可能有確定解,但是求解過程中的計算機(jī)代價令人難以接受。在很多問題(如國際象棋)中,狀態(tài)空間的增長特別快,可能的狀態(tài)數(shù)隨著搜索的深度呈指數(shù)級增長、分解。在這種情況下,窮盡式搜索策略諸如深度優(yōu)先或廣度優(yōu)先搜索,在一個給定的較實(shí)際的時空內(nèi)很可能得不到最終的解和發(fā)明創(chuàng)造的所有規(guī)則一樣,啟發(fā)式策略也是極易出錯的第100頁，課件共163頁，創(chuàng)作于2023年2月圖搜索策略圖搜索策略的定義圖搜索策略可看作一種在圖中尋找路徑的方法。初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別代表初始數(shù)據(jù)庫和滿足終止條件的數(shù)據(jù)庫。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。研究圖搜索的一般策略，能夠給出圖搜索過程的一般步驟。圖搜索算法中的幾個重要名詞術(shù)語（1）OPEN表與CLOSE表（2）搜索圖與搜索樹第101頁，課件共163頁，創(chuàng)作于2023年2月你可曾聽說過“深藍(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

卡氏何許人也？第102頁，課件共163頁，創(chuàng)作于2023年2月第103頁，課件共163頁，創(chuàng)作于2023年2月電腦棋手：永不停歇的挑戰(zhàn)！1988年“深思”擊敗了丹麥特級大師拉森。1993年“深思”第二代擊敗了丹麥?zhǔn)澜鐑?yōu)秀女棋手小波爾加。第104頁，課件共163頁，創(chuàng)作于2023年2月電腦棋手：永不停歇的挑戰(zhàn)！2001年“更弗里茨”擊敗了除了克拉姆尼克之外的所有排名世界前十位的棋手。2002年10月“更弗里茨”與世界棋王克拉姆尼克在巴林交手，雙方以4比4戰(zhàn)平。2003年1至2月“更年少者”與卡斯帕羅夫在紐約較量，3比3戰(zhàn)平。第105頁，課件共163頁，創(chuàng)作于2023年2月許多人在努力

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

——人機(jī)博弈程序的一般設(shè)計方法以中國棋為例第112頁，課件共163頁，創(chuàng)作于2023年2月（1）第一步該做什么？數(shù)據(jù)結(jié)構(gòu)的選取——棋盤表示占用空間-〉少操作速度-〉快是否方便-〉方便在機(jī)器中表示棋局，讓程序知道博弈狀態(tài)。第113頁，課件共163頁，創(chuàng)作于2023年2月九列十行十四種不同的棋子三十二個棋子第114頁，課件共163頁，創(chuàng)作于2023年2月幾種棋盤表示的方式二維數(shù)組——直觀緊湊的數(shù)據(jù)結(jié)構(gòu)——省空間，不直觀，速度?比特棋盤——用于8*8棋盤（國際象棋），64位主機(jī)第115頁，課件共163頁，創(chuàng)作于2023年2月（2）接下來怎么辦？產(chǎn)生合法走步的規(guī)則，使博弈能公正的進(jìn)行，并且能夠判斷對手是否亂走。依賴于具體棋類特征。是一段將局面所有可能的正確走法羅列出來的程序。稱之為走法產(chǎn)生。第116頁，課件共163頁，創(chuàng)作于2023年2月幾種走法產(chǎn)生的實(shí)現(xiàn)方式一般做法建立小型數(shù)據(jù)庫位運(yùn)算第117頁，課件共163頁，創(chuàng)作于2023年2月位運(yùn)算走法產(chǎn)生之例尋找象的可走步第118頁，課件共163頁，創(chuàng)作于2023年2月位運(yùn)算走法產(chǎn)生之要求一個基于比特棋盤的完善的數(shù)據(jù)庫該數(shù)據(jù)庫應(yīng)位于內(nèi)存中第119頁，課件共163頁，創(chuàng)作于2023年2月（3）終于到核心了從所有的走法中找出最佳的走法，也就是——搜索第120頁，課件共163頁，創(chuàng)作于2023年2月博弈概述諸如下棋、打牌、競技、戰(zhàn)爭等一類競爭性智能活動稱為博弈。博弈有很多種，我們討論最簡單的"二人零和、全信息、非偶然"博弈，其特征如下：

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

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

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

第121頁，課件共163頁，創(chuàng)作于2023年2月博弈概述在博弈過程中，任何一方都希望自己取得勝利。因此，當(dāng)某一方當(dāng)前有多個行動方案可供選擇時，他總是挑選對自己最為有利而對對方最為不利的那個行動方案。此時，如果我們站在MAX方的立場上，則可供MAX方選擇的若干行動方案之間是"或"關(guān)系，因?yàn)橹鲃訖?quán)操在MAX方手里，他或者選擇這個行動方案，或者選擇另一個行動方案，完全由MAX方自已決定。當(dāng)MAX方選取任一方案走了一步后，MIN方也有若干個可供選擇的行動方案，此時這些行動方案對MAX方來說它們之間則是"與"關(guān)系，因?yàn)檫@時主動權(quán)操在MIN方手里，這些可供選擇的行動方案中的任何一個都可能被MIN方選中，MAX方必須應(yīng)付每一種情況的發(fā)生。第122頁，課件共163頁，創(chuàng)作于2023年2月博弈概述這樣，如果站在某一方(如MAX方，即MAX要取勝)，把上述博弈過程用圖表示出來，則得到的是一棵"與或樹"。描述博弈過程的與或樹稱為博弈樹，它有如下特點(diǎn)：

(1)博弈的初始格局是初始節(jié)點(diǎn)。

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

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

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

第123頁，課件共163頁，創(chuàng)作于2023年2月搜索算法極大極小值算法

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

MTD(f)算法（Memory–enhancedTestDriverwithfandn）第124頁，課件共163頁，創(chuàng)作于2023年2月極大極小法基本思想或算法：(1)設(shè)博弈的雙方中一方為MAX，另一方為MIN。然后為其中的一方(例如MAX)尋找一個最優(yōu)行動方案。(2)為了找到當(dāng)前的最優(yōu)行動方案，需要對各個可能的方案所產(chǎn)生的后果進(jìn)行比較,具體地說，就是要考慮每一方案實(shí)施后對方可能采取的所有行動，并計算可能的得分。(3)為計算得分，需要根據(jù)問題的特性信息定義一個估價函數(shù)，用來估算當(dāng)前博弈樹端節(jié)點(diǎn)的得分。此時估算出來的得分稱為靜態(tài)估值。(4)當(dāng)端節(jié)點(diǎn)的估值計算出來后，再推算出父節(jié)點(diǎn)的得分，推算的方法是：對“或”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個最大的得分作為父節(jié)點(diǎn)的得分，這是為了使自己在可供選擇的方案中選一個對自己最有利的方案；對“與”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個最小的得分作為父節(jié)點(diǎn)的得分，這是為了立足于最壞的情況。這樣計算出的父節(jié)點(diǎn)的得分稱為倒推值。(5)如果一個行動方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動方案。第125頁，課件共163頁，創(chuàng)作于2023年2月極大極小倒推值的計算A是與節(jié)點(diǎn)，從下往上可以倒推出S0的估計值第126頁，課件共163頁，創(chuàng)作于2023年2月一字棋游戲極小極大分析法設(shè)有九個空格，由MAX，MIN二人對弈，輪到誰走棋誰就往空格上放一只自己的棋子，誰先使自己的棋子構(gòu)成“三子成一線”(同一行或列或?qū)蔷€全是某人的棋子)，誰就取得了勝利。用叉號表示MAX，用圓圈代表MIN。第127頁，課件共163頁，創(chuàng)作于2023年2月一字棋游戲極小極大分析法為了不致于生成太大的博弈樹，假設(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)＝-∞。

第128頁，課件共163頁，創(chuàng)作于2023年2月一字棋游戲極小極大分析法集中典型棋局得分值h(n)計算：(a)h(n)=4-2=2(b)是和局，h(n)=0(c)×方獲勝，h(n)=+∞(d)○方獲勝，h(n)=-∞第129頁，課件共163頁，創(chuàng)作于2023年2月一字棋游戲極小極大分析法第一回合擴(kuò)展深度為2第130頁，課件共163頁，創(chuàng)作于2023年2月第131頁，課件共163頁，創(chuàng)作于2023年2月一字棋極大極小法的第一階段第132頁，課件共163頁，創(chuàng)作于2023年2月一字棋極大極小法的第二階段第133頁，課件共163頁，創(chuàng)作于2023年2月一字棋極大極小法的第三階段第134頁，課件共163頁，創(chuàng)作于2023年2月Alpha-Beta剪枝技術(shù)極大極小搜索要求先生成與／或樹，然后再計算各節(jié)點(diǎn)的估值，需要生成規(guī)定深度內(nèi)的所有節(jié)點(diǎn)，因此搜索效率較低。基本思想或算法是，邊生成博弈樹邊計算評估各節(jié)點(diǎn)的倒推值，并且根據(jù)評估出的倒推值范圍，及時停止擴(kuò)展那些已無必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機(jī)器開銷，提高了搜索效率。第135頁，課件共163頁，創(chuàng)作于2023年2月Alpha-Beta剪枝技術(shù)(1)對于一個與節(jié)點(diǎn)MIN，若能估計出其倒推值的上確界β，并且這個β值不大于MIN的父節(jié)點(diǎn)(一定是或節(jié)點(diǎn))的估計倒推值的下確界α，即α≥β，則就不必再擴(kuò)展該MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對MIN父節(jié)點(diǎn)的倒推值已無任何影響了)。這一過程稱為α剪枝。(2)對于一