人工智能之搜索課件

人工智能導(dǎo)論

第二章：搜索、問題求解與博弈人工智能導(dǎo)論

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

表示盤片A所在的柱號(hào)，SK1

表示盤片B所在的柱號(hào)全部可能的狀態(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)例:二階HanoiTower（梵塔）問題設(shè)有三根柱子，在例:二階HanoiTower（梵塔）問題9種狀態(tài)，12種算子構(gòu)成的狀態(tài)空間轉(zhuǎn)移圖：例:二階HanoiTower（梵塔）問題9種狀態(tài)，12種2.2.1狀態(tài)空間表示法總結(jié)：用狀態(tài)空間方法表示問題時(shí)，首先必須定義狀態(tài)的描述形式，通過使用這種描述形式可把問題的一切狀態(tài)都表示出來。其次，還安定義一組算符，通過使用算符可把問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。問題的求解過程是一個(gè)不斷把算符作用于狀態(tài)的過程。如果在使用某個(gè)算符后得到的新狀態(tài)是目標(biāo)狀態(tài)，就得到問題的一個(gè)解：從初始狀態(tài)到目標(biāo)狀態(tài)所用算符構(gòu)成的序列。算符的一次使用，就使問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)?？赡苡卸鄠€(gè)算特序列都可使問題從初始狀態(tài)變到目標(biāo)狀態(tài)，這就得到了多個(gè)解。把使用算符最少的解稱為最優(yōu)解。對(duì)任何一個(gè)狀態(tài)，可使用的算符可能不止一個(gè)，因而由一個(gè)狀態(tài)所生成的后繼狀態(tài)就可能有多個(gè)。當(dāng)對(duì)這些后繼狀態(tài)使用算子生成更進(jìn)一步狀態(tài)時(shí)，首先應(yīng)對(duì)哪一狀態(tài)進(jìn)行操作呢？這取決于搜索策略，不同搜索策略的操作順序是不相同的。2.2.1狀態(tài)空間表示法總結(jié)：2.2.1狀態(tài)空間表示法基于狀態(tài)空間表示的問題求解算法Step1：確定問題狀態(tài)的計(jì)算機(jī)描述形式，將所有可能的狀態(tài)表示出來，并確定其中的初始狀態(tài)和目標(biāo)狀態(tài)。Step2：確定促使?fàn)顟B(tài)發(fā)生轉(zhuǎn)換的操作，并在計(jì)算機(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)路徑或可行路徑。2.2.1狀態(tài)空間表示法基于狀態(tài)空間表示的問題求解算法例:三階HanoiTower（梵塔）問題例:三階HanoiTower（梵塔）問題例:三階HanoiTower（梵塔）問題例:三階HanoiTower（梵塔）問題例:三階HanoiTower（梵塔）問題例:三階HanoiTower（梵塔）問題2.2.2與或圖表示法也稱為問題歸約方法：把初始問題通過一系列交換最終變?yōu)橐粋€(gè)子問題集合，而這些于問題的解可以直接得到，從而解答了初始問題。分解：把一個(gè)復(fù)雜問題分解為若干個(gè)較為簡(jiǎn)單的子問題，每個(gè)子問題又可繼續(xù)分解為若干個(gè)更為簡(jiǎn)單的子問題。重復(fù)此過程，直到不需要再分解或者不能再分解為止。然后對(duì)每個(gè)子問題分別進(jìn)行求解，最后把各子問題的解復(fù)合起來就得到了原問題的解。問題的分解可以用圖表示出來，稱為與樹。例如，把問題P分解為三個(gè)子問題P1、P2和P3，可以表示為下圖：2.2.2與或圖表示法也稱為問題歸約方法：把初始問題通過一2.2.2與或圖表示法等價(jià)變換：利用同構(gòu)或同態(tài)的等價(jià)變換，把它變換成若干個(gè)較容易求解的新問題。若新問題中有一個(gè)可求解，則就得到了原問題的解。問題的等價(jià)變換過程也可用一個(gè)圖表示出來，稱為“或”樹。與或樹的結(jié)合稱為與或圖（樹）。2.2.2與或圖表示法等價(jià)變換：利用同構(gòu)或同態(tài)的等價(jià)變換，2.2.2與或圖表示法本原問題：不能再分解或變換，而且直接可解的子問題稱為本原問題。端節(jié)點(diǎn)與終止節(jié)點(diǎn)：在與／或樹中，沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為端節(jié)點(diǎn)；本原問題所對(duì)應(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)它是一個(gè)終止節(jié)點(diǎn)。2)它是一個(gè)“或”節(jié)點(diǎn)，且其子節(jié)點(diǎn)至少有一個(gè)是可解節(jié)點(diǎn)。3)它是一個(gè)“與”節(jié)點(diǎn)，且其子節(jié)點(diǎn)全部是可解節(jié)點(diǎn)。不可解節(jié)點(diǎn)：上面三個(gè)條件全不滿足的節(jié)點(diǎn)。解樹：由可解節(jié)點(diǎn)所構(gòu)成的，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)(它對(duì)應(yīng)于原始問題)為可解節(jié)點(diǎn)的子樹稱為解樹。在解樹中’定包含初始節(jié)點(diǎn)。2.2.2與或圖表示法本原問題：不能再分解或變換，而且直接例:三階HanoiTower（梵塔）問題設(shè)有A、B、C三個(gè)盤片以及三根柱子，三個(gè)盤片按從小到大的順序穿在1號(hào)柱上，要求把它們?nèi)恳频?號(hào)柱上，而且每次只能移動(dòng)一個(gè)盤片，任何時(shí)刻都不能把大的盤片壓在小的盤片上面，如圖所示。例:三階HanoiTower（梵塔）問題設(shè)有A、B、C三例:三階HanoiTower（梵塔）問題分析：1)為了把三個(gè)盤片全部移到3號(hào)柱上，必須先把盤片C移到3號(hào)柱上。2)為了移盤片C，必須先把盤片A及B移到2號(hào)柱上。3)當(dāng)把盤片C移到3號(hào)盤上后，就可把A、B從2號(hào)柱移到3號(hào)柱上，以完成問題的求解。把原問題分解為三個(gè)子問題：1)把盤片A及B移到2號(hào)柱的雙盤片問題。2)把盤片C移到3號(hào)柱的單盤片問題。3)把盤片A及B移到3號(hào)柱的雙盤片問題。其中，子問題1)與子問題3)又分別可分解為三個(gè)子問題例:三階HanoiTower（梵塔）問題分析：例:三階HanoiTower（梵塔）問題定義問題狀態(tài)表示：設(shè)三元組(i,j,k)表示狀態(tài)，其中i表示盤片C所在的柱號(hào),j表示盤片B所在的柱號(hào)；k表示盤片A所在的柱號(hào)。初始問題可表示為：(1、1．1)(3，3，3)與／或樹表示如圖所示。(把圖中7個(gè)終止節(jié)點(diǎn)(本原問題)按從左至右排列，得到了初始問題的解)例:三階HanoiTower（梵塔）問題定義問題狀態(tài)表示2.2.2與或圖表示法基于與或圖表示的問題求解算法Step1：確定單個(gè)問題描述形式，可采用狀態(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)時(shí)，輸出相應(yīng)解圖為問題的解。2.2.2與或圖表示法基于與或圖表示的問題求解算法2.3搜索技術(shù)

