搜索策略搜索策略1問題求解過程的形式表示搜索策略概述Nilsson說，搜索是人工智能中的一個(gè)基本問題。人工智能的研究對(duì)象主要是那些沒有成熟方法可依的問題領(lǐng)域，也就是說沒有直接方法可以把有關(guān)問題解出來，而是必須一步步地去摸索求解，這種問題求解過程就是搜索技術(shù)。根據(jù)問題的實(shí)際情況，按照一定的策略或規(guī)則，從知識(shí)庫中尋找可利用的知識(shí)，從而構(gòu)造出一條使問題獲得解決的推理路線的過程稱為搜索。問題求解過程的形式表示搜索策略概述Nilsson說，搜索是人2問題求解過程的形式表示狀態(tài)空間表示法【例3-1】15-數(shù)碼問題在一個(gè)4*4的16宮格棋盤上，擺放有15個(gè)將牌，每一個(gè)都刻有1-15中的某一個(gè)數(shù)碼。棋盤中留有一個(gè)空格，允許其周圍的某一個(gè)將牌向空格移動(dòng)，這樣通過移動(dòng)將牌就可以不斷改變將牌的布局。所要求解的問題：是給定一種初始布局(初始狀態(tài))和一個(gè)目標(biāo)布局(目標(biāo)狀態(tài))，問如何移動(dòng)數(shù)碼實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)變，如圖3-1所示。問題求解過程的形式表示狀態(tài)空間表示法【例3-1】15-數(shù)碼問3數(shù)碼移動(dòng)的狀態(tài)空間圖數(shù)碼移動(dòng)的狀態(tài)空間圖4狀態(tài)空間圖的盲目搜索回溯策略回溯策略的定義是從初始狀態(tài)出發(fā)，不停地、試探性地尋找路徑，直到它到達(dá)目的或“不可解結(jié)點(diǎn)”，即“死胡同”為止。若它遇到不可解結(jié)點(diǎn)就回溯到路徑中最近的父結(jié)點(diǎn)上，查看該結(jié)點(diǎn)是否還有其他的子結(jié)點(diǎn)未被擴(kuò)展。若有，則沿這些子結(jié)點(diǎn)繼續(xù)搜索；如果找到目標(biāo)，就成功退出搜索，返回解題路徑。狀態(tài)空間圖的盲目搜索回溯策略回溯策略的定義是從初始狀態(tài)出發(fā)，5【例3-3】皇后問題4-QueenProblem在4*4的棋盤上，安排4個(gè)Queen，使其互不干擾，即，行、列、斜線上沒有其他棋子，如圖所示。4*4棋盤皇后問題示意圖皇后問題回溯搜索過程圖回溯搜索算法：BACKTRACK（DATA）DATA:當(dāng)前狀態(tài)返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑（以規(guī)則表的形式表示）或FAIL。BACKTRACK（i:integer）{在棋盤上的前i-1行上已安置的各個(gè)棋子互不沖突。本過程從第i行起為各棋子安排合適的位置。當(dāng)i>n時(shí)，表示已求得一個(gè)棋盤的合法布局，則輸出結(jié)果}IFi>nTHEN輸出棋盤的當(dāng)前布局ELSEFORj:=1TOnDO

在第i行j列上安放一個(gè)棋子；

