人工智能-5搜索策略

1人工智能

ArtificialIntelligence主講：鮑軍鵬博士西安交通大學(xué)電信學(xué)院計(jì)算機(jī)系電子郵箱：dr.baojp@版本：2.02010年1月第五章 搜索策略5.1概述5.2狀態(tài)空間搜索5.3與或樹(shù)搜索25.1概述5.1.1什么是搜索根據(jù)問(wèn)題的實(shí)際情況不斷尋找可利用的知識(shí)，從而構(gòu)造一條代價(jià)較少的推理路線，使問(wèn)題得到圓滿解決的過(guò)程稱為搜索。在人工智能中即使對(duì)于結(jié)構(gòu)性能較好，理論上有算法可依的問(wèn)題，由于問(wèn)題本身的復(fù)雜性以及計(jì)算機(jī)在時(shí)間、空間上的局限性，往往也需要通過(guò)搜索來(lái)求解。3搜索的分類搜索分為盲目搜索和啟發(fā)式搜索。盲目搜索是按照預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略。啟發(fā)式搜索是在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。45.1.2狀態(tài)空間表示法問(wèn)題求解過(guò)程可以看作一個(gè)搜索過(guò)程。狀態(tài)空間表示法是用來(lái)表示問(wèn)題及其搜索過(guò)程的一種方法。它是人工智能中最基本的一種形式化方法。狀態(tài)空間用“狀態(tài)”和“算符”來(lái)表示問(wèn)題。狀態(tài) 狀態(tài)用以描述問(wèn)題求解過(guò)程中不同時(shí)刻的狀況，是一個(gè)數(shù)據(jù)結(jié)構(gòu)，一般用一組變量的有序組合表示：SK=(Sk0,Sk1,…)當(dāng)每一個(gè)分量的值確定時(shí)，就得到了一個(gè)具體的狀態(tài)。算符 引起狀態(tài)中某些分量發(fā)生變化，從而使問(wèn)題從一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)的操作稱為算符。在產(chǎn)生式系統(tǒng)中，一條產(chǎn)生式規(guī)則就是一個(gè)算符。狀態(tài)空間由問(wèn)題的全部狀態(tài)及一切可用算符所構(gòu)成的集合稱為問(wèn)題的狀態(tài)空間，一般用一個(gè)三元組表示：(S,F,G)其中S是問(wèn)題所有初始狀態(tài)的集合；F是算符的集合；G是目標(biāo)狀態(tài)的集合。狀態(tài)空間的圖示形式稱為狀態(tài)空間圖。5狀態(tài)空間示例——二階梵塔問(wèn)題 設(shè)用SK=(Sk0,Sk1)表示問(wèn)題的狀態(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)

問(wèn)題的初始狀態(tài)集合為S={S0},目標(biāo)狀態(tài)集合為G={S4,S8}。 算符分別用A(i,j)及B(i,j)。A(i,j)表示把A金片從第i號(hào)柱移到第j號(hào)柱。