搜索技術(shù)是人工智能的基本技術(shù)之一,在人工智能各應(yīng)用領(lǐng)域中被廣泛地使用。早期的人工智能程序與搜索技術(shù)聯(lián)系就更為緊密，幾乎所有的早期的人工智能程序都是以搜索為基礎(chǔ)的。例如，A.Newell(艾倫·紐厄爾)和H·A·Simon(西蒙)等人編寫的LT(LogicTheorist)程序,J.Slagle寫的符號(hào)積分程序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)、自然語(yǔ)言理解、自動(dòng)程序設(shè)計(jì)、模式識(shí)別、機(jī)器人學(xué)、信息檢索和博弈都廣泛使用搜技術(shù)。2.3搜索技術(shù)搜索技術(shù)是人工智能的基本技術(shù)之一,在人2.3搜索技術(shù)

搜索問題是AI核心理論問題之一一般一個(gè)問題可以用好幾種搜索技術(shù)解決,選擇一種好的搜索技術(shù)對(duì)解決問題的效率很有關(guān)系,甚至關(guān)系到求解問題有沒有解。搜索方法好的標(biāo)準(zhǔn),一般認(rèn)為有兩個(gè)：(1)搜索空間小;(2)解最佳。2.3搜索技術(shù)搜索問題是AI核心理論問題之一2.3搜索技術(shù)

搜索從問題性質(zhì)上來看,可分為一般搜索和博奕搜索,從處理方法上來看,可分為盲目搜索和啟發(fā)式搜索。還可以分得更細(xì)。當(dāng)所給定的問題用狀態(tài)空間表示時(shí),則求解過程可歸結(jié)為對(duì)狀態(tài)空間的搜索。當(dāng)問題有解時(shí),使用不同的搜索策略,找到解的搜索空間范圍是有區(qū)別的。一般來說,對(duì)大空間問題,搜索策略是要解決組合爆炸的問題2.3搜索技術(shù)搜索從問題性質(zhì)上來看,可分為一般搜索和博人工智能之搜索2.3搜索策略

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

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

