人工智能第五章狀態(tài)空間搜索策略山

1、第五章狀態(tài)空間搜索策略搜索是人工智能的一個(gè)基本問題，是推理不可分割的一部分。搜索是求解問題的一種方法，是根據(jù)問題的實(shí)際情況，按照一定的策略或規(guī)則，從知識(shí)庫中尋找可利用的知識(shí)，從而構(gòu)造出一條使問題獲得解決的推理路線的過程。搜索包含兩層含義：一層含義是要找到從初始事實(shí)到問題最終答案的一條推理路線；另一層含義是找到的這條路線是時(shí)間和空間復(fù)雜度最小的求解路線。搜索可分為盲目搜索和啟發(fā)式搜索兩種。11盲目搜索策略1狀態(tài)空間圖的搜索策略為了利用搜索的方法求解問題，首先必須將被求解的問題用某種形式表示出來。一般情況下，不同的知識(shí)表示對(duì)應(yīng)著不同的求解方法。狀態(tài)空間表示法是一種用“狀態(tài)”和“算符”表示問題的方法

2、。狀態(tài)空間可由一個(gè)三元組表示（S，F(xiàn)，0S）。g利用搜索方法求解問題的基本思想是：首先將問題的初始狀態(tài)（即狀態(tài)空間圖中的初始節(jié)點(diǎn)）當(dāng)作當(dāng)前狀態(tài)，選擇一適當(dāng)?shù)乃惴饔糜诋?dāng)前狀態(tài)，生成一組后繼狀態(tài)（或稱后繼節(jié)點(diǎn)），然后檢查這組后繼狀態(tài)中有沒有目標(biāo)狀態(tài)。如果有，則說明搜索成功，從初始狀態(tài)到目標(biāo)狀態(tài)的一系列算符即是問題的解；若沒有，則按照某種控制策略從已生成的狀態(tài)中再選一個(gè)狀態(tài)作為當(dāng)前狀態(tài)，重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)或不再有可供操作的狀態(tài)及算符時(shí)為止。算法51狀態(tài)空間圖的一般搜索算法建立一個(gè)只含有初始節(jié)點(diǎn)S的搜索圖G,把S放入OPEN表中。00表，且置為空表。CLOSED）建立判斷OPEN表是否為

3、空表，若為空，則問題無解，退出。選擇OPEN表中的第一個(gè)節(jié)點(diǎn)，把它從OPENS移出，并放入CLOSED!中，將此節(jié)點(diǎn)記為節(jié)點(diǎn)n。考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，若是，則問題有解，并成功退出。問題的解即可從圖G中沿著指針從n到S的這條路徑得到。擴(kuò)展節(jié)點(diǎn)n生成一組不是n的祖先的后繼節(jié)點(diǎn)，并將它們記作集合M，將M中的這些節(jié)點(diǎn)作為n的后繼節(jié)點(diǎn)加入圖G中。對(duì)那些未曾在G中出現(xiàn)過的（即未曾在OPEN表上或CLOSED1上出現(xiàn)過的）M中的節(jié)點(diǎn)，設(shè)置一個(gè)指向父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把這些節(jié)點(diǎn)加入OPEN表中；對(duì)于已在G中出現(xiàn)過的M中的那些節(jié)點(diǎn)，確定是否需要修改指向父節(jié)點(diǎn)（n節(jié)點(diǎn)）的指針；對(duì)于那些先前已在G中出現(xiàn)

4、并且已在COLSEDI中的M中的節(jié)點(diǎn)，確定是否需要修改通向它們后繼節(jié)點(diǎn)的指針。按某一任意方式或按某種策略重排OPEN表中節(jié)點(diǎn)的順序。轉(zhuǎn)第步。2 寬度優(yōu)先搜索策略寬度優(yōu)先搜索是一種盲目搜索策略。其基本思想是，從初始節(jié)點(diǎn)開始，逐層對(duì)節(jié)點(diǎn)進(jìn)行依次擴(kuò)展，并考察它是否為目標(biāo)節(jié)點(diǎn)，在對(duì)下層節(jié)點(diǎn)進(jìn)行擴(kuò)展（或搜索）之前，必須完成對(duì)當(dāng)前層的所有節(jié)點(diǎn)的擴(kuò)展（或搜索）。在搜索過程中，未擴(kuò)展節(jié)點(diǎn)表OPEN中的節(jié)點(diǎn)排序準(zhǔn)則是：先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面（即將擴(kuò)展得到的后繼節(jié)點(diǎn)放于OPEN表的末端）。寬度優(yōu)先搜索的盲目性較大，搜索效率低，這是它的缺點(diǎn)。但寬度優(yōu)先搜索策略是完備的，即只要問題有解，用寬度優(yōu)先