IF當(dāng)前布局合法THENBACKTRACK（i+1）；移走第i行j列的棋子遞歸過程BACKTRACK（DATA）【例3-3】皇后問題4-QueenProblem4*4棋盤皇6廣度優(yōu)先搜索策略如果搜索是以接近起始點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做廣度優(yōu)先搜索（breadth-firstsearch）。1.廣度優(yōu)先搜索廣度優(yōu)先搜索策略如果搜索是以接近起始點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，72.代價(jià)樹廣度優(yōu)先搜索策略在實(shí)際問題中，將一個(gè)狀態(tài)變換成另一個(gè)狀態(tài)的代價(jià)（或費(fèi)用）是不一樣的，也就是狀態(tài)空間圖中各有向邊的代價(jià)是不一樣的，把有向邊上標(biāo)有代價(jià)的搜索樹稱為代價(jià)搜索樹，簡(jiǎn)稱代價(jià)樹。在代價(jià)樹中，把從節(jié)點(diǎn)i到其后繼節(jié)點(diǎn)j的連線之代價(jià)記為C(i,j)，而把從初始節(jié)點(diǎn)S0到任意節(jié)點(diǎn)x的路徑代價(jià)記為g(x)，則g(j)=g(i)+C(i,j)代價(jià)樹廣度優(yōu)先搜索的基本思想，每次從OPEN表中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)移入CLOSED表，因此每當(dāng)一節(jié)點(diǎn)擴(kuò)展后，就要計(jì)算它的所有后繼節(jié)點(diǎn)的代價(jià)，并將它們與OPEN表中已有的待擴(kuò)展節(jié)點(diǎn)按代價(jià)的大小從小到大依次排序，而從OPEN表選擇被擴(kuò)展節(jié)點(diǎn)時(shí)即選擇排在最前面的節(jié)點(diǎn)。算法如下：1G:=G0(G0=s),OPEN:=(s),CLOSED:=();2LOOP:IFOPEN=()THENEXIT(FAIL);3n:=FIRST(OPEN);4IFGOAL(n)THENEXIT(SUCCESS);5REMOVE(n,OPEN),ADD(n,CLOSED);6EXPAND(n)→{mi},G:=ADD(mi,G);7IF目標(biāo)在{mi}中THENEXIT(SUCCESS);8g(j)=g(i)+C(i,j),ADD(OPEN,mj),并標(biāo)記mj到n的指針,對(duì)OPEN按g()進(jìn)行排序;9GOLOOP;廣度優(yōu)先搜索策略2.代價(jià)樹廣度優(yōu)先搜索策略廣度優(yōu)先搜索策略8深度優(yōu)先搜索策略深度優(yōu)先搜索（depth-firstsearch）中，首先擴(kuò)展最新產(chǎn)生的（即最深的）點(diǎn)，只有當(dāng)搜索到達(dá)一個(gè)沒有后裔的狀態(tài)時(shí)，才考慮另一條替代路徑。深度優(yōu)先搜索策略深度優(yōu)先搜索（depth-firstsea9狀態(tài)空間圖的啟發(fā)式搜索策略理論上，如果計(jì)算機(jī)可以使用的時(shí)間和空間是無限的，則僅有盲目搜索算法就已經(jīng)夠用了，但是實(shí)際上并非如此。啟發(fā)式算法的本質(zhì)是部分的放棄算法“一般化、通用化”的蓋面，認(rèn)為有關(guān)具體問題領(lǐng)域的信息可以用來引導(dǎo)搜索，以達(dá)到減少搜索范圍，減低問題復(fù)雜度的目的。可以用于指導(dǎo)搜索過程，并且與具體問題求解有關(guān)的信息叫做啟發(fā)式信息，并把利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索方法（heuristicallysearch）或信息搜索（informedsearch）。啟發(fā)式搜索的原理是，對(duì)于每個(gè)在搜索過程中遇到的新狀態(tài)，計(jì)算一個(gè)估計(jì)值，根據(jù)估計(jì)值的大小，確定下一步將從哪一個(gè)狀態(tài)開始繼續(xù)前進(jìn)。一般以估計(jì)值小者為較優(yōu)的狀態(tài)，以此實(shí)行最佳優(yōu)先搜索。而啟發(fā)信息的強(qiáng)度強(qiáng)時(shí)，會(huì)降低搜索工作量，但是可能導(dǎo)致找不到最優(yōu)解，如果強(qiáng)度弱時(shí)，一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉鳎强赡芸梢哉业阶顑?yōu)解。啟發(fā)信息可以分為三類，第一類是用于決定要擴(kuò)展的下一個(gè)節(jié)點(diǎn)，以免像在廣度優(yōu)先搜索或者深度優(yōu)先搜索中那樣盲目的擴(kuò)展，第二類是在擴(kuò)展一個(gè)節(jié)點(diǎn)的過程中，用于決定要生成哪一個(gè)或者哪幾個(gè)后繼節(jié)點(diǎn)，以免盲目的同時(shí)生成搜索可能的節(jié)點(diǎn)，第三種是用于決定某些應(yīng)該從搜索樹中拋棄或修剪的節(jié)點(diǎn)。狀態(tài)空間圖的啟發(fā)式搜索策略理論上，如果計(jì)算機(jī)可以使用的時(shí)間和10估價(jià)函數(shù)估價(jià)函數(shù)f是對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行估價(jià)，找出一個(gè)最優(yōu)希望的節(jié)點(diǎn)來進(jìn)行擴(kuò)展，f(n)表示節(jié)點(diǎn)n的估價(jià)函數(shù)值。估價(jià)函數(shù)的格式為：f(n)=g(n)+h(n)，其中f(n)為估價(jià)函數(shù)，h(n)為啟發(fā)函數(shù)，g(n)為從初始節(jié)點(diǎn)到n已經(jīng)付出的代價(jià)，h(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑的估計(jì)代價(jià)，它體現(xiàn)了問題的啟發(fā)性信息，其形式要根據(jù)問題的特性確定，如，可以是節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的距離，也可以是節(jié)點(diǎn)n處于最優(yōu)路徑的概率等等。估價(jià)函數(shù)f(n)表示從初始節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑的代價(jià)的估計(jì)值，它的作用是評(píng)價(jià)OPEN表中各節(jié)點(diǎn)的重要程度，決定它們?cè)贠PEN表中的次序，其中g(shù)(n)指出了搜索的橫向趨勢(shì)，它有利于搜索的完備性，但影響搜索的效率。如果只關(guān)心到達(dá)目標(biāo)節(jié)點(diǎn)的路徑，并且希望有較高的搜索效率，則g(n)可以忽略，但是此時(shí)會(huì)影響搜索的完備性，因此要綜合考慮，使g(n)、h(n)各占適當(dāng)?shù)谋戎亍９纼r(jià)函數(shù)與擇優(yōu)搜索估價(jià)函數(shù)估價(jià)函數(shù)f是對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行估價(jià)，找出一個(gè)最優(yōu)希11【例3-6】設(shè)有如下結(jié)構(gòu)的移動(dòng)將牌游戲，其中B代表黑色的將牌，W代表白色的將牌，E代表該位置為空，玩法是：當(dāng)一個(gè)將牌移入相鄰的空位置時(shí)，費(fèi)用為一個(gè)單位；一個(gè)將牌至多可跳過兩個(gè)將牌進(jìn)入空位置，其費(fèi)用等于跳過的將牌數(shù)加1；要求把所有的B移至所有的W的右邊，設(shè)計(jì)估價(jià)函數(shù)中的h(n)BBBWWWE根據(jù)要求可知，W左邊的B越少越接近目標(biāo)，因此可以用W左邊的B的個(gè)數(shù)作為h(n)，即h(n)=3*(每個(gè)W左邊B的個(gè)數(shù)的總和)，乘以3是為了擴(kuò)大h(n)在f(n)中的比重，如對(duì)于BEBWWBW則有h(n)=3*(2+2+3)=21【例3-6】BBBWWWE根據(jù)要求可知，W左邊的B越少越接近12擇優(yōu)搜索有序搜索(OrderedSearch)又稱為最好優(yōu)先搜索(Best-Firstsearch)，總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。有序搜索算法ORDERDSEARCH1G=G0(G0=s),OPEN:=(s)，計(jì)算f(s);2CLOSED:=();3LOOP:IFOPEN=()THENEXIT(FAIL);4n:=MIN_VALUE_F(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5IFGOAL(n)THENEXIT(SUCCESS);6EXPAND(n)→{mi},G:=ADD(mi,G);7標(biāo)記和修改指針：計(jì)算f(mi)

若mi不在OPEN也不在CLOSED，ADD(n,OPEN),標(biāo)記指向n的指針；若mi記在OPEN或CLOSED上，比較f值，若新計(jì)算的f較小，則以新值取代舊值，mi指向n；若mi記在CLOSED，REMOVE(mi,CLOSED),ADD(mi,OPEN)8OPEN中節(jié)點(diǎn)按由小到大排序9GOLOOP擇優(yōu)搜索有序搜索(OrderedSearch)又稱為最好優(yōu)13局部擇優(yōu)搜索是一種啟發(fā)式搜索方法，是對(duì)深度優(yōu)先搜索方法的一種改進(jìn)，它的基本思想是當(dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展后，按f(n)對(duì)每一個(gè)子節(jié)點(diǎn)計(jì)算估價(jià)值，并選擇最小者作為下一個(gè)要考察的節(jié)點(diǎn)，由于每次都只在子節(jié)點(diǎn)范圍內(nèi)選擇下一個(gè)要考察的節(jié)點(diǎn)，范圍比較窄，所以稱為局部擇優(yōu)。算法：1把初始節(jié)點(diǎn)S0放入OPEN表，計(jì)算f(S0)2LOOP:IFEMPTY(OPEN)THENEXIT(FAIL)3n:=FIRST(OPEN);REMOVE(n,OPEN),ADD(n,CLOSED);4IFGOAL(n)THENEXIT(SUCCESS);5若n不可擴(kuò)展，GOLOOP6EXPAND(n)，計(jì)算每個(gè)子節(jié)點(diǎn)的f，將子節(jié)點(diǎn)按f由小到大的順序加入OPEN表的首部，將每個(gè)子節(jié)點(diǎn)指向n；GOLOOP擇優(yōu)搜索全局擇優(yōu)搜索是在搜索中每次從OPEN表的全體節(jié)點(diǎn)中先擇一個(gè)估價(jià)值最小的節(jié)點(diǎn)。算法如下：1把初始節(jié)點(diǎn)S0放入OPEN表，計(jì)算f(S0)2LOOP:IFEMPTY(OPEN)THENEXIT(FAIL)3n:=FIRST(OPEN);REMOVE(n,OPEN),ADD(n,CLOSED);4IFGOAL(n)THENEXIT(SUCCESS);5若n不可擴(kuò)展，GOLOOP6EXPAND(n)，計(jì)算每個(gè)子節(jié)點(diǎn)的f，使每個(gè)子節(jié)點(diǎn)指向n，將每個(gè)子節(jié)點(diǎn)加入OPEN表中，對(duì)OPEN表中的全部節(jié)點(diǎn)按估價(jià)值由小到大的順序進(jìn)行排序7GOLOOP局部擇優(yōu)搜索是一種啟發(fā)式搜索方法，是對(duì)深度優(yōu)先搜索方法的一種14啟發(fā)式搜索A算法首先介紹一下H*算法估值函數(shù)f的含義是f在某個(gè)節(jié)點(diǎn)處的值估計(jì)了從根節(jié)點(diǎn)開始，到達(dá)目標(biāo)節(jié)點(diǎn)，并且經(jīng)過該節(jié)點(diǎn)n的一條代價(jià)為最小的路徑的代價(jià)。H*算法：令g(n)為對(duì)g*(n)的估計(jì)：g(n)>0令h(n)為對(duì)h*(n)的估計(jì)：h(n)≥0令f(n)=g(n)+h(n)為每個(gè)節(jié)點(diǎn)n處的估值函數(shù)使用如此選定的估值函數(shù)f的有序搜索算法即為H*算法其中，g*(n)是從s到n的最短路徑的代價(jià)值，h*(n)從n到g的最短路徑的代價(jià)值，f*(n)=g*(n)+h*(n)是從s到g的最短路徑的代價(jià)值，g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計(jì)值。啟發(fā)式搜索A算法首先介紹一下H*算法15啟發(fā)式搜索A算法A算法：1OPEN:=(s),f(s):=g(s)+h(s)2LOOPIFOPEN=()THENEXIT(FAIL)3n:=FIRST(OPEN);4IFGOAL(n)THENEXIT(SUCCESS);5REMOVE(n,OPEN),ADD(n,CLOSED);6EXPAND(n)→{mi},計(jì)算f(n,mi):=g(n,mi)+h(mi)ADD(mj,OPEN),標(biāo)記mj到n的指針

IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),標(biāo)記mk到n的指針

IFf(n,ml)<f(ml)THENf(ml):=f(n,ml),標(biāo)記ml到n的指針,ADD(ml,OPEN)7OPEN中的節(jié)點(diǎn)按f值由小到大排序8GOLOOP啟發(fā)式搜索A算法A算法：16A*算法1.定義在A算法中，如果滿足條件h(n)≤h*(n)，則A算法稱為A*算法，其中，h(n)稱為h*(n)的下界，它表示某種偏于保守的估計(jì)，當(dāng)h=0時(shí)，A*算法就變?yōu)橛行蛩阉魉惴āＴ贏*算法中，g(n)比較容易求得，它實(shí)際上就是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的路徑代價(jià)，恒有g(shù)(n)≥g*(n)，而且在算法執(zhí)行過程中，隨著更多搜索信息的獲得，g(n)的值呈下降的趨勢(shì)。h(n)的確定依賴于具體問題領(lǐng)域的啟發(fā)性信息，其中h(n)≤h*(n)是十分重要的，它可保證A*算法能找到最優(yōu)解。【例3-8】