啟發(fā)式剪枝法(HeuristicPruning)AI領(lǐng)域的搜索方法(3)求與或關(guān)系解圖的搜索法搜索策略分類搜索策略分類盲目搜索方法盲目搜索是不利用問題的有關(guān)信息,而根據(jù)事先確定好的某種固定的搜索方法進(jìn)行搜索。典型的盲目搜索方法是深度優(yōu)先搜索和寬度優(yōu)先搜索(亦稱廣度優(yōu)先搜索),這是兩處基本搜索方法盲目搜索方法盲目搜索是不利用問題的有關(guān)信息,而根據(jù)事先確定回溯策略例：皇后問題在一個(gè)4×4的國(guó)際象棋棋盤上,一次一個(gè)地?cái)[布四枚皇后棋子,擺好后要滿足每行、每列和對(duì)象線上只允許出現(xiàn)一枚棋子,即棋子間不許相互俘獲回溯策略例：皇后問題()()()Q((1,1))()Q((1,1))()QQ((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,1()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,1()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,1()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()Q((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))()((1,1))((1,1)(2,3))((1,1)()((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))()((1,1))((1,1)(2,3))((1,1)()((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))()((1,1))((1,1)(2,3))((1,1)遞歸的思想從前有座山……

從前有座山……

從前有座山……遞歸的思想從前有座山……從前有座山……Fibonacci數(shù)列1202年，意大利家斐波那契在提出了一個(gè)關(guān)于兔子繁殖的問題：

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

不發(fā)生死亡的情況下，由一對(duì)出生的小兔開始，50個(gè)月后會(huì)有多少對(duì)兔子？Fibonacci數(shù)列1202年，意大利家斐波那契在提出了一當(dāng)n＞1時(shí)，F(xiàn)n+2=Fn+1+Fn，而F0=F1=1。當(dāng)n＞1時(shí)，F(xiàn)n+2=Fn+1+Fn，而F0=F1遞歸的思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g遞歸的思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g回溯搜索算法 BACKTRACK（DATA）

DATA：當(dāng)前狀態(tài)。 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL?；厮菟阉魉惴?BACKTRACK（DATA）回溯搜索算法遞歸過程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);回溯搜索算法遞歸過程BACKTRACK(DATA)存在問題及解決辦法問題：深度問題死循環(huán)問題解決辦法：對(duì)搜索深度加以限制記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑存在問題及解決辦法問題：回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向） 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。回溯搜索算法1BACKTRACK1（DATALIST）回溯搜索算法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);回溯搜索算法11, DATA:=FIRST(DATALIS回溯搜索算法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);回溯搜索算法1（續(xù)）9, RULES:=TAIL(RULE一些深入的問題失敗原因分析、多步回溯QQ一些深入的問題失敗原因分析、多步回溯QQ一些深入問題（續(xù)）回溯搜索中知識(shí)的利用 基本思想： 盡可能選取劃去對(duì)角線上位置數(shù)最少的。QQQQ4334一些深入問題（續(xù)）回溯搜索中知識(shí)的利用QQQQ4

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

圖搜索策略問題的引出一些基本概念節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0

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

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

代價(jià)樹寬度優(yōu)先搜索的基本思想是：OPEN表中的節(jié)點(diǎn)在任一時(shí)刻都是按其代價(jià)從小到大排序的，每次擴(kuò)展時(shí)總是從OPEN表中選取代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。其搜索過程如下：代價(jià)樹的寬度憂先搜索邊上標(biāo)有代價(jià)(或費(fèi)用)的樹稱為代價(jià)樹。五城市間的交通路線圖，A城市是出發(fā)地，E城市是目的地，兩城市間的交道費(fèi)用(代價(jià))如左圖小數(shù)字所示。求從A到E的最小費(fèi)用交通路線。交通代價(jià)樹如右圖，解為ACDE代價(jià)樹的寬度優(yōu)先搜索舉例五城市間的交通路線圖，A城市是出發(fā)地，E城市是目的地，兩城市代價(jià)樹的深度憂先搜索代價(jià)樹的寬度優(yōu)先搜索中，每次擴(kuò)展時(shí)總是從OPEN表中選取代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。而代價(jià)樹的深度優(yōu)先搜索是從剛擴(kuò)展出的子節(jié)點(diǎn)中選一個(gè)代價(jià)最小的節(jié)點(diǎn)送入CLOSE表中進(jìn)行考察。其搜索過程如下：解也為ACDE代價(jià)樹的深度憂先搜索代價(jià)樹的寬度優(yōu)先搜索中，每次擴(kuò)展時(shí)總是從啟發(fā)式圖搜索利用知識(shí)來引導(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)解啟發(fā)式圖搜索利用知識(shí)來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)希望：引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。希望：基本思想定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來擴(kuò)展?；舅枷攵x一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一1，啟發(fā)式搜索算法A（A算法）評(píng)價(jià)函數(shù)的格式：

f(n)=g(n)+h(n) f(n)：評(píng)價(jià)函數(shù)

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

h(n)：?jiǎn)l(fā)函數(shù)1，啟發(fā)式搜索算法A（A算法）評(píng)價(jià)函數(shù)的格式：符號(hào)的意義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)的估計(jì)值符號(hào)的意義g*(n)：從s(初始狀態(tài)S0)到n(當(dāng)前狀態(tài)Sn一個(gè)A算法的例子定義評(píng)價(jià)函數(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一個(gè)A算法的例子定義評(píng)價(jià)函數(shù)：2831h計(jì)算舉例 h(n)=42

831

647512345768h計(jì)算舉例 h(n)=428312831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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=32832832832最佳圖搜索算法A*（A*算法）在A算法中，如果滿足條件：

h(n)≤h*(n)

則A算法稱為A*算法。其中h*(n)是從頂點(diǎn)Sn到Sg的最小代價(jià)。由于h*(n)最小代價(jià)通常不知道，因此用h(n)（不在位的將牌數(shù)）進(jìn)行代價(jià)估計(jì)，因此可得h(n)<h*(n),所以上例是A*算法。最佳圖搜索算法A*（A*算法）在A算法中，如果滿足條件：A*條件舉例8數(shù)碼問題h(n)=“不在位”的將牌數(shù)=f1h(n)=將牌“不在位”的距離和=f2采用f2算法的效率會(huì)高于f1的算法，因?yàn)閒2>=f12

831

647512345768將牌1：1將牌2：1將牌6：1將牌8：2A*條件舉例8數(shù)碼問題28312A*算法的性質(zhì)定理1： 對(duì)有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。A*算法的性質(zhì)定理1：AO*算法是A*算法在與或圖上的擴(kuò)展算法。AO*算法中由于與節(jié)點(diǎn)的存在，解對(duì)應(yīng)的不是一條路徑，而是一個(gè)子圖，因此對(duì)頂點(diǎn)的評(píng)估實(shí)際上是對(duì)局部解圖的評(píng)價(jià)。與節(jié)點(diǎn)代價(jià)計(jì)算：最大代價(jià)和代價(jià)或節(jié)點(diǎn)的代價(jià)計(jì)算：最小代價(jià)AO*算法AO*算法是A*算法在與或圖上的擴(kuò)展算法。AO*算法AO*算法舉例7=3+1(左樹)+2+18=3+1+3+18=min(8+1,7+1)AO*算法舉例7=3+1(左樹)+2+18=3+1+3+18與或樹的寬度優(yōu)先與深度優(yōu)先搜索寬度優(yōu)先：12345深度優(yōu)先：13B524與或樹的寬度優(yōu)先與深度優(yōu)先搜索寬度優(yōu)先：12345問題圖搜索是針對(duì)什么知識(shí)表示方法的問題求解方法？什么是圖搜索?其中，重排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ù)加以說明問題圖搜索是針對(duì)什么知識(shí)表示方法的問題求解方法？啟發(fā)式搜索的必要性

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

由于這些選擇的不同,就得到了不同的啟發(fā)式算法啟發(fā)式搜索的必要性根據(jù)啟發(fā)信息,在生成各種搜索樹時(shí)可以考慮*解路徑如粗線所標(biāo)左、上、右、下**S、A、B、…、L、M等為狀態(tài)空間圖中各個(gè)節(jié)點(diǎn)名,其后的小括號(hào)中數(shù)字表示該節(jié)點(diǎn)的評(píng)價(jià)函數(shù)f(n)的估計(jì)值,例如S(4)、L(5)等。

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

九宮重排問題*解路徑如粗線所標(biāo)左、上、右、下九宮重排問題搜索效率比較搜索效率比較啟發(fā)式搜索策略

人工智能問題求解者在兩種基本情況下運(yùn)用啟發(fā)式策略:一個(gè)問題由于在問題陳述和數(shù)據(jù)獲取方面固有的模糊性可能使它沒有一個(gè)確定的解。醫(yī)療診斷即是一例。所給出的一系列癥狀可能有多個(gè)原因,醫(yī)生運(yùn)用啟發(fā)式搜索來選擇最有可能的論斷并依此產(chǎn)生治療計(jì)劃。一個(gè)問題可能有確定解,但是求解過程中的計(jì)算機(jī)代價(jià)令人難以接受。在很多問題(如國(guó)際象棋)中,狀態(tài)空間的增長(zhǎng)特別快,可能的狀態(tài)數(shù)隨著搜索的深度呈指數(shù)級(jí)增長(zhǎng)、分解。在這種情況下,窮盡式搜索策略諸如深度優(yōu)先或廣度優(yōu)先搜索,在一個(gè)給定的較實(shí)際的時(shí)空內(nèi)很可能得不到最終的解和發(fā)明創(chuàng)造的所有規(guī)則一樣,啟發(fā)式策略也是極易出錯(cuò)的啟發(fā)式搜索策略

人工智能問題求解者在兩種基本情況下運(yùn)用啟發(fā)式圖搜索策略圖搜索策略的定義圖搜索策略可看作一種在圖中尋找路徑的方法。初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別代表初始數(shù)據(jù)庫(kù)和滿足終止條件的數(shù)據(jù)庫(kù)。求得把一個(gè)數(shù)據(jù)庫(kù)變換為另一數(shù)據(jù)庫(kù)的規(guī)則序列問題就等價(jià)于求得圖中的一條路徑問題。研究圖搜索的一般策略，能夠給出圖搜索過程的一般步驟。圖搜索算法中的幾個(gè)重要名詞術(shù)語(yǔ)（1）OPEN表與CLOSE表（2）搜索圖與搜索樹圖搜索策略圖搜索策略的定義你可曾聽說過“深藍(lán)”？1997年5月11日，IBM開發(fā)的“深藍(lán)”擊敗了國(guó)際象棋冠軍卡斯帕羅夫。1980年他獲得世界少年組冠軍

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

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

卡氏何許人也？你可曾聽說過“深藍(lán)”？1997年5月11日，IBM開發(fā)人工智能之搜索電腦棋手：永不停歇的挑戰(zhàn)！1988年“深思”擊敗了丹麥特級(jí)大師拉森。1993年“深思”第二代擊敗了丹麥?zhǔn)澜鐑?yōu)秀女棋手小波爾加。電腦棋手：永不停歇的挑戰(zhàn)！1988年“深思”擊敗了丹麥特級(jí)大電腦棋手：永不停歇的挑戰(zhàn)！2001年“更弗里茨”擊敗了除了克拉姆尼克之外的所有排名世界前十位的棋手。2002年10月“更弗里茨”與世界棋王克拉姆尼克在巴林交手，雙方以4比4戰(zhàn)平。2003年1至2月“更年少者”與卡斯帕羅夫在紐約較量，3比3戰(zhàn)平。電腦棋手：永不停歇的挑戰(zhàn)！2001年“更弗里茨”擊敗了除了許多人在努力