5、搜索總可以找到它的解。3 xx優(yōu)先搜索首先擴(kuò)展最新產(chǎn)生的其基本思想是：深度優(yōu)先搜索也是一種盲目搜索策略，（即最深的）節(jié)點(diǎn)，即從初始節(jié)點(diǎn)S開始，在其后繼節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)，對(duì)其進(jìn)0行考察，若它不是目標(biāo)節(jié)點(diǎn)，則對(duì)該節(jié)點(diǎn)進(jìn)行擴(kuò)展，并再從它的后繼節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察。依此類推，一直搜索下去，當(dāng)?shù)竭_(dá)某個(gè)既非目標(biāo)節(jié)點(diǎn)又無法繼續(xù)擴(kuò)展的節(jié)點(diǎn)時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察。深度優(yōu)先搜索與寬度優(yōu)先搜索的區(qū)別就在于：在對(duì)節(jié)點(diǎn)n進(jìn)行擴(kuò)展時(shí)，其后繼節(jié)點(diǎn)在OPEN表中的存放位置。寬度優(yōu)先搜索是將后繼節(jié)點(diǎn)放入OPEN表的末端，而深度優(yōu)先搜索則是將后繼節(jié)點(diǎn)放入OPEN表的前端。4 有界xx優(yōu)先搜索對(duì)于許多問題，其狀態(tài)空間

6、搜索樹的深度可能為無限深。為了避免搜索過程沿著無窮的路徑搜索下去，往往對(duì)一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度進(jìn)行限制。任何節(jié)點(diǎn)如果達(dá)到了深度界限，就把它作為沒有后繼節(jié)點(diǎn)進(jìn)行處理，即對(duì)另一個(gè)分支進(jìn)行搜索。在有界深度優(yōu)先搜索算法中，深度界限的選擇很重要。選擇過大，可能會(huì)影響搜索的效率；選擇的過小，有可能求不到解。有界深度優(yōu)先搜索策略是不完備的。5 代價(jià)樹的寬度優(yōu)先搜索前面的搜索算法沒有考慮搜索的代價(jià)問題，即假設(shè)狀態(tài)空間圖中各節(jié)點(diǎn)之間的有向邊的代價(jià)是相同的。在實(shí)際問題求解中，往往是將一個(gè)狀態(tài)變換成另一個(gè)狀態(tài)時(shí)所付出的操作代價(jià)（或費(fèi)用）是不一樣的，即狀態(tài)空間圖中各有向邊的代價(jià)是不一樣的。把有向邊上標(biāo)有代價(jià)的搜索樹稱

7、為代價(jià)搜索樹，簡(jiǎn)稱代價(jià)樹。代價(jià)樹寬度優(yōu)先搜索的基本思想是：每次從OPEN表中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)，移入COLSED!。因此，每當(dāng)對(duì)一節(jié)點(diǎn)擴(kuò)展之后，就要計(jì)算它的所有后繼節(jié)點(diǎn)的代價(jià)，并將它們與OPEN表中已有的待擴(kuò)展的節(jié)點(diǎn)按代價(jià)的大小從小到大依次排序。而從OPEN®選擇被擴(kuò)展節(jié)點(diǎn)時(shí)即選擇排在最前面的節(jié)點(diǎn)（代價(jià)最小）。代價(jià)樹的寬度優(yōu)先搜索算法是一個(gè)完備算法。6 代價(jià)樹的xx優(yōu)先搜索代價(jià)樹的深度優(yōu)先搜索和寬度優(yōu)先搜索的區(qū)別是：寬度優(yōu)先搜索法每次從OPEN®中的全體節(jié)點(diǎn)中選擇彳t價(jià)最小的節(jié)點(diǎn)移入CLOSED1,并對(duì)這一節(jié)點(diǎn)進(jìn)行擴(kuò)展或判斷（是否為目標(biāo)節(jié)點(diǎn)），而深度優(yōu)先搜索法則是從剛剛