在圖中，從節(jié)點(diǎn)S0開始景擴(kuò)展得到x1和x2，且g(x1)=3,g(x2)=7,對(duì)x1擴(kuò)展后得到x2與x3，此時(shí)g(x2)=6，,g(x3)=5，顯然，后來算出的,g(x2)比先前算出的小。A*算法1.定義17A*算法2.A*算法性質(zhì)3.A*算法的可采納性4.A*算法的最優(yōu)性5.A*的復(fù)雜性6.h(n)的單調(diào)性限制A*算法2.A*算法性質(zhì)18與或樹的搜索策略與或圖表示1.分解2.等價(jià)變換3.與或圖的基本概念與或樹的搜索策略與或圖表示1.分解19與或樹的盲目搜索1.廣度優(yōu)先搜索廣度優(yōu)先搜索步驟如下：(1)把初始節(jié)點(diǎn)S0放入OPEN表。(2)LOOP:取出OPEN表第一個(gè)節(jié)點(diǎn)n放入CLOSED表。(3)若n可擴(kuò)展擴(kuò)展n，將其子節(jié)點(diǎn)放入OPEN表尾部，并為每個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針，以備標(biāo)示過程使用調(diào)用可解節(jié)點(diǎn)標(biāo)示過程GOLOOP(4)若n不可擴(kuò)展標(biāo)識(shí)n為不可解節(jié)點(diǎn)調(diào)用不可解節(jié)點(diǎn)標(biāo)識(shí)過程GOLOOP2.深度優(yōu)先搜索深度優(yōu)先搜索步驟如下：(1)把初始節(jié)點(diǎn)S0放入OPEN表。(2)LOOP:取出OPEN表第一個(gè)節(jié)點(diǎn)n放入CLOSED表。(3)若節(jié)點(diǎn)n的深度大于深度界限GOSTEP5(4)若n可擴(kuò)展擴(kuò)展n，將其子節(jié)點(diǎn)放入OPEN表首部，并為每個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針，以備標(biāo)示過程使用調(diào)用可解節(jié)點(diǎn)標(biāo)示過程GOLOOP(5)若n不可擴(kuò)展標(biāo)識(shí)n為不可解節(jié)點(diǎn)調(diào)用不可解節(jié)點(diǎn)標(biāo)識(shí)過程GOLOOP與或樹的盲目搜索1.廣度優(yōu)先搜索2.深度優(yōu)先搜索20與或樹的啟發(fā)式搜索1.解樹的代價(jià)2.希望樹3.與或樹的有序搜索算法與或樹的啟發(fā)式搜索1.解樹的代價(jià)21博弈樹的啟發(fā)式搜索1.博弈舉例【例3-16】剪刀、石頭、布游戲甲乙兩個(gè)人用剪刀石頭布來決定誰休息，誰找水。