許多人在努力

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

——人機(jī)博弈程序的一般設(shè)計(jì)方法以中國(guó)棋為例解謎：電腦是怎樣下棋的

—（1）第一步該做什么？數(shù)據(jù)結(jié)構(gòu)的選取——棋盤表示占用空間-〉少操作速度-〉快是否方便-〉方便在機(jī)器中表示棋局，讓程序知道博弈狀態(tài)。（1）第一步該做什么？數(shù)據(jù)結(jié)構(gòu)的選取——棋盤表示占用空間-〉九列十行十四種不同的棋子三十二個(gè)棋子九列十行十四種不同的棋子三十二個(gè)棋子幾種棋盤表示的方式二維數(shù)組——直觀

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

比特棋盤——用于8*8棋盤（國(guó)際象棋），64位主機(jī)幾種棋盤表示的方式二維數(shù)組——直觀緊湊的數(shù)據(jù)結(jié)構(gòu)——省空間（2）接下來怎么辦？產(chǎn)生合法走步的規(guī)則，使博弈能公正的進(jìn)行，并且能夠判斷對(duì)手是否亂走。依賴于具體棋類特征。是一段將局面所有可能的正確走法羅列出來的程序。稱之為走法產(chǎn)生。（2）接下來怎么辦？產(chǎn)生合法走步的規(guī)則，使博弈能公正的進(jìn)行，幾種走法產(chǎn)生的實(shí)現(xiàn)方式一般做法

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