8、擴(kuò)展的節(jié)點(diǎn)之后3/ 6繼節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)移入CLOSED1,并進(jìn)行擴(kuò)展或判斷。代價(jià)樹的深度優(yōu)先搜索算法是不完備的算法，所求得的解不一定是最優(yōu)解，甚至有可能進(jìn)入無窮分支路徑而搜索不到問題的解。12啟發(fā)式搜索策略利用問題自身特性信息，以提高搜索效率的搜索策略，稱為啟發(fā)式搜索或有信息搜索。1啟發(fā)信息與估價(jià)函數(shù)在搜索過程中，如果在確定要被考察的節(jié)點(diǎn)時(shí)，能夠利用被求解問題的有關(guān)特性信息，估計(jì)出各節(jié)點(diǎn)的重要性，就可選擇重要性較高的節(jié)點(diǎn)進(jìn)行擴(kuò)展，以便提高求解的效率。通?？梢詷?gòu)造一個(gè)函數(shù)來表示節(jié)點(diǎn)的“希望”程度，稱這種函數(shù)為估價(jià)函數(shù)。估價(jià)函數(shù)f(x)可定義為從初始節(jié)點(diǎn)經(jīng)過節(jié)點(diǎn)z到達(dá)目標(biāo)節(jié)點(diǎn)的最小代

9、價(jià)路徑的代價(jià)估計(jì)值。它的一般形式為f(x)=g(x)+h(x)其中g(shù)(x)為初始節(jié)點(diǎn)S到節(jié)點(diǎn)z已實(shí)際付出的代價(jià)；h(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)0點(diǎn)S的最優(yōu)路徑的估計(jì)代價(jià)，搜索的啟發(fā)信息主要由h(x)來體現(xiàn)，故把h(x)稱g作啟發(fā)函數(shù)。估價(jià)函數(shù)是針對(duì)具體問題構(gòu)造的，是與問題特性密切相關(guān)的。不同的問題，其估價(jià)函數(shù)可能不同。在構(gòu)造估價(jià)函數(shù)時(shí)，依賴于問題特性的啟發(fā)函數(shù)h(x)的構(gòu)造尤為重要。.在構(gòu)造啟發(fā)函數(shù)時(shí)，還要考慮到兩個(gè)方面因素的影響：一個(gè)是搜索工作量，一個(gè)是搜索代價(jià)。有些啟發(fā)信息雖然能夠大大減少搜索的工作量，但卻不能保證求得最小代價(jià)的路徑。而我們感興趣的是，使問題求解的路徑代價(jià)與為求此路徑所花費(fèi)的搜

10、索代價(jià)的綜合指標(biāo)為最小。最佳優(yōu)先搜索又稱為有序搜索或擇優(yōu)搜索，它總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)，而這種最有希望的節(jié)點(diǎn)是按估價(jià)函數(shù)f(x)的值來挑選的，一般估價(jià)函數(shù)的值越小，它的希望程度越大。最佳優(yōu)先搜索又分局部最佳優(yōu)先搜索和全局最佳優(yōu)先搜索。(1)局部最佳優(yōu)先搜索局部最佳優(yōu)先搜索的思想類似于深度優(yōu)先搜索法，但由于使用了與問題特性相關(guān)的估價(jià)函數(shù)來確定下一個(gè)待擴(kuò)展的節(jié)點(diǎn)，所以它是一種啟發(fā)式搜索方法。其思想是：當(dāng)對(duì)某一個(gè)節(jié)點(diǎn)擴(kuò)展之后，對(duì)它的每一個(gè)后繼節(jié)點(diǎn)計(jì)算估價(jià)函數(shù)f(x)的值，并在這些后繼節(jié)點(diǎn)的范圍內(nèi)，選擇一個(gè)f(x)的值最小的節(jié)點(diǎn)，作為下一個(gè)要考察的節(jié)點(diǎn)。由于它每次只在后繼節(jié)點(diǎn)的范