乙甲

石頭剪刀布石頭未定、未定休息、找水找水、休息剪刀找水、休息未定、未定休息、找水布休息、找水找水、休息未定、未定博弈樹的啟發(fā)式搜索1.博弈舉例

乙甲

石頭剪刀布石頭未定、未22博弈樹的啟發(fā)式搜索2.博弈要素(1)參與者（Player）：參與者的標(biāo)志是他是否是博弈的利害關(guān)系者；(2)規(guī)則（Rule）：對(duì)博弈作出具體規(guī)定的集合，如參與者行動(dòng)的順序、行動(dòng)時(shí)知道的信息、可選擇的行動(dòng)、行動(dòng)后會(huì)得到的結(jié)果；(3)結(jié)果（Outcome）：所有參與者每一個(gè)可能行動(dòng)的結(jié)果；(4)收益（Payoff）：在每一個(gè)可能的結(jié)果上參與者的得失3.博弈樹4.博弈樹方法

(1)極小極大分析(2)α-β剪枝博弈樹的啟發(fā)式搜索2.博弈要素23(1)極小極大分析極小極大分析基本思想為，設(shè)博弈雙方一方為A一方為B，極小極大分析方是為其中一方如A來尋找一個(gè)最優(yōu)行動(dòng)方案的方法；為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)方案可能產(chǎn)生的后果進(jìn)行比較，考慮每個(gè)方案實(shí)施后對(duì)手可能采取的行動(dòng)，并計(jì)算可能的得分；為計(jì)算得分，需根據(jù)問題的特性信息定義一個(gè)估價(jià)函數(shù)，用來估算當(dāng)前博弈樹端節(jié)點(diǎn)的得分，此時(shí)計(jì)算出的得分稱為靜態(tài)估值；當(dāng)端節(jié)點(diǎn)估值計(jì)算出后，再推算父節(jié)點(diǎn)的得分，稱為倒推值。推算方法是：對(duì)于“或”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最大的得分作為父節(jié)點(diǎn)得分，對(duì)“與”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中最小的得分作為父節(jié)點(diǎn)得分；如果一個(gè)行動(dòng)方案能獲得較大的倒推值，它就是當(dāng)前最好的行動(dòng)方案。極小極大過程如圖所示：(1)極小極大分析24(2)α-β剪枝α-β剪枝的原理為，在極小極大過程中，總是先生成一定深度的博弈樹，然后對(duì)端節(jié)點(diǎn)進(jìn)行估值，再計(jì)算上層節(jié)點(diǎn)的倒推值，效率較低，博弈樹具有“與”節(jié)點(diǎn)與“或”節(jié)點(diǎn)逐層交替出現(xiàn)的特點(diǎn)，如果能邊生成節(jié)點(diǎn)，邊計(jì)算估值及倒推值，就可能刪去一些不必要的節(jié)點(diǎn)，從而減少不必要的工作量，例如，在圖中，由S3與S4的估值計(jì)算的S1的倒推值為3，這表示S0的倒推值最小為3；另外由S5的估值得到S2的倒推值最大為2，因此S0的倒推值為3，此時(shí)S6的值對(duì)上層的計(jì)算沒有影響，可以從博弈樹中剪去。