位運(yùn)算幾種走法產(chǎn)生的實(shí)現(xiàn)方式一般做法建立小型數(shù)據(jù)庫(kù)位運(yùn)算位運(yùn)算走法產(chǎn)生之例尋找象的可走步位運(yùn)算走法產(chǎn)生之例尋找象的可走步位運(yùn)算走法產(chǎn)生之要求一個(gè)基于比特棋盤的完善的數(shù)據(jù)庫(kù)該數(shù)據(jù)庫(kù)應(yīng)位于內(nèi)存中位運(yùn)算走法產(chǎn)生之要求（3）終于到核心了從所有的走法中找出最佳的走法，也就是——搜索（3）終于到核心了從所有的走法中找出最佳的走法，搜索博弈概述諸如下棋、打牌、競(jìng)技、戰(zhàn)爭(zhēng)等一類競(jìng)爭(zhēng)性智能活動(dòng)稱為博弈。博弈有很多種，我們討論最簡(jiǎn)單的"二人零和、全信息、非偶然"博弈，其特征如下：

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

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

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

博弈概述諸如下棋、打牌、競(jìng)技、戰(zhàn)爭(zhēng)等一類競(jìng)爭(zhēng)性智能活動(dòng)稱為博弈概述在博弈過程中，任何一方都希望自己取得勝利。因此，當(dāng)某一方當(dāng)前有多個(gè)行動(dòng)方案可供選擇時(shí)，他總是挑選對(duì)自己最為有利而對(duì)對(duì)方最為不利的那個(gè)行動(dòng)方案。此時(shí)，如果我們站在MAX方的立場(chǎng)上，則可供MAX方選擇的若干行動(dòng)方案之間是"或"關(guān)系，因?yàn)橹鲃?dòng)權(quán)操在MAX方手里，他或者選擇這個(gè)行動(dòng)方案，或者選擇另一個(gè)行動(dòng)方案，完全由MAX方自已決定。當(dāng)MAX方選取任一方案走了一步后，MIN方也有若干個(gè)可供選擇的行動(dòng)方案，此時(shí)這些行動(dòng)方案對(duì)MAX方來說它們之間則是"與"關(guān)系，因?yàn)檫@時(shí)主動(dòng)權(quán)操在MIN方手里，這些可供選擇的行動(dòng)方案中的任何一個(gè)都可能被MIN方選中，MAX方必須應(yīng)付每一種情況的發(fā)生。博弈概述在博弈過程中，任何一方都希望自己取得勝利。因此，當(dāng)某博弈概述這樣，如果站在某一方(如MAX方，即MAX要取勝)，把上述博弈過程用圖表示出來，則得到的是一棵"與或樹"。描述博弈過程的與或樹稱為博弈樹，它有如下特點(diǎn)：

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

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

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

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

