第五章人工智能搜索策略

人工智能

ArtificialIntelligence主講：楊利英西安電子科技大學(xué)計(jì)算機(jī)學(xué)院E_mail：yangliying1208@163.com第五章 搜索策略5.1基本概念5.2狀態(tài)空間的搜索策略5.3與/或樹的搜索策略5.4搜索的完備性與效率5.1基本概念

采用某種策略，在知識(shí)庫(kù)中尋找可利用的知識(shí)，從而構(gòu)造一條代價(jià)較小的推理路線，使問題得到解決的過(guò)程稱為搜索。5.1.1什么是搜索5.1.1什么是搜索搜索分為盲目搜索和啟發(fā)式搜索。

盲目搜索是按照預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略。啟發(fā)式搜索是在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過(guò)程并找到最優(yōu)解。5.1.2狀態(tài)空間表示法狀態(tài)空間用“狀態(tài)”和“算符”來(lái)表示問題。狀態(tài) 狀態(tài)用以描述問題在求解過(guò)程中不同時(shí)刻的狀態(tài)，一般用向量表示算符 使問題從一個(gè)狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€(gè)狀態(tài)的操作稱為算符。狀態(tài)空間由所有可能出現(xiàn)的狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)空間?；仡櫊顟B(tài)空間示例：十五數(shù)碼難題119151341275861321014119415131275861321014119151341275861321014119415131275861321014119151341275861321014119415131275861321014119415138127561321014119415131275861321014回顧5.1.3與/或樹表示法對(duì)于一個(gè)復(fù)雜問題，直接求解往往比較困難。此時(shí)可通過(guò)下述方法進(jìn)行簡(jiǎn)化：（1）分解（2）等價(jià)變換回顧5.1.3與/或樹表示法（1）分解