11、圍內(nèi)選擇下一個(gè)要考察的節(jié)點(diǎn)，范圍比較小，所以稱為局部最佳優(yōu)先搜索或局部擇優(yōu)搜索。局部最佳優(yōu)先搜索與深度優(yōu)先搜索及代價(jià)樹的深度優(yōu)先搜索的區(qū)別，就在于在選擇下一個(gè)節(jié)點(diǎn)時(shí)所用的標(biāo)準(zhǔn)不一樣。局部最佳優(yōu)先搜索是以估價(jià)函數(shù)值作為標(biāo)準(zhǔn)；深度優(yōu)先搜索則是以后繼節(jié)點(diǎn)的深度作為選擇標(biāo)準(zhǔn)，后生成的節(jié)點(diǎn)先考察；而代價(jià)樹深度優(yōu)先則是以各后繼節(jié)點(diǎn)到其前驅(qū)節(jié)點(diǎn)之間的代價(jià)作為選擇標(biāo)準(zhǔn)。如果把層深函數(shù)d(x)就當(dāng)作估價(jià)函數(shù)f(x),或把代價(jià)函數(shù)g(x)當(dāng)作估價(jià)函數(shù)f(x),那么就可以把深度優(yōu)先搜索和代價(jià)樹深度優(yōu)先搜索看作局部最佳優(yōu)先搜索的兩個(gè)特例。(2)全局最佳優(yōu)先搜索它的思想類似于寬度優(yōu)先全局最佳優(yōu)先搜索也是一個(gè)有信息的啟發(fā)

12、式搜索，搜索，所不同的是，在確定下一個(gè)擴(kuò)展節(jié)點(diǎn)時(shí)，以與問題特性密切相關(guān)的估價(jià)函數(shù)f(x)作為標(biāo)準(zhǔn)，不過這種方法是在OPEN表中的全部節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值f(x)最小的節(jié)點(diǎn)，作為下一個(gè)被考察的節(jié)點(diǎn)。正因?yàn)檫x擇的范圍是OPEN®中的全部節(jié)點(diǎn)，所以它稱為全局最佳優(yōu)先搜索或全局擇優(yōu)搜索。全局最佳優(yōu)先搜索實(shí)際是對(duì)寬度優(yōu)先搜索和代價(jià)樹的寬度優(yōu)先搜索的擴(kuò)展，而寬度優(yōu)先搜索和代價(jià)樹的寬度優(yōu)先搜索則是它的兩個(gè)特例(這時(shí)可分別令f(x)等于d(x)或g(x),d(x)表示節(jié)點(diǎn)x的深度，而g(x)則表示初始節(jié)點(diǎn)S到節(jié)點(diǎn)x在啟發(fā)式搜索中，估價(jià)函數(shù)的定義是非常重要的，如果定義得不好，則上述的搜索算法不一定能找到問題的解，即便找到解，也不一定是最優(yōu)解。所以，有必要討論如何對(duì)估價(jià)函數(shù)進(jìn)行限制或定義。A*啟發(fā)式搜索算法就使用了一種特殊定義的估價(jià)函數(shù)。A*算法具有下列一些性質(zhì)：可采納性。所謂可采納性是指對(duì)于可求解的狀態(tài)空間圖(即從狀態(tài)空間圖的初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在)來說，如果一個(gè)搜索算法能在有限步內(nèi)終止，并且能找到最優(yōu)解，則稱該算法是可采納的。單調(diào)性。所謂單調(diào)性是指在A*算法中，如果對(duì)其估價(jià)函數(shù)中的h(x)部分即啟發(fā)性函數(shù)，加以適當(dāng)?shù)膯握{(diào)性限制條件，就可以使它對(duì)所擴(kuò)展的