博弈概述這樣，如果站在某一方(如MAX方，即MAX要取勝)，搜索算法極大極小值算法

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

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

一字棋游戲極小極大分析法為了不致于生成太大的博弈樹，假設(shè)每次一字棋游戲極小極大分析法集中典型棋局得分值h(n)計(jì)算：(a)h(n)=4-2=2(b)是和局，h(n)=0(c)×方獲勝，h(n)=+∞(d)○方獲勝，h(n)=-∞一字棋游戲極小極大分析法集中典型棋局得分值h(n)計(jì)算：一字棋游戲極小極大分析法第一回合擴(kuò)展深度為2一字棋游戲極小極大分析法第一回合擴(kuò)展深度為2人工智能之搜索一字棋極大極小法的第一階段一字棋極大極小法的第一階段一字棋極大極小法的第二階段一字棋極大極小法的第二階段一字棋極大極小法的第三階段一字棋極大極小法的第三階段Alpha-Beta剪枝技術(shù)極大極小搜索要求先生成與／或樹，然后再計(jì)算各節(jié)點(diǎn)的估值，需要生成規(guī)定深度內(nèi)的所有節(jié)點(diǎn)，因此搜索效率較低?；舅枷牖蛩惴ㄊ?，邊生成博弈樹邊計(jì)算評(píng)估各節(jié)點(diǎn)的倒推值，并且根據(jù)評(píng)估出的倒推值范圍，及時(shí)停止擴(kuò)展那些已無必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機(jī)器開銷，提高了搜索效率。Alpha-Beta剪枝技術(shù)極大極小搜索要求先生成與／或樹，Alpha-Beta剪枝技術(shù)(1)對(duì)于一個(gè)與節(jié)點(diǎn)MIN，若能估計(jì)出其倒推值的上確界β，并且這個(gè)β值不大于MIN的父節(jié)點(diǎn)(一定是或節(jié)點(diǎn))的估計(jì)倒推值的下確界α，即α≥β，則就不必再擴(kuò)展該MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對(duì)MIN父節(jié)點(diǎn)的倒推值已無任何影響了)。這一過程稱為α剪枝。(2)對(duì)于一個(gè)或節(jié)點(diǎn)MAX，若能估計(jì)出其倒推值的下確界α，并且這個(gè)α值不小于MAX的父節(jié)點(diǎn)(一定是與節(jié)點(diǎn))的估計(jì)倒推值的上確界β，即α≥β，則就不必再擴(kuò)展該MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對(duì)MAX父節(jié)點(diǎn)的倒推值已無任何影響了)。這一過程稱為β剪枝。Alpha-Beta剪枝技術(shù)(1)對(duì)于一個(gè)與節(jié)點(diǎn)MIN，若Alpha-Beta剪枝Alpha剪枝Beta剪枝Alpha-Beta剪枝Alpha剪枝Beta剪枝Alpha-Beta剪枝搜索過程Alpha-Beta剪枝搜索過程人工智能之搜索人工智能之搜索搜索算法最佳優(yōu)先算法SSS*和DUAL*算法B*和PB*算法搜索算法最佳優(yōu)先算法Alpha-Beta搜索和極大極小搜索結(jié)合在奇數(shù)層進(jìn)行Alpha剪枝，偶數(shù)層Beta剪枝。和負(fù)極大值搜索結(jié)合在每一層都進(jìn)行Beta剪枝。Alpha-Beta搜索和極大極小搜索結(jié)合和負(fù)極大值搜索結(jié)合（4）最后評(píng)估局面優(yōu)劣，配合搜索技術(shù)做出智能的選擇——估值技術(shù)棋子價(jià)值評(píng)估SideValue=Sum(piecenumber*piecevalue)棋子靈活性Mobility=Sum(movenumber*movevalue)棋盤控制棋子關(guān)系的評(píng)估（威脅、保護(hù)、形、定勢(shì)。并且要考慮到誰走棋）（4）最后評(píng)估局面優(yōu)劣，配合搜索技術(shù)做出智能的選擇——估值技估值的幾種形式終點(diǎn)估值思路清晰，容易設(shè)計(jì)，模塊獨(dú)立性高，同搜索算法耦合程度低速度慢棋子價(jià)值表