把一個(gè)復(fù)雜問題分解為若干個(gè)較為簡(jiǎn)單的子問題，每個(gè)子問題又可繼續(xù)分解。重復(fù)此過(guò)程，直到不需要再分解或者不能再分解為止。如此形成“與”樹。（2）等價(jià)變換 利用同構(gòu)或同態(tài)的等價(jià)變換，把原問題變換為若干個(gè)較為容易求解的新問題。如此形成“或”樹?；仡櫯c/或樹分解與等價(jià)變換可以結(jié)合起來(lái)使用，這樣形成的圖稱為“與/或樹”回顧由可解節(jié)點(diǎn)所構(gòu)成，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)為可解節(jié)點(diǎn)的子樹稱為解樹(t表示終止節(jié)點(diǎn))。解樹中一定包含初始節(jié)點(diǎn)。（它對(duì)應(yīng)于原始問題）解樹回顧5.2狀態(tài)空間的搜索策略5.2狀態(tài)空間的搜索策略盲目搜索搜索按規(guī)定的路線進(jìn)行，不使用與問題有關(guān)的啟發(fā)性信息；適用于其狀態(tài)空間圖是樹狀結(jié)構(gòu)的一類問題。啟發(fā)式搜索使用與問題有關(guān)的啟發(fā)性信息，并以這些啟發(fā)性信息指導(dǎo)搜索過(guò)程，可以高效地求解結(jié)構(gòu)復(fù)雜的問題。5.2.1狀態(tài)空間的一般搜索過(guò)程一個(gè)復(fù)雜問題的狀態(tài)空間一般都是十分龐大的。如64階梵塔問題共有3的64次方個(gè)不同的狀態(tài)。把問題的所有狀態(tài)空間都進(jìn)行存儲(chǔ)有時(shí)候是不可能的。把問題的所有狀態(tài)空間都進(jìn)行存儲(chǔ)也是不必要的。因?yàn)榕c解題有關(guān)的狀態(tài)空間往往只是整個(gè)狀態(tài)空間的一部分，只要能生產(chǎn)并存儲(chǔ)這部分狀態(tài)空間就可以求出問題的解。5.2.1狀態(tài)空間的一般搜索過(guò)程如何產(chǎn)生問題需要的狀態(tài)空間從而實(shí)現(xiàn)對(duì)問題的求解呢？答案就是搜索技術(shù)。搜索技術(shù)基本思想：把問題的初始狀態(tài)作為當(dāng)前狀態(tài)，選擇適用的算符對(duì)其操作，生產(chǎn)一組子狀態(tài)，然后檢查目標(biāo)狀態(tài)是否在其中出現(xiàn)。若出現(xiàn)，則搜索成功，找到了問題的解，否則按某種搜索策略從已生成的狀態(tài)中再選擇一個(gè)作為當(dāng)前狀態(tài)。重復(fù)上述過(guò)程，直到目標(biāo)狀態(tài)出現(xiàn)或者不再有可供操作的狀態(tài)及算符為止。5.2.1狀態(tài)空間的一般搜索過(guò)程OPEN表和CLOSE表OPEN表用于存放剛生成的節(jié)點(diǎn)。對(duì)于不同的搜索策略，節(jié)點(diǎn)在OPEN表中的排列順序是不同的。CLOSE表用于存放將要擴(kuò)展的節(jié)點(diǎn)。對(duì)一個(gè)節(jié)點(diǎn)的擴(kuò)展是指：用所有可適用的算符對(duì)該節(jié)點(diǎn)進(jìn)行操作，生成一組子節(jié)點(diǎn) OPEN表 狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)CLOSE表搜索的一般過(guò)程把初始節(jié)點(diǎn)S0放入OPEN表，并建立目前只包含S0的圖，記為G；檢查OPEN表是否為空，若為空則問題無(wú)解，退出；把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入CLOSE表，并計(jì)該節(jié)點(diǎn)為n；考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出；擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把其中不是節(jié)點(diǎn)n先輩的那些子節(jié)點(diǎn)記做集合M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入G中；針對(duì)M中子節(jié)點(diǎn)的不同情況，分別進(jìn)行如下處理：對(duì)于那些未曾在G中出現(xiàn)過(guò)的M成員設(shè)置一個(gè)指向父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把它們放入OPEN表；（不在OPEN表）對(duì)于那些先前已經(jīng)在G中出現(xiàn)過(guò)的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針；（在OPEN表中）對(duì)于那些先前已在G中出現(xiàn)并且已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針；（在CLOSE表中）按某種搜索策略對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序；轉(zhuǎn)第2步。搜索的一般過(guò)程對(duì)一般搜索過(guò)程的一些說(shuō)明一個(gè)節(jié)點(diǎn)經(jīng)一個(gè)算符操作后一般只生成一個(gè)子節(jié)點(diǎn)。但適用于一個(gè)節(jié)點(diǎn)的算符可能有多個(gè)，此時(shí)就會(huì)生成一組子節(jié)點(diǎn)。這些子節(jié)點(diǎn)中可能有些是當(dāng)前擴(kuò)展節(jié)點(diǎn)的父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等，此時(shí)不能把這些先輩節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)的子節(jié)點(diǎn)。對(duì)一般搜索過(guò)程的一些說(shuō)明一個(gè)新生成的節(jié)點(diǎn)，它可能是第一次被生成的節(jié)點(diǎn)，也可能是先前已作為其它節(jié)點(diǎn)的子節(jié)點(diǎn)被生成過(guò)，當(dāng)前又作為另一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)被再次生成。此時(shí)，它究竟應(yīng)選擇哪個(gè)節(jié)點(diǎn)作為父節(jié)點(diǎn)？一般由原始節(jié)點(diǎn)到該節(jié)點(diǎn)的代價(jià)來(lái)決定，處于代價(jià)小的路途上的那個(gè)節(jié)點(diǎn)就作為該節(jié)點(diǎn)的父節(jié)點(diǎn)。對(duì)一般搜索過(guò)程的一些說(shuō)明在搜索過(guò)程中，一旦某個(gè)被考察的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)就得到了一個(gè)解。該解是由從初始節(jié)點(diǎn)到該目標(biāo)節(jié)點(diǎn)路徑上的算符構(gòu)成。如果在搜索中一直找不到目標(biāo)節(jié)點(diǎn)，而且OPEN表中不再有可供擴(kuò)展的節(jié)點(diǎn)，則搜索失敗。對(duì)一般搜索過(guò)程的一些說(shuō)明通過(guò)搜索得到的圖稱為搜索圖，搜索圖是狀態(tài)空間圖的一個(gè)子集。由搜索圖中的所有節(jié)點(diǎn)及反向指針?biāo)鶚?gòu)成的集合是一棵樹，稱為搜索樹。根據(jù)搜索樹可給出問題的解。5.2.2廣度（寬度）優(yōu)先搜索基本思想： 從初始節(jié)點(diǎn)S0開始，逐層地對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點(diǎn)。在第n層的節(jié)點(diǎn)沒有全部擴(kuò)展并考察之前，不對(duì)第n＋1層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。OPEN表中節(jié)點(diǎn)總是按進(jìn)入的先后順序排列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。廣度優(yōu)先搜索過(guò)程把初始節(jié)點(diǎn)S0放入OPEN表。如果OPEN表為空，則問題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的尾部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。重排九宮的廣度優(yōu)先搜索