B(i,j)與之同理。算符共有12個(gè)。 在狀態(tài)空間圖中，從初始節(jié)點(diǎn)(1,1)到目標(biāo)節(jié)點(diǎn)(2,2)或(3,3)的任何一條通路都是問(wèn)題的一個(gè)解。其中最短的路徑長(zhǎng)度是3，它由3個(gè)算符組成。例如:A(1,3),B(1,2),A(3,2)6狀態(tài)空間用狀態(tài)空間方法表示問(wèn)題，首先必須定義狀態(tài)的描述形式，把問(wèn)題的一切狀態(tài)都表示出來(lái)。其次要定義一組算符。問(wèn)題的求解過(guò)程是一個(gè)不斷把算符作用于狀態(tài)的過(guò)程。如果在使用某個(gè)算符后得到的新?tīng)顟B(tài)是目標(biāo)狀態(tài)，就得到了問(wèn)題的一個(gè)解。這個(gè)解是從初始狀態(tài)到目標(biāo)狀態(tài)所用算符構(gòu)成的序列。算符的一次使用，就使問(wèn)題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。使用算符最少的解或者總代價(jià)最少的解稱為最優(yōu)解。對(duì)任何一個(gè)狀態(tài)，可使用的算符可能不止一個(gè)。這樣由一個(gè)狀態(tài)所生成的后繼狀態(tài)就可能有多個(gè)。此時(shí)首先對(duì)哪一個(gè)狀態(tài)進(jìn)行操作，就取決于搜索策略。75.1.3與或樹(shù)表示法與或樹(shù)是用于表示問(wèn)題及其求解過(guò)程的又一種形式化方法，通常用于表示比較復(fù)雜問(wèn)題的求解。對(duì)于一個(gè)復(fù)雜問(wèn)題，直接求解往往比較困難。此時(shí)可通過(guò)下述方法進(jìn)行簡(jiǎn)化：分解 把一個(gè)復(fù)雜問(wèn)題分解為若干個(gè)較為簡(jiǎn)單的子問(wèn)題，每個(gè)子問(wèn)題又可繼續(xù)分解。重復(fù)此過(guò)程，直到不需要或者不能再分解為止。如此形成“與”樹(shù)。等價(jià)變換 利用同構(gòu)或同態(tài)的等價(jià)變換，把原問(wèn)題變換為若干個(gè)較為容易求解的新問(wèn)題。如此形成“或”樹(shù)。8與或樹(shù)9與或樹(shù)的基本概念本原問(wèn)題不能再分解或變換，而且直接可解的子問(wèn)題。端節(jié)點(diǎn)與終止節(jié)點(diǎn)在與/或樹(shù)中，沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)統(tǒng)稱為端節(jié)點(diǎn)；本原問(wèn)題所對(duì)應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)。可解節(jié)點(diǎn)在與/或樹(shù)中，滿足下列條件之一者，稱為可解節(jié)點(diǎn)：它是一個(gè)終止節(jié)點(diǎn)；它是一個(gè)“或”節(jié)點(diǎn)，且其子節(jié)點(diǎn)中至少有一個(gè)是可解節(jié)點(diǎn)；它是一個(gè)“與”節(jié)點(diǎn)，且其子節(jié)點(diǎn)全部是可解節(jié)點(diǎn)。不可解節(jié)點(diǎn)關(guān)于可解節(jié)點(diǎn)的三個(gè)條件全部不滿足的節(jié)點(diǎn)10解樹(shù) 由可解節(jié)點(diǎn)所構(gòu)成，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)為可解節(jié)點(diǎn)的子樹(shù)稱為解樹(shù)。11三階梵塔問(wèn)題的與或樹(shù)125.2狀態(tài)空間搜索13盲目搜索的特點(diǎn)：搜索按規(guī)定的路線進(jìn)行，不使用與問(wèn)題有關(guān)的啟發(fā)性信息；適用于其狀態(tài)空間圖是樹(shù)狀結(jié)構(gòu)的一類問(wèn)題。啟發(fā)式搜索要使用與問(wèn)題有關(guān)的啟發(fā)性信息，并以這些啟發(fā)性信息指導(dǎo)搜索過(guò)程，可以高效地求解結(jié)構(gòu)復(fù)雜的問(wèn)題。搜索的原則廣度優(yōu)先搜索按照“先擴(kuò)展出的節(jié)點(diǎn)先被考察”的原則進(jìn)行搜索；深度優(yōu)先搜索按照“后擴(kuò)展出的節(jié)點(diǎn)先被考察”的原則進(jìn)行搜索；有界深度優(yōu)先搜索的原則與深度優(yōu)先搜索相同，但是它規(guī)定了深度限界，使搜索不得無(wú)限制地向縱深方向發(fā)展；代價(jià)樹(shù)的廣度優(yōu)先搜索按照“哪個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的代價(jià)小就先考察哪個(gè)節(jié)點(diǎn)”的原則進(jìn)行搜索；代價(jià)樹(shù)的深度優(yōu)先搜索按照“當(dāng)前節(jié)點(diǎn)的哪個(gè)子節(jié)點(diǎn)到其父節(jié)點(diǎn)的代價(jià)小就先考察哪個(gè)子節(jié)點(diǎn)”的原則進(jìn)行搜索；局部擇優(yōu)搜索按照“當(dāng)前節(jié)點(diǎn)的哪個(gè)子節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)代價(jià)小就先考察哪個(gè)子節(jié)點(diǎn)”的原則進(jìn)行搜索；全局擇優(yōu)搜索按照“哪個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)代價(jià)小就先考察哪個(gè)節(jié)點(diǎn)”的原則進(jìn)行搜索；145.2.1狀態(tài)空間的一般搜索過(guò)程OPEN表和CLOSE表OPEN表用于存放剛生成的節(jié)點(diǎn)。對(duì)于不同的搜索策略，節(jié)點(diǎn)在OPEN表中的排列順序是不同的。CLOSE表用于存放將要擴(kuò)展或者已經(jīng)擴(kuò)展的節(jié)點(diǎn)。