T[pieceType][boardWidth][boardHeight]二者結(jié)合動(dòng)態(tài)棋子價(jià)值表估值的幾種形式終點(diǎn)估值棋子價(jià)值表二者結(jié)合動(dòng)態(tài)棋子價(jià)值表估值函數(shù)的內(nèi)容及其調(diào)試Score=aX+bY+cZ+dK+……X=車+馬+炮+……估值函數(shù)的內(nèi)容及其調(diào)試Score=aX+bY+cZ+dK+…參數(shù)確定的方法手工調(diào)整爬山法蒙特卡羅模擬退火遺傳算法參數(shù)確定的方法手工調(diào)整爬山法的缺陷——初值依賴爬山法的缺陷——初值依賴蒙特卡羅使用多種初始參數(shù)，從不同的地方開始多次爬山有足夠多次的爬山，出現(xiàn)頻率最高的結(jié)果是最優(yōu)解的概率就會(huì)足夠大不同初值的大量采樣，使運(yùn)算效率低蒙特卡羅使用多種初始參數(shù)，從不同的地方開始多次爬山模擬退火MetroPolis重要性采樣的基本思想：在尋優(yōu)的開始使用較高的概率進(jìn)行隨機(jī)突跳，隨著尋優(yōu)過程的深入逐步降低這一接受不佳參數(shù)概率。并且隨著搜索的深入，可接受的參數(shù)的不佳程度也越來越小。模擬退火MetroPolis重要性采樣的基本思想：在尋優(yōu)的開模擬退火一次對(duì)參數(shù)改變一點(diǎn)，測(cè)試。提高，保留不提高，在一定概率上繼續(xù)由粗到細(xì)，逼近最優(yōu)參數(shù)模擬退火一次對(duì)參數(shù)改變一點(diǎn)，測(cè)試。遺傳算法隨機(jī)產(chǎn)生一組初始個(gè)體構(gòu)成初始種群，并評(píng)價(jià)每一個(gè)體的適配值。判斷算法收斂準(zhǔn)則是否滿足，若滿足則輸出搜索結(jié)果，否則執(zhí)行以下步驟。根據(jù)適配值大小以一定方式執(zhí)行復(fù)制操作。按交叉概率pc之行交叉操作。按變異概率pm執(zhí)行變異操作。返回上面第二步驟。遺傳算法隨機(jī)產(chǎn)生一組初始個(gè)體構(gòu)成初始種群，并評(píng)價(jià)每一個(gè)體的適遺傳算法適配值：對(duì)個(gè)體進(jìn)行評(píng)價(jià)的指標(biāo)，算法優(yōu)化的主要信息，與個(gè)體的目標(biāo)值對(duì)應(yīng)復(fù)制：復(fù)制概率正比于適配值交叉：交換父代個(gè)體中的部分信息產(chǎn)生后代，繼承變異：隨機(jī)改變個(gè)體中的某些信息產(chǎn)生新個(gè)體，增加種群多樣性遺傳算法適配值：對(duì)個(gè)體進(jìn)行評(píng)價(jià)的指標(biāo)，算法優(yōu)化的主要信息，與標(biāo)準(zhǔn)遺傳算法優(yōu)化框圖標(biāo)準(zhǔn)遺傳算法優(yōu)化框圖GeneticAlgorithms優(yōu)越性全空間并行搜索，重點(diǎn)集中在高性能部分，防止陷入局部最優(yōu)GeneticAlgorithms優(yōu)越性全空間并行搜索，孰優(yōu)孰劣？名局測(cè)試和其他博弈程序?qū)倪x不同的參數(shù)，自相對(duì)弈同向下幾層的搜索結(jié)果比較孰優(yōu)孰劣？名局測(cè)試啟發(fā)式搜索的一個(gè)例子井字博弈中，博弈者在3X3數(shù)組中輪流標(biāo)記，一個(gè)標(biāo)記X，一個(gè)標(biāo)記O,先用標(biāo)記填滿一行、一列或一條對(duì)角線者便贏得博弈。初始狀態(tài)為空棋盤，從起點(diǎn)到終點(diǎn)的路徑表明了贏棋的走法。啟發(fā)式搜索的一個(gè)例子井字博弈中，博弈者在3X3數(shù)組中輪流標(biāo)記人工智能之搜索啟發(fā)式搜索的一個(gè)例子