對(duì)于“與”節(jié)點(diǎn)，取當(dāng)前子節(jié)點(diǎn)中最小倒推值作為倒推值的上界，稱為β，β值永不增加；對(duì)于“或”節(jié)點(diǎn)，取當(dāng)前子節(jié)點(diǎn)中最大倒推值作為倒推值的下界，稱為α，α值永不減少。剪枝的條件：后輩節(jié)點(diǎn)的β值≤祖先節(jié)點(diǎn)的α值時(shí)，α剪枝后輩節(jié)點(diǎn)的α值≥祖先節(jié)點(diǎn)的β值時(shí)，β剪枝簡(jiǎn)記為：極小≤極大，剪枝極大≥極小，剪枝(2)α-β剪枝25本章小結(jié)本章介紹了多種搜索策略。盲目搜索包括廣度優(yōu)先搜索、深度優(yōu)先搜索等。啟發(fā)式搜索主要討論了A*算法，與盲目搜索不同的是，啟發(fā)式搜索運(yùn)用啟發(fā)信息，引用某些準(zhǔn)則或者經(jīng)驗(yàn)來重新排列OPEN表中節(jié)點(diǎn)的順序，使得搜索沿著某個(gè)被認(rèn)為是最有希望的方向擴(kuò)展。本章還介紹了與或樹等知識(shí)，使得讀者對(duì)于搜索策略有全面的了解。本章小結(jié)本章介紹了多種搜索策略。盲目搜索包括廣度優(yōu)先搜索、深26思考與小結(jié)(1)深度優(yōu)先搜索和廣度優(yōu)先搜索有什么區(qū)別？(2)如何證明一個(gè)算法是A*算法？A*算法的可采納性如何證明？(3)用與或圖表示“猴子和香蕉”問題。一只猴子位于水平位置a處，香蕉掛在水平位置c處的上方，猴子想吃香蕉，但高度不夠，夠不著。恰好在b處有可移動(dòng)的臺(tái)子，若猴子站在臺(tái)子上，就可以夠到香蕉。問題是判定猴子的行動(dòng)計(jì)劃，使它能夠到香蕉。(4)一博弈樹如下圖所示，回答如下問題：1）計(jì)算各結(jié)點(diǎn)的倒推估值2）畫出α-β剪枝的結(jié)果思考與小結(jié)(1)深度優(yōu)先搜索和廣度優(yōu)先搜索有什么區(qū)別？27搜索策略搜索策略28問題求解過程的形式表示搜索策略概述Nilsson說，搜索是人工智能中的一個(gè)基本問題。人工智能的研究對(duì)象主要是那些沒有成熟方法可依的問題領(lǐng)域，也就是說沒有直接方法可以把有關(guān)問題解出來，而是必須一步步地去摸索求解，這種問題求解過程就是搜索技術(shù)。根據(jù)問題的實(shí)際情況，按照一定的策略或規(guī)則，從知識(shí)庫中尋找可利用的知識(shí)，從而構(gòu)造出一條使問題獲得解決的推理路線的過程稱為搜索。問題求解過程的形式表示搜索策略概述Nilsson說，搜索是人29問題求解過程的形式表示狀態(tài)空間表示法【例3-1】15-數(shù)碼問題在一個(gè)4*4的16宮格棋盤上，擺放有15個(gè)將牌，每一個(gè)都刻有1-15中的某一個(gè)數(shù)碼。棋盤中留有一個(gè)空格，允許其周圍的某一個(gè)將牌向空格移動(dòng)，這樣通過移動(dòng)將牌就可以不斷改變將牌的布局。所要求解的問題：是給定一種初始布局(初始狀態(tài))和一個(gè)目標(biāo)布局(目標(biāo)狀態(tài))，問如何移動(dòng)數(shù)碼實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)變，如圖3-1所示。問題求解過程的形式表示狀態(tài)空間表示法【例3-1】15-數(shù)碼問30數(shù)碼移動(dòng)的狀態(tài)空間圖數(shù)碼移動(dòng)的狀態(tài)空間圖31狀態(tài)空間圖的盲目搜索回溯策略回溯策略的定義是從初始狀態(tài)出發(fā)，不停地、試探性地尋找路徑，直到它到達(dá)目的或“不可解結(jié)點(diǎn)”，即“死胡同”為止。若它遇到不可解結(jié)點(diǎn)就回溯到路徑中最近的父結(jié)點(diǎn)上，查看該結(jié)點(diǎn)是否還有其他的子結(jié)點(diǎn)未被擴(kuò)展。若有，則沿這些子結(jié)點(diǎn)繼續(xù)搜索；如果找到目標(biāo)，就成功退出搜索，返回解題路徑。狀態(tài)空間圖的盲目搜索回溯策略回溯策略的定義是從初始狀態(tài)出發(fā)，32【例3-3】皇后問題4-QueenProblem在4*4的棋盤上，安排4個(gè)Queen，使其互不干擾，即，行、列、斜線上沒有其他棋子，如圖所示。4*4棋盤皇后問題示意圖皇后問題回溯搜索過程圖回溯搜索算法：BACKTRACK（DATA）DATA:當(dāng)前狀態(tài)返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑（以規(guī)則表的形式表示）或FAIL。BACKTRACK（i:integer）{在棋盤上的前i-1行上已安置的各個(gè)棋子互不沖突。本過程從第i行起為各棋子安排合適的位置。當(dāng)i>n時(shí)，表示已求得一個(gè)棋盤的合法布局，則輸出結(jié)果}IFi>nTHEN輸出棋盤的當(dāng)前布局ELSEFORj:=1TOnDO