操作符：空格左移、上移、右移、下移小插曲－關(guān)于九宮問題射雕英雄傳

瑛姑的問題：將一至九這九個(gè)數(shù)字排成三列，不論縱橫斜角，每三字相加都是十五，如何排法？

黃蓉的回答：九宮之義，法以靈龜，二四為肩，六八為足，左三右七，戴九履一，五居中央?；梅絾栴}中國(guó)人首先發(fā)現(xiàn)了幻方

洛水神龜獻(xiàn)奇圖關(guān)于三階幻方的奧秘南宋楊輝研究幻方第一人

幻方問題在我國(guó)古代稱為“縱橫圖”，又叫“九宮算圖”。南宋大數(shù)學(xué)家楊輝在1275年所著的《續(xù)古摘奇算法》兩卷中，除了給出洛書中3階幻方的構(gòu)造方法外，還給出了4階至10階的幻方。楊輝對(duì)3階幻方的解釋29435761816594211714310615138121三階幻方(15)四階幻方(34)歐美的幻方熱德國(guó)畫家和文藝?yán)碚摷襾G勒在1514年創(chuàng)作的一幅銅版雕刻畫《憂傷》中就有一個(gè)4階幻方。名畫《憂傷》現(xiàn)在珍藏于大英博物館。富蘭克林也投入了很大精力研究幻方。名畫《憂傷》廣度優(yōu)先算法中需要注意的問題1、對(duì)于任意一個(gè)可擴(kuò)展的節(jié)點(diǎn)，總是按照固定的操作符的順序?qū)ζ溥M(jìn)行擴(kuò)展（如前面重排九宮例子中的空格左移、上移、右移、下移）。2、在對(duì)任一節(jié)點(diǎn)進(jìn)行擴(kuò)展的時(shí)候，如果所得的某個(gè)子節(jié)點(diǎn)（狀態(tài)）前面已經(jīng)出現(xiàn)過(guò)，則立即將其放棄，不再重復(fù)畫出（不送入OPEN表）。因此，廣度優(yōu)先搜索的本質(zhì)是：以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，在狀態(tài)空間圖中按照廣度優(yōu)先的原則，生成一棵搜索樹。廣度優(yōu)先搜索的特點(diǎn)優(yōu)點(diǎn)： 只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。缺點(diǎn)： 廣度優(yōu)先搜索盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無(wú)用節(jié)點(diǎn)，搜索效率低。5.2.3深度優(yōu)先搜索基本思想：從初始節(jié)點(diǎn)開始，在其子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，若不是目標(biāo)節(jié)點(diǎn)，則再在該子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，一直如此向下搜索。當(dāng)?shù)竭_(dá)某個(gè)子節(jié)點(diǎn)，且該子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察。深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別：廣度優(yōu)先搜索是將節(jié)點(diǎn)n的子節(jié)點(diǎn)放入到OPEN表的尾部，而深度優(yōu)先搜索是把節(jié)點(diǎn)n的子節(jié)點(diǎn)放入到OPEN表的首部。深度優(yōu)先搜索過(guò)程把初始節(jié)點(diǎn)S0放入OPEN表。如果OPEN表為空，則問題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。重排九宮的深度優(yōu)先搜索操作符：空格左移、上移、右移、下移深度優(yōu)先搜索的特點(diǎn)在深度優(yōu)先搜索中，搜索一旦進(jìn)入某個(gè)分支，就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上，則可較快地得到解。但是，如果目標(biāo)節(jié)點(diǎn)不在此分支上，而該分支又是一個(gè)無(wú)窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的，即使問題有解，它也不一定能求得解。用深度優(yōu)先求得的解，不一定是路徑最短的解。本質(zhì)：以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，在狀態(tài)空間圖中按照深度優(yōu)先的原則，生成一棵搜索樹。5.2.4有界深度優(yōu)先搜索基本思想：對(duì)深度優(yōu)先搜索引入搜索深度界限（設(shè)為dm），當(dāng)搜索深度達(dá)到了深度界限，而仍未出現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，就換一個(gè)分支進(jìn)行搜索?！坝薪纭笔菫榱私鉀Q深度優(yōu)先搜索不完備的問題，避免陷入無(wú)窮分支的死循環(huán)。有界深度優(yōu)先搜索過(guò)程把初始節(jié)點(diǎn)S0放入OPEN表中，置S0的深度d(S0)=0。如果OPEN表為空，則問題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表。考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。若節(jié)點(diǎn)n的深度d(n)=dm，則轉(zhuǎn)第2步（此時(shí)節(jié)點(diǎn)n位于CLOSE表，但并未進(jìn)行擴(kuò)展）。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的首部，為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，將每一個(gè)子節(jié)點(diǎn)的深度設(shè)置為d(n)+1，然后轉(zhuǎn)第2步。對(duì)有界深度優(yōu)先搜索的說(shuō)明如果問題有解，且其路徑長(zhǎng)度≤dm，則上述搜索過(guò)程一定能求得解。但是，若解的路徑長(zhǎng)度>dm,則上述搜索過(guò)程就得不到解。這說(shuō)明在有界深度優(yōu)先搜索中，深度界限的選擇是很重要的。要恰當(dāng)?shù)亟o出dm的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。有界深度優(yōu)先搜索的改進(jìn)先任意設(shè)定一個(gè)較小的數(shù)作為dm，然后進(jìn)行上述的有界深度優(yōu)先搜索，當(dāng)搜索達(dá)到了指定的深度界限dm仍未發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)，并且CLOSE表中仍有待擴(kuò)展節(jié)點(diǎn)時(shí)，就將這些節(jié)點(diǎn)送回OPEN表，同時(shí)增大深度界限dm，繼續(xù)向下搜索。如此不斷地增大dm，只要問題有解，就一定可以找到它。但此時(shí)找到的解不一定是最優(yōu)解。有界深度優(yōu)先搜索的改進(jìn)2.為了找到最優(yōu)解，可增設(shè)一個(gè)表R，每找到目標(biāo)節(jié)點(diǎn)Sg后，就把它放入到R的前面，并令dm等于該目標(biāo)節(jié)點(diǎn)所對(duì)應(yīng)的路徑長(zhǎng)度，然后繼續(xù)搜索。由于后求得的解的路徑長(zhǎng)度不會(huì)超過(guò)先求得的解的路徑長(zhǎng)度，所以最后求得的解一定是最優(yōu)解。重排九宮的有界深度優(yōu)先搜索設(shè)深度界限dm＝45.2.5代價(jià)樹的廣度優(yōu)先搜索邊上標(biāo)有代價(jià)(或費(fèi)用)的樹稱為代價(jià)樹。用g(x)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的代價(jià)，用c(x1,x2)表示從父節(jié)點(diǎn)x1到子節(jié)點(diǎn)x2的代價(jià)，則有：g(x2)=g(x1)+c(x1,x2)5.2.5代價(jià)樹的廣度優(yōu)先搜索每次從OPEN表中選擇節(jié)點(diǎn)往CLOSE表傳送時(shí)，總是選擇其中代價(jià)最小的節(jié)點(diǎn)。也就是說(shuō)，OPEN表中的節(jié)點(diǎn)在任一時(shí)刻都是按其代價(jià)從小到大排序的。代價(jià)小的節(jié)點(diǎn)排在前面，代價(jià)大的節(jié)點(diǎn)排在后面。如果問題有解，代價(jià)樹的廣度優(yōu)先搜索一定可以求得解，并且求出的是最優(yōu)解。該算法應(yīng)用的條件:該算法是針對(duì)代價(jià)樹的算法。為了采用該算法對(duì)圖進(jìn)行搜索，必須先將圖轉(zhuǎn)換為代價(jià)樹。代價(jià)樹廣度優(yōu)先搜索過(guò)程把初始節(jié)點(diǎn)S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，并將各子節(jié)點(diǎn)放入OPEN表中；計(jì)算各子節(jié)點(diǎn)的代價(jià)，按各節(jié)點(diǎn)的代價(jià)對(duì)OPEN表中的全部節(jié)點(diǎn)進(jìn)行排序(按從小到大的順序)，然后轉(zhuǎn)第2步。代價(jià)樹示例圖到代價(jià)樹的轉(zhuǎn)換求A到E的最小費(fèi)用交通路線代價(jià)樹的廣度優(yōu)先搜索5.2.6代價(jià)樹的深度優(yōu)先搜索在代價(jià)樹的廣度優(yōu)先搜索中，每次都是從OPEN表的全體節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)送入CLOSE表進(jìn)行考察在代價(jià)樹的深度優(yōu)先搜索中，是從剛擴(kuò)展出的子節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)送入CLOSE表進(jìn)行考察代價(jià)樹的深度優(yōu)先搜索過(guò)程把初始節(jié)點(diǎn)S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表。考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)按“邊”代價(jià)從小到大的順序放到OPEN表中的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。代價(jià)樹的深度優(yōu)先搜索是不完備的。