一個(gè)簡(jiǎn)單的啟發(fā)式策略幾乎可以整個(gè)地消除復(fù)雜的搜索過程。假設(shè)我方為“X”,首先,將棋子走到棋盤上×有最多的贏線的點(diǎn)啟發(fā)式搜索的一個(gè)例子一個(gè)簡(jiǎn)單的啟發(fā)式策略幾乎可以整個(gè)地消除人工智能之搜索啟發(fā)式搜索的一個(gè)例子啟發(fā)信息：將棋子走到棋盤上×有最多的贏線的點(diǎn)啟發(fā)式搜索的一個(gè)例子啟發(fā)信息：將棋子走到棋盤上×有最多的贏線人工智能之搜索衡量一個(gè)搜索策略性能的準(zhǔn)則完備性只要問題有解，在搜索策略的控制下就一定能找到這個(gè)（些）解盡量避免無用搜索增強(qiáng)搜索的目的性，盡量避免產(chǎn)生及考察那些無用的節(jié)點(diǎn)控制開銷小要求搜索策略實(shí)現(xiàn)簡(jiǎn)單，選擇及調(diào)度可用知識(shí)的開銷盡可能小衡量一個(gè)搜索策略性能的準(zhǔn)則完備性問題什么是搜索？有哪兩大類不同的搜索方法？?jī)烧叩膮^(qū)別是什么？廣度優(yōu)先搜索和深度優(yōu)先搜索有和區(qū)別？在何種情況下廣度優(yōu)先搜索優(yōu)于深度優(yōu)先搜索？在何種情況下深度優(yōu)先搜索優(yōu)于廣度優(yōu)先搜索？試談機(jī)器博弈的基本思想。問題什么是搜索？有哪兩大類不同的搜索方法？?jī)烧叩膮^(qū)別是什么？人工智能導(dǎo)論

第二章：搜索、問題求解與博弈人工智能導(dǎo)論

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

表示盤片A所在的柱號(hào)，SK1

表示盤片B所在的柱號(hào)全部可能的狀態(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)例:二階HanoiTower（梵塔）問題設(shè)有三根柱子，在例:二階HanoiTower（梵塔）問題9種狀態(tài)，12種算子構(gòu)成的狀態(tài)空間轉(zhuǎn)移圖：例:二階HanoiTower（梵塔）問題9種狀態(tài)，12種2.2.1狀態(tài)空間表示法總結(jié)：用狀態(tài)空間方法表示問題時(shí)，首先必須定義狀態(tài)的描述形式，通過使用這種描述形式可把問題的一切狀態(tài)都表示出來。其次，還安定義一組算符，通過使用算符可把問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。問題的求解過程是一個(gè)不斷把算符作用于狀態(tài)的過程。如果在使用某個(gè)算符后得到的新狀態(tài)是目標(biāo)狀