OPEN表 CLOSE表15狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)搜索的一般過(guò)程把初始節(jié)點(diǎn)S0放入OPEN表，并建立目前只包含S0的圖，記為G；檢查OPEN表是否為空，若為空則問(wèn)題無(wú)解，退出；把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入CLOSE表，并計(jì)該節(jié)點(diǎn)為n；考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wè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表；對(duì)于那些先前已經(jīng)在G中出現(xiàn)過(guò)的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針；對(duì)于那些先前已在G中出現(xiàn)并且已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針；按某種搜索策略對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序；轉(zhuǎn)第2步。16一些說(shuō)明上述是一個(gè)通用過(guò)程，各種搜索策略的主要區(qū)別是對(duì)OPEN表中節(jié)點(diǎn)排序的準(zhǔn)則不同。一個(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)。一個(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à)小的相應(yīng)節(jié)點(diǎn)就作為父節(jié)點(diǎn)。在搜索過(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)，則搜索失敗。175.2.2廣度優(yōu)先搜索基本思想： 從初始節(jié)點(diǎn)S0開(kāi)始，逐層地對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點(diǎn)。在第n層的節(jié)點(diǎn)沒(méi)有全部擴(kuò)展并考察之前，不對(duì)第n＋1層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。OPEN表中節(jié)點(diǎn)總是按進(jìn)入的先后順序排列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。18廣度優(yōu)先搜索過(guò)程把初始節(jié)點(diǎn)S0放入OPEN表。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表。考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wè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步。19重排九宮的廣度優(yōu)先搜索20廣度優(yōu)先搜索的特點(diǎn)優(yōu)點(diǎn)： 只要問(wè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)，搜索效率低。215.2.3深度優(yōu)先搜索基本思想： 從初始節(jié)點(diǎn)S0開(kāi)始，在其子節(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)達(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表的首部。22深度優(yōu)先搜索過(guò)程把初始節(jié)點(diǎn)S0放入OPEN表。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wè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步。23重排九宮的深度優(yōu)先搜索24深度優(yōu)先搜索的特點(diǎn)在深度優(yōu)先搜索中，搜索一旦進(jìn)入某個(gè)分支，就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上，則可較快地得到解。但是，如果目標(biāo)節(jié)點(diǎn)不在此分支上，而該分支又是一個(gè)無(wú)窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的，即使問(wèn)題有解，它也不一定能求得解。用深度優(yōu)先求得的解，不一定是路徑最短的解。255.2.4有界深度優(yōu)先搜索基本思想：對(duì)深度優(yōu)先搜索引入搜索深度的界限（設(shè)為dm），當(dāng)搜索深度達(dá)到了深度界限，而尚未出現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，就換一個(gè)分支進(jìn)行搜索。搜索過(guò)程：把初始節(jié)點(diǎn)S0放入OPEN表中，置S0的深度d(S0)=0。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，退出。若節(jié)點(diǎn)n的深度d(節(jié)點(diǎn)n)=dm，則轉(zhuǎn)第2步。若節(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步。26如果問(wèn)題有解，且其路徑長(zhǎng)度≤dm，則上述搜索過(guò)程一定能求得解。但是，若解的路徑長(zhǎng)度>dm,則上述搜索過(guò)程就得不到解。這說(shuō)明在有界深度優(yōu)先搜索中，深度界限的選擇是很重要的。要恰當(dāng)?shù)亟o出dm的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。27有界深度優(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，只要問(wèn)題有解，就一定可以找到它。但此時(shí)找到的解不一定是最優(yōu)解。為了找到最優(yōu)解，可增設(shè)一個(gè)表R，每找到遠(yuǎn)程目標(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)解。28重排九宮的有界深度優(yōu)先搜索設(shè)深度界限dm＝4295.2.5啟發(fā)式搜索盲目搜索具有較大的盲目性，產(chǎn)生的無(wú)用節(jié)點(diǎn)較多，搜索空間較大，效率不高。啟發(fā)式搜索要用到問(wèn)題自身的某些特性信息，以指導(dǎo)搜索朝著最有希望的方向前進(jìn)。由于這種搜索針對(duì)性較強(qiáng)，因而原則上只需要搜索問(wèn)題的部分狀態(tài)空間，效率較高。30啟發(fā)性信息與估價(jià)函數(shù)可用于指導(dǎo)搜索過(guò)程，且與具體問(wèn)題求解有關(guān)的控制性信息稱為啟發(fā)性信息。用于估價(jià)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)。其一般形式為：f(x)=g(x)+h(x)其中g(shù)(x)為從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x已經(jīng)實(shí)際付出的代價(jià)；h(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價(jià)，它體現(xiàn)了問(wèn)題的啟發(fā)性信息，其形式要根據(jù)問(wèn)題的特性確定。例如它可以是節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的距離，或者節(jié)點(diǎn)x處于最優(yōu)路徑上的概率等等。h(x)稱為啟發(fā)函數(shù)。g(x)指出了搜索的橫向趨勢(shì)。它有利于搜索的完備性，但影響搜索的效率。如果我們只關(guān)心到達(dá)目標(biāo)節(jié)點(diǎn)的路徑，并且希望有較高的搜索效率，則g(x)可以忽略，但此時(shí)會(huì)影響搜索的完備性。31估價(jià)函數(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ì)估價(jià)函數(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)中的比重。32BBBWWWE局部擇優(yōu)搜索基本思想： 當(dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展以后，按f(x)對(duì)每一個(gè)子節(jié)點(diǎn)計(jì)算估價(jià)值，并選擇最小者作為下一個(gè)要考察的節(jié)點(diǎn)。搜索過(guò)程：把初始節(jié)點(diǎn)S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wè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步。深度優(yōu)先搜索、代價(jià)樹(shù)的深度優(yōu)先搜索以及局部擇優(yōu)搜索都是以子節(jié)點(diǎn)作為考察范圍的。但是前二者可以看作局部擇優(yōu)搜索的特例。33代價(jià)樹(shù)的深度優(yōu)先搜索基本思想： 在代價(jià)樹(shù)的廣度優(yōu)先搜索中，每次都是從OPEN表的全體節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)送入CLOSE表進(jìn)行考察。而代價(jià)樹(shù)的深度優(yōu)先搜索是從剛擴(kuò)展出的子節(jié)點(diǎn)中選一個(gè)代價(jià)最小的節(jié)點(diǎn)送入CLOSE表進(jìn)行考察。搜索過(guò)程：把初始節(jié)點(diǎn)S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表。考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wè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à)樹(shù)的深度有限搜索是不完備的。34全局擇優(yōu)搜索35基本思想： 每當(dāng)要選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察時(shí)，局部擇優(yōu)搜索只是從剛生成的子節(jié)點(diǎn)中進(jìn)行選擇，選擇的范圍比較狹窄。全局擇優(yōu)搜索每次總是從OPEN表的全體節(jié)點(diǎn)中選擇一個(gè)估價(jià)值最小的節(jié)點(diǎn)。搜索過(guò)程：把初始節(jié)點(diǎn)S0放入OPEN表，計(jì)算f(S0)。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表。考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wè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步。廣度優(yōu)先搜索、代價(jià)樹(shù)的廣度優(yōu)先搜索以及全局擇優(yōu)搜索都是以當(dāng)前所有節(jié)點(diǎn)作為考察范圍的。但是前二者可以看作全局擇優(yōu)搜索的特例。重排九宮問(wèn)題的全局擇優(yōu)搜索樹(shù)設(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ù)。36代價(jià)樹(shù)的廣度優(yōu)先搜索邊上標(biāo)有代價(jià)(或費(fèi)用)的樹(shù)稱為代價(jià)樹(shù)。用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)基本思想： 每次從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é)點(diǎn)在代價(jià)樹(shù)中處于什么位置。如果問(wèn)題有解，代價(jià)樹(shù)的廣度優(yōu)先搜索一定可以求得解，并且求出的是最優(yōu)解。37代價(jià)樹(shù)廣度優(yōu)先搜索過(guò)程把初始節(jié)點(diǎn)S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wè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)的指針。計(jì)算各子節(jié)點(diǎn)的代價(jià)，并按各節(jié)點(diǎn)的代價(jià)對(duì)OPEN表中的全部節(jié)點(diǎn)進(jìn)行排序(按從小到大的順序)，然后轉(zhuǎn)第2步。38代價(jià)樹(shù)廣度優(yōu)先搜索示例395.2.6A*算法如果使一般搜索過(guò)程滿足如下限制，則它就稱為A*算法：1、把OPEN表中的節(jié)點(diǎn)按估價(jià)函數(shù)f(x)=g(x)+h(x)