總結(jié)

1、上述各種搜索方法的本質(zhì)是，以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，按照既定的策略對(duì)狀態(tài)空間圖進(jìn)行遍歷，并希望能夠盡早發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)。2、由于對(duì)狀態(tài)空間圖遍歷的策略是既定的，因此這些方法統(tǒng)稱為盲目搜索方法。5.2.7啟發(fā)式搜索盲目搜索具有較大的盲目性，產(chǎn)生的無(wú)用節(jié)點(diǎn)較多，效率不高。啟發(fā)式搜索采用問題自身的特性信息，以指導(dǎo)搜索朝著最有希望的方向前進(jìn)。這種搜索針對(duì)性較強(qiáng)，因而效率較高。1.啟發(fā)性信息與估價(jià)函數(shù)可用于指導(dǎo)搜索過(guò)程，且與具體問題有關(guān)的信息稱為啟發(fā)性信息。用于評(píng)估節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)。其一般形式為：f(x)=g(x)+h(x)其中g(shù)(x)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的代價(jià)；h(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的代價(jià)的估計(jì)，它體現(xiàn)了問題的啟發(fā)性信息，稱為啟發(fā)函數(shù)。f(x)決定節(jié)點(diǎn)在OPEN表中的次序。1.啟發(fā)性信息與估價(jià)函數(shù)g(x)指出了搜索的橫向趨勢(shì)，有利于搜索的完備性，但影響搜索的效率。h(x)指出了搜索的縱向趨勢(shì)，有利于提高搜索的效率，但影響搜索的完備性。確定f(x)時(shí)要使g(x)+h(x)各占適當(dāng)比重。啟發(fā)函數(shù)示例設(shè)有如下結(jié)構(gòu)的移動(dòng)將牌游戲：游戲規(guī)則：當(dāng)一個(gè)牌移入相鄰的空位置時(shí)，費(fèi)用為一個(gè)單位。一個(gè)牌至多可跳過(guò)兩個(gè)牌進(jìn)入空位置，其費(fèi)用等于跳過(guò)的牌數(shù)加1。要求：把所有的B都移至W的右邊，請(qǐng)?jiān)O(shè)計(jì)啟發(fā)函數(shù)h(x)。解：根據(jù)要求可知，W左邊的B越少越接近目標(biāo)，因此可用W左邊B的個(gè)數(shù)作為h(x),即h(x)=3×(每個(gè)W左邊B的個(gè)數(shù)的總和)這里乘以系數(shù)3是為了擴(kuò)大h(x)在f(x)中的比重。BBBWWWEBEBWWBW例如下面這一狀態(tài)：h(x)=3×(2+2+3)=212.局部擇優(yōu)搜索局部擇優(yōu)搜索是一種啟發(fā)式搜索方法，是對(duì)深度優(yōu)先搜索方法的一種改進(jìn)?；舅枷耄寒?dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展以后，按f(x)對(duì)每一個(gè)子節(jié)點(diǎn)計(jì)算估價(jià)值，并選擇最小者作為下一個(gè)要考察的節(jié)點(diǎn)。局部擇優(yōu)搜索過(guò)程把初始節(jié)點(diǎn)S0放入OPEN表，計(jì)算f(S0)。如果OPEN表為空，則問題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表。考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并按估價(jià)值從小到大的順序放到OPEN表中的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。2.局部擇優(yōu)搜索在局部擇優(yōu)搜索中，若令f(x)=g(x)，則局部擇優(yōu)搜索就成為代價(jià)樹的深度優(yōu)先搜索。在局部擇優(yōu)搜索中，若令f(x)=d(x)，這里d(x)表示節(jié)點(diǎn)x的深度，則局部擇優(yōu)搜索就成為深度優(yōu)先搜索。因此：深度優(yōu)先搜索、代價(jià)樹的深度優(yōu)先搜索均為局部擇優(yōu)搜索的特例。3.全局擇優(yōu)搜索每當(dāng)要選擇下一個(gè)節(jié)點(diǎn)進(jìn)行考察時(shí)，局部擇優(yōu)搜索只是從剛生成的子節(jié)點(diǎn)中選擇一個(gè)估價(jià)值最小的節(jié)點(diǎn)。其選擇范圍比較窄。每當(dāng)要選擇下一個(gè)節(jié)點(diǎn)進(jìn)行考察時(shí)，全局擇優(yōu)搜索每次總是從OPEN表的全體節(jié)點(diǎn)中選擇一個(gè)估價(jià)值最小的節(jié)點(diǎn)。全局擇優(yōu)搜索過(guò)程把初始節(jié)點(diǎn)S0放入OPEN表，計(jì)算f(S0)。如果OPEN表為空，則問題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針。把這些子節(jié)點(diǎn)都送入OPEN表中，然后對(duì)OPEN表中的全部節(jié)點(diǎn)按估價(jià)值從小至大的順序進(jìn)行排序，然后轉(zhuǎn)第2步。3.全局擇優(yōu)搜索在全局擇優(yōu)搜索中，若令f(x)=g(x)，則它就成為代價(jià)樹的廣度優(yōu)先搜索。在全局擇優(yōu)搜索中，若令f(x)=d(x)，這里d(x)表示節(jié)點(diǎn)x的深度，則它就成為廣度優(yōu)先搜索。因此：廣度優(yōu)先搜索、代價(jià)樹的廣度優(yōu)先搜索是全局擇優(yōu)搜索的兩個(gè)特例。重排九宮問題的全局擇優(yōu)搜索樹設(shè)估價(jià)函數(shù)為f(x)=d(x)+h(x)，其中，d(x)表示節(jié)點(diǎn)x的深度，h(x)表示節(jié)點(diǎn)x的格局與目標(biāo)節(jié)點(diǎn)格局不相同的牌數(shù)。5.3與/或樹的搜索策略5.3.1與/或樹的一般搜索過(guò)程5.3.2博弈樹的啟發(fā)式搜索5.3.3α–β剪枝技術(shù)5.3與/或樹的搜索策略5.3與/或樹的搜索策略用與/或樹方法求解問題時(shí)，首先要定義問題的描述方法及分解和變換問題的算符，然后就可以用它們通過(guò)搜索生成與/或樹，從而求得原始問題的解。在與/或樹中，由可解子節(jié)點(diǎn)來(lái)確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為可解節(jié)點(diǎn)的過(guò)程稱為可解標(biāo)示過(guò)程；由不可解子節(jié)點(diǎn)來(lái)確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為不可解節(jié)點(diǎn)的過(guò)程稱為不可解標(biāo)示過(guò)程；在與/或樹搜索過(guò)程中，將反復(fù)使用可解和不可解標(biāo)示過(guò)程，直到初始節(jié)點(diǎn)被標(biāo)示為可解或不可解節(jié)點(diǎn)為止。5.3.1與/或樹的一般搜索過(guò)程把原始問題作為初始節(jié)點(diǎn)S0，并把S0作為當(dāng)前節(jié)點(diǎn)；應(yīng)用分解或等價(jià)算法對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展；為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第2和第3步，期間將反復(fù)使用可解和不可解標(biāo)示過(guò)程，直到初始節(jié)點(diǎn)被標(biāo)示為可解或不可解節(jié)點(diǎn)為止。由這個(gè)搜索過(guò)程形成的節(jié)點(diǎn)和指針結(jié)構(gòu)稱為搜索樹。與/或樹的廣度優(yōu)先搜索把初始節(jié)點(diǎn)S0放入OPEN表。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表。若節(jié)點(diǎn)n可擴(kuò)展，則做如下工作。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的尾部，并為每個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針，以備標(biāo)示過(guò)程使用。考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。如有，則標(biāo)示這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并用可解標(biāo)示過(guò)程對(duì)其先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)示。如果初始節(jié)點(diǎn)S0也被標(biāo)示為可解節(jié)點(diǎn)，則得到了解樹，搜索成功，退出；如果不能確定S0為可解節(jié)點(diǎn)，則從OPEN表中刪去具有可解先輩的節(jié)點(diǎn)。轉(zhuǎn)第2步。若節(jié)點(diǎn)n不可擴(kuò)展，則做如下工作。標(biāo)示節(jié)點(diǎn)n為不可解節(jié)點(diǎn)。用不可解標(biāo)示過(guò)程對(duì)n的先輩節(jié)點(diǎn)中的不可解節(jié)點(diǎn)進(jìn)行標(biāo)示。如果初始節(jié)點(diǎn)S0也被標(biāo)示為不可解節(jié)點(diǎn)，則搜索失敗，退出；如果不能確定S0為不可解節(jié)點(diǎn)，則從OPEN表中刪去具有不可解先輩的節(jié)點(diǎn)。轉(zhuǎn)第2步。與/或樹的（有界）深度優(yōu)先搜索把初始節(jié)點(diǎn)S0放入OPEN表。把OPEN表的第個(gè)節(jié)一點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表。若節(jié)點(diǎn)n的深度大于等于深度界限，則轉(zhuǎn)第5步中的第①。若節(jié)點(diǎn)n可擴(kuò)展，則做如下工作。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的首部，并為每個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針，以備標(biāo)示過(guò)程使用?？疾爝@些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。如有，則標(biāo)示這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并用可解標(biāo)示過(guò)程對(duì)其先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)示。如果初始節(jié)點(diǎn)S0也被標(biāo)示為可解節(jié)點(diǎn)，則得到了解樹，搜索成功，退出；如果不能確定S0為可解節(jié)點(diǎn)，則從OPEN表中刪去具有可解先輩的節(jié)點(diǎn)。轉(zhuǎn)第2步。若節(jié)點(diǎn)n不可擴(kuò)展，則做如下工作。標(biāo)示節(jié)點(diǎn)n為不可解節(jié)點(diǎn)。用不可解標(biāo)示過(guò)程對(duì)n的先輩節(jié)點(diǎn)中的不可解節(jié)點(diǎn)進(jìn)行標(biāo)示。如果初始節(jié)點(diǎn)S0也被標(biāo)示為不可解節(jié)點(diǎn)，則搜索失敗，退出；如果不能確定S0為不可解節(jié)點(diǎn)，則從OPEN表中刪去具有不可解先輩的節(jié)點(diǎn)。轉(zhuǎn)第2步。與/或樹的廣度和深度優(yōu)先搜索舉例A廣度優(yōu)先的擴(kuò)展順序：.5深度優(yōu)先的擴(kuò)展順序（規(guī)定深度界限為4）：1.3.B.5.2.4A,B為不可解的端節(jié)點(diǎn)t1,t2,t3,t4為終止節(jié)點(diǎn)1t2t1t4t354B325.3.2博弈樹的啟發(fā)式搜索1.博弈樹的基本概念博弈：諸如下棋、打牌、戰(zhàn)爭(zhēng)等一類競(jìng)爭(zhēng)性智能活動(dòng)?！岸肆愫?、全信息、非偶然”博弈（1）對(duì)壘的雙方A、B輪流采取行動(dòng)，博弈的結(jié)果只有三種情況：A勝B敗，A敗B勝，平局。（2）對(duì)壘過(guò)程中，任何一方都了解當(dāng)前的格局及過(guò)去的歷史。（3）雙方都是理智的決定自己的行動(dòng)的。博弈樹描述博弈過(guò)程的與/或樹稱為博弈樹，它具有如下特點(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)系。雙方輪流擴(kuò)展。（3）所有能使己方獲勝的終局都是可解節(jié)點(diǎn)，使對(duì)方獲勝的終局是不可解節(jié)點(diǎn)。博弈樹是始終站在一方的立場(chǎng)上得出的。2.極大極小分析法極大極小分析法是在二人博弈中，為了使己方獲勝而采用的分析方法?；舅枷肴缦拢海?）為博弈雙方中的一方尋找一個(gè)最優(yōu)行動(dòng)方案。（2）要考慮每一方案實(shí)施后對(duì)方可能采取的所有行動(dòng)，并計(jì)算可能的得分。（3）為計(jì)算得分，需要定義一個(gè)估價(jià)函數(shù)，用來(lái)估算當(dāng)前博弈樹端節(jié)點(diǎn)的得分（靜態(tài)估算值）。（4）由端節(jié)點(diǎn)的得分估算父節(jié)點(diǎn)的得分（倒推值）：對(duì)或節(jié)點(diǎn)，選子節(jié)點(diǎn)中最大的得分給父節(jié)點(diǎn)；對(duì)與節(jié)點(diǎn)，選子節(jié)點(diǎn)中最小的得分給父節(jié)點(diǎn)。（5）如果一個(gè)行動(dòng)方案能獲得較大的倒推值，則它就是當(dāng)前最好的方案。極大極小分析法面臨的問題試圖用完整的博弈樹來(lái)進(jìn)行極大極小分析是困難的?？尚械姆椒ǎ荷梢欢ㄉ疃鹊牟┺臉洌筮M(jìn)行極大極小分析法，找出當(dāng)前最好的方案。此后再在已經(jīng)選定的分支上擴(kuò)展一定深度，再選最好的方案。如此進(jìn)行下去，直到取得勝敗的結(jié)果為止。5.3.3α–β剪枝技術(shù)在極大極小分析法中，總是先生成一定深度的博弈樹，對(duì)端節(jié)點(diǎn)進(jìn)行估值，然后計(jì)算上層節(jié)點(diǎn)的倒推值。這樣做效率并不高。鑒于博弈樹具有或節(jié)點(diǎn)和與節(jié)點(diǎn)交替出現(xiàn)的特點(diǎn)，如果能夠邊生成節(jié)點(diǎn)邊估值，就有可能刪去一些不必要的節(jié)點(diǎn)。剪枝技術(shù)就是基于此提出的。通過(guò)邊生成節(jié)點(diǎn)邊計(jì)算估值，從而刪去某些分枝的技術(shù)稱為α–β剪枝技術(shù)。與節(jié)點(diǎn)取當(dāng)前子節(jié)點(diǎn)中的最小倒推值最為它倒推值的上界，稱為β值；或節(jié)點(diǎn)取當(dāng)前子節(jié)點(diǎn)中的最大倒推值最為它倒推值的下界，稱為α值。α–β剪枝技術(shù)53BS023S1S3S4S5S6S2例：圖中S6尚未計(jì)算估值則：由α–β剪枝技術(shù)可知，S6形成的分枝