在第i行j列上安放一個(gè)棋子；

IF當(dāng)前布局合法THENBACKTRACK（i+1）；移走第i行j列的棋子遞歸過程BACKTRACK（DATA）【例3-3】皇后問題4-QueenProblem4*4棋盤皇33廣度優(yōu)先搜索策略如果搜索是以接近起始點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做廣度優(yōu)先搜索（breadth-firstsearch）。1.廣度優(yōu)先搜索廣度優(yōu)先搜索策略如果搜索是以接近起始點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，342.代價(jià)樹廣度優(yōu)先搜索策略在實(shí)際問題中，將一個(gè)狀態(tài)變換成另一個(gè)狀態(tài)的代價(jià)（或費(fèi)用）是不一樣的，也就是狀態(tài)空間圖中各有向邊的代價(jià)是不一樣的，把有向邊上標(biāo)有代價(jià)的搜索樹稱為代價(jià)搜索樹，簡(jiǎn)稱代價(jià)樹。在代價(jià)樹中，把從節(jié)點(diǎn)i到其后繼節(jié)點(diǎn)j的連線之代價(jià)記為C(i,j)，而把從初始節(jié)點(diǎn)S0到任意節(jié)點(diǎn)x的路徑代價(jià)記為g(x)，則g(j)=g(i)+C(i,j)代價(jià)樹廣度優(yōu)先搜索的基本思想，每次從OPEN表中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)移入CLOSED表，因此每當(dāng)一節(jié)點(diǎn)擴(kuò)展后，就要計(jì)算它的所有后繼節(jié)點(diǎn)的代價(jià)，并將它們與OPEN表中已有的待擴(kuò)展節(jié)點(diǎn)按代價(jià)的大小從小到大依次排序，而從OPEN表選擇被擴(kuò)展節(jié)點(diǎn)時(shí)即選擇排在最前面的節(jié)點(diǎn)。算法如下：1G:=G0(G0=s),OPEN:=(s),CLOSED:=();2LOOP:IFOPEN=()THENEXIT(FAIL);3n:=FIRST(OPEN);4IFGOAL(n)THENEXIT(SUCCESS);5REMOVE(n,OPEN),ADD(n,CLOSED);6EXPAND(n)→{mi},G:=ADD(mi,G);7IF目標(biāo)在{mi}中THENEXIT(SUCCESS);8g(j)=g(i)+C(i,j),ADD(OPEN,mj),并標(biāo)記mj到n的指針,對(duì)OPEN按g()進(jìn)行排序;9GOLOOP;廣度優(yōu)先搜索策略2.代價(jià)樹廣度優(yōu)先搜索策略廣度優(yōu)先搜索策略35深度優(yōu)先搜索策略深度優(yōu)先搜索（depth-firstsearch）中，首先擴(kuò)展最新產(chǎn)生的（即最深的）點(diǎn)，只有當(dāng)搜索到達(dá)一個(gè)沒有后裔的狀態(tài)時(shí)，才考慮另一條替代路徑。深度優(yōu)先搜索策略深度優(yōu)先搜索（depth-firstsea36狀態(tài)空間圖的啟發(fā)式搜索策略理論上，如果計(jì)算機(jī)可以使用的時(shí)間和空間是無限的，則僅有盲目搜索算法就已經(jīng)夠用了，但是實(shí)際上并非如此。啟發(fā)式算法的本質(zhì)是部分的放棄算法“一般化、通用化”的蓋面，認(rèn)為有關(guān)具體問題領(lǐng)域的信息可以用來引導(dǎo)搜索，以達(dá)到減少搜索范圍，減低問題復(fù)雜度的目的。可以用于指導(dǎo)搜索過程，并且與具體問題求解有關(guān)的信息叫做啟發(fā)式信息，并把利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索方法（heuristicallysearch）或信息搜索（informedsearch）。啟發(fā)式搜索的原理是，對(duì)于每個(gè)在搜索過程中遇到的新狀態(tài)，計(jì)算一個(gè)估計(jì)值，根據(jù)估計(jì)值的大小，確定下一步將從哪一個(gè)狀態(tài)開始繼續(xù)前進(jìn)。一般以估計(jì)值小者為較優(yōu)的狀態(tài)，以此實(shí)行最佳優(yōu)先搜索。而啟發(fā)信息的強(qiáng)度強(qiáng)時(shí)，會(huì)降低搜索工作量，但是可能導(dǎo)致找不到最優(yōu)解，如果強(qiáng)度弱時(shí)，一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉鳎强赡芸梢哉业阶顑?yōu)解。啟發(fā)信息可以分為三類，第一類是用于決定要擴(kuò)展的下一個(gè)節(jié)點(diǎn)，以免像在廣度優(yōu)先搜索或者深度優(yōu)先搜索中那樣盲目的擴(kuò)展，第二類是在擴(kuò)展一個(gè)節(jié)點(diǎn)的過程中，用于決定要生成哪一個(gè)或者哪幾個(gè)后繼節(jié)點(diǎn)，以免盲目的同時(shí)生成搜索可能的節(jié)點(diǎn)，第三種是用于決定某些應(yīng)該從搜索樹中拋棄或修剪的節(jié)點(diǎn)。狀態(tài)空間圖的啟發(fā)式搜索策略理論上，如果計(jì)算機(jī)可以使用的時(shí)間和37估價(jià)函數(shù)估價(jià)函數(shù)f是對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行估價(jià)，找出一個(gè)最優(yōu)希望的節(jié)點(diǎn)來進(jìn)行擴(kuò)展，f(n)表示節(jié)點(diǎn)n的估價(jià)函數(shù)值。估價(jià)函數(shù)的格式為：f(n)=g(n)+h(n)，其中f(n)為估價(jià)函數(shù)，h(n)為啟發(fā)函數(shù)，g(n)為從初始節(jié)點(diǎn)到n已經(jīng)付出的代價(jià)，h(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑的估計(jì)代價(jià)，它體現(xiàn)了問題的啟發(fā)性信息，其形式要根據(jù)問題的特性確定，如，可以是節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的距離，也可以是節(jié)點(diǎn)n處于最優(yōu)路徑的概率等等。估價(jià)函數(shù)f(n)表示從初始節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑的代價(jià)的估計(jì)值，它的作用是評(píng)價(jià)OPEN表中各節(jié)點(diǎn)的重要程度，決定它們?cè)贠PEN表中的次序，其中g(shù)(n)指出了搜索的橫向趨勢(shì)，它有利于搜索的完備性，但影響搜索的效率。如果只關(guān)心到達(dá)目標(biāo)節(jié)點(diǎn)的路徑，并且希望有較高的搜索效率，則g(n)可以忽略，但是此時(shí)會(huì)影響搜索的完備性，因此要綜合考慮，使g(n)、h(n)各占適當(dāng)?shù)谋戎亍９纼r(jià)函數(shù)與擇優(yōu)搜索估價(jià)函數(shù)估價(jià)函數(shù)f是對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行估價(jià)，找出一個(gè)最優(yōu)希38【例3-6】設(shè)有如下結(jié)構(gòu)的移動(dòng)將牌游戲，其中B代表黑色的將牌，W代表白色的將牌，E代表該位置為空，玩法是：當(dāng)一個(gè)將牌移入相鄰的空位置時(shí)，費(fèi)用為一個(gè)單位；一個(gè)將牌至多可跳過兩個(gè)將牌進(jìn)入空位置，其費(fèi)用等于跳過的將牌數(shù)加1；要求把所有的B移至所有的W的右邊，設(shè)計(jì)估價(jià)函數(shù)中的h(n)BBBWWWE根據(jù)要求可知，W左邊的B越少越接近目標(biāo)，因此可以用W左邊的B的個(gè)數(shù)作為h(n)，即h(n)=3*(每個(gè)W左邊B的個(gè)數(shù)的總和)，乘以3是為了擴(kuò)大h(n)在f(n)中的比重，如對(duì)于BEBWWBW則有h(n)=3*(2+2+3)=21【例3-6】BBBWWWE根據(jù)要求可知，W左邊的B越少越接近39擇優(yōu)搜索有序搜索(OrderedSearch)又稱為最好優(yōu)先搜索(Best-Firstsearch)，總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。有序搜索算法ORDERDSEARCH1G=G0(G0=s),OPEN:=(s)，計(jì)算f(s);2CLOSED:=();3LOOP:IFOPEN=()THENEXIT(FAIL);4n:=MIN_VALUE_F(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5IFGOAL(n)THENEXIT(SUCCESS);6EXPAND(n)→{mi},G:=ADD(mi,G);7標(biāo)記和修改指針：計(jì)算f(mi)

若mi不在OPEN也不在CLOSED，ADD(n,OPEN),標(biāo)記指向n的指針；若mi記在OPEN或CLOSED上，比較f值，若新計(jì)算的f較小，則以新值取代舊值，mi指向n；若mi記在CLOSED，REMOVE(mi,CLOSED),ADD(mi,OPEN)8OPEN中節(jié)點(diǎn)按由小到大排序9GOLOOP擇優(yōu)搜索有序搜索(OrderedSearch)又稱為最好優(yōu)40局部擇優(yōu)搜索是一種啟發(fā)式搜索方法，是對(duì)深度優(yōu)先搜索方法的一種改進(jìn)，它的基本思想是當(dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展后，按f(n)對(duì)每一個(gè)子節(jié)點(diǎn)計(jì)算估價(jià)值，并選擇最小者作為下一個(gè)要考察的節(jié)點(diǎn)，由于每次都只在子節(jié)點(diǎn)范圍內(nèi)選擇下一個(gè)要考察的節(jié)點(diǎn)，范圍比較窄，所以稱為局部擇優(yōu)。算法：1把初始節(jié)點(diǎn)S0放入OPEN表，計(jì)算f(S0)2LOOP:IFEMPTY(OPEN)THENEXIT(FAIL)3n:=FIRST(OPEN);REMOVE(n,OPEN),ADD(n,CLOSED);4IFGOAL(n)THENEXIT(SUCCESS);5若n不可擴(kuò)展，GOLOOP6EXPAND(n)，計(jì)算每個(gè)子節(jié)點(diǎn)的f，將子節(jié)點(diǎn)按f由小到大的順序加入OPEN表的首部，將每個(gè)子節(jié)點(diǎn)指向n；GOLOOP擇優(yōu)搜索全局擇優(yōu)搜索是在搜索中每次從OPEN表的全體節(jié)點(diǎn)中先擇一個(gè)估價(jià)值最小的節(jié)點(diǎn)。算法如下：1把初始節(jié)點(diǎn)S0放入OPEN表，計(jì)算f(S0)2LOOP:IFEMPTY(OPEN)THENEXIT(FAIL)3n:=FIRST(OPEN);REMOVE(n,OPEN),ADD(n,CLOSED);4IFGOAL(n)THENEXIT(SUCCESS);5若n不可擴(kuò)展，GOLOOP6EXPAND(n)，計(jì)算每個(gè)子節(jié)點(diǎn)的f，使每個(gè)子節(jié)點(diǎn)指向n，將每個(gè)子節(jié)點(diǎn)加入OPEN表中，對(duì)OPEN表中的全部節(jié)點(diǎn)按估價(jià)值由小到大的順序進(jìn)行排序7GOLOOP局部擇優(yōu)搜索是一種啟發(fā)式搜索方法，是對(duì)深度優(yōu)先搜索方法的一種41啟發(fā)式搜索A算法首先介紹一下H*算法估值函數(shù)f的含義是f在某個(gè)節(jié)點(diǎn)處的值估計(jì)了從根節(jié)點(diǎn)開始，到達(dá)目標(biāo)節(jié)點(diǎn)，并且經(jīng)過該節(jié)點(diǎn)n的一條代價(jià)為最小的路徑的代價(jià)。H*算法：令g(n)為對(duì)g*(n)的估計(jì)：g(n)>0令h(n)為對(duì)h*(n)的估計(jì)：h(n)≥0令f(n)=g(n)+h(n)為每個(gè)節(jié)點(diǎn)n處的估值函數(shù)使用如此選定的估值函數(shù)f的有序搜索算法即為H*算法其中，g*(n)是從s到n的最短路徑的代價(jià)值，h*(n)從n到g的最短路徑的代價(jià)值，f*(n)=g*(n)+h*(n)是從s到g的最短路徑的代價(jià)值，g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計(jì)值。啟發(fā)式搜索A算法首先介紹一下H*算法42啟發(fā)式搜索A算法A算法：1OPEN:=(s),f(s):=g(s)+h(s)2LOOPIFOPEN=()THENEXIT(FAIL)3n:=FIRST(OPEN);4IFGOAL(n)THENEXIT(SUCCESS);5REMOVE(n,OPEN),ADD(n,CLOSED);6EXPAND(n)→{mi},計(jì)算f(n,mi):=g(n,mi)+h(mi)ADD(mj,OPEN),標(biāo)記mj到n的指針

IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),標(biāo)記mk到n的指針

IFf(n,ml)<f(ml)THENf(ml):=f(n,ml),標(biāo)記ml到n的指針,ADD(ml,OPEN)7OPEN中的節(jié)點(diǎn)按f值由小到大排序8GOLOOP啟發(fā)式搜索A算法A算法：43A*算法1.定義在A算法中，如果滿足條件h(n)≤h*(n)，則A算法稱為A*算法，其中，h(n)稱為h*(n)的下界，它表示某種偏于保守的估計(jì)，當(dāng)h=0時(shí)，A*算法就變?yōu)橛行蛩阉魉惴āＴ贏*算法中，g(n)比較容易求得，它實(shí)際上就是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的路徑代價(jià)，恒有g(shù)(n)≥g*(n)，而且在算法執(zhí)行過程中，隨著更多搜索信息的獲得，g(n)的值呈下降的趨勢(shì)。h(n)的確定依賴于具體問題領(lǐng)域的啟發(fā)性信息，其中h(n)≤h*(n)是十分重要的，它可保證A*算法能找到最優(yōu)解。【例3-8】