的值從小至大進(jìn)行排序（一般搜索過(guò)程的第7步）。2、g(x)是對(duì)g*(x)的估計(jì)，g(x)>0。3、h(x)是h*(x)的下界，即對(duì)所有的x均有：h(x)≤h*(x)其中，g*(x)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的最小代價(jià)；h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià)，若有多個(gè)目標(biāo)節(jié)點(diǎn)，則為其中最小的一個(gè)。40在A*算法中，g(x)實(shí)際上就是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的路徑代價(jià)，恒有g(shù)(x)≥g*(x)。而且在算法執(zhí)行過(guò)程中隨著更多搜索信息的獲得，g(x)的值呈下降的趨勢(shì)。 例如：H(x)的確定依賴于具體問(wèn)題領(lǐng)域的啟發(fā)性信息，其中h(x)≤h*(x)的限制十分重要，它保證A*算法能找到最優(yōu)解。41A*算法的性質(zhì)可納性 對(duì)于可解狀態(tài)空間圖(即從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在)來(lái)說(shuō)，如果一個(gè)搜索算法能在有限步那終止，并且能找到最優(yōu)解，則稱該搜索算法是可納的。A*算法是可納的。A*算法的最優(yōu)性

A*算法的搜索效率在很大程度上取決于h(x)，在滿足h(x)≤h*(x)的前提下，h(x)的值越大越好。h(x)的值越大，表明它攜帶的啟發(fā)性信息越多，搜索時(shí)擴(kuò)展的節(jié)點(diǎn)數(shù)越少，搜索的效率越高。h(x)的單調(diào)性限制 在A*算法中，每當(dāng)要擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)都要先檢查其子節(jié)點(diǎn)是否已在OPEN表或CLOSE表中，有時(shí)還要調(diào)整指向父節(jié)點(diǎn)的指針，這就增加了搜索的代價(jià)。如果對(duì)啟發(fā)函數(shù)h(x)加上單調(diào)性限制，就可減少檢查及調(diào)整的工作量，從而減少搜索代價(jià)。42h(x)的單調(diào)性所謂單調(diào)性限制是指h(x)滿足如下兩個(gè)條件：1、h(Sg)=0;2、設(shè)xj是節(jié)點(diǎn)xi的任意子節(jié)點(diǎn)，則有h(xi)-h(xj)≤c(xi,xj)，即h(xi)≤h(xj)+c(xi,xj)其中，Sg是目標(biāo)節(jié)點(diǎn)；c(xi,xj)是