在圖中，從節(jié)點(diǎn)S0開始景擴(kuò)展得到x1和x2，且g(x1)=3,g(x2)=7,對(duì)x1擴(kuò)展后得到x2與x3，此時(shí)g(x2)=6，,g(x3)=5，顯然，后來算出的,g(x2)比先前算出的小。A*算法1.定義44A*算法2.A*算法性質(zhì)3.A*算法的可采納性4.A*算法的最優(yōu)性5.A*的復(fù)雜性6.h(n)的單調(diào)性限制A*算法2.A*算法性質(zhì)45與或樹的搜索策略與或圖表示1.分解2.等價(jià)變換3.與或圖的基本概念與或樹的搜索策略與或圖表示1.分解46與或樹的盲目搜索1.廣度優(yōu)先搜索廣度優(yōu)先搜索步驟如下：(1)把初始節(jié)點(diǎn)S0放入OPEN表。(2)LOOP:取出OPEN表第一個(gè)節(jié)點(diǎn)n放入CLOSED表。(3)若n可擴(kuò)展擴(kuò)展n，將其子節(jié)點(diǎn)放入OPEN表尾部，并為每個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針，以備標(biāo)示過程使用調(diào)用可解節(jié)點(diǎn)標(biāo)示過程GOLOOP(4)若n不可擴(kuò)展標(biāo)識(shí)n為不可解節(jié)點(diǎn)調(diào)用不可解節(jié)點(diǎn)標(biāo)識(shí)過程GOLOOP2.深度優(yōu)先搜索深度優(yōu)先搜索步驟如下：(1)把初始節(jié)點(diǎn)S0放入OPEN表。(2)LOOP:取出OPEN表第一個(gè)節(jié)點(diǎn)n放入CLOSED表。(3)若節(jié)點(diǎn)n的深度大于深度界限GOSTEP5(4)若n可擴(kuò)展擴(kuò)展n，將其子節(jié)點(diǎn)放入OPEN表首部，并為每個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針，以備標(biāo)示過程使用調(diào)用可解節(jié)點(diǎn)標(biāo)示過程GOLOOP(5)若n不可擴(kuò)展標(biāo)識(shí)n為不可解節(jié)點(diǎn)調(diào)用不可解節(jié)點(diǎn)標(biāo)識(shí)過程GOLOOP與或樹的盲目搜索1.廣度優(yōu)先搜索2.深度優(yōu)先搜索47與或樹的啟發(fā)式搜索1.解樹的代價(jià)2.希望樹3.與或樹的有序搜索算法與或樹的啟發(fā)式搜索1.解樹的代價(jià)48博弈樹的啟發(fā)式搜索1.博弈舉