《人工智能》課件

《人工智能》PPT課件本課件僅供大家學(xué)習(xí)學(xué)習(xí)學(xué)習(xí)完畢請(qǐng)自覺刪除謝謝本課件僅供大家學(xué)習(xí)學(xué)習(xí)學(xué)習(xí)完畢請(qǐng)自覺刪除謝謝?另外，可能存在多條線路都可實(shí)現(xiàn)對(duì)問題的求解，這就又出現(xiàn)按哪一條線路進(jìn)行求解以獲得較高的運(yùn)行效率的問題。

像這樣根據(jù)問題的實(shí)際情況不斷尋找可利用的知識(shí)，從而構(gòu)造一條代價(jià)較少的推理路線，使問題得到圓滿解決的過程稱為搜索。2.搜索分類

搜索分為盲目搜索和啟發(fā)式搜索。

盲目搜索——按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的中間信息不用來改進(jìn)控制策略。這種搜索具有盲目性，效率不高，不便于復(fù)雜問題的求解。

啟發(fā)式搜索——在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程并找到最優(yōu)解。5.2求解問題的表示方法

用搜索策略求解問題，首先要解決的問題也是：用什么樣的形式把問題表示出來.

一般來說，有兩種方法：

狀態(tài)空間表示法；與/或樹表示法；

1.狀態(tài)空間表示法

狀態(tài)空間表示法是用來表示問題及其搜索過程的一種方法，它是人工智能中最基本的形式化方法。狀態(tài)空間表示法是用“狀態(tài)”和“算符”來表示問題的一種方法。其中，“狀態(tài)”——用以描述問題求解過程中不同時(shí)刻的狀況；“算符”——表示對(duì)狀態(tài)的操作，算符的每一次使用就使問題由一種狀態(tài)變換為另一種狀態(tài);解——當(dāng)?shù)竭_(dá)目標(biāo)狀態(tài)時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所用算符的序列就是問題的一個(gè)解。Ⅰ.狀態(tài)

狀態(tài)是描述問題求解過程中任一時(shí)刻狀況的數(shù)據(jù)結(jié)構(gòu)，一般用一組變量的有序組合表示：

SK＝(SK0,SK1,…)當(dāng)給每一個(gè)分量以確定的值時(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)空間，—般用—個(gè)三元組表示：(S，F(xiàn)，G)其中,S是問題的所有初始狀態(tài)構(gòu)成的集合；F是算符的集合；G是目標(biāo)狀態(tài)的集合。狀態(tài)空間的圖示形式稱為狀態(tài)空間圖。其中，節(jié)點(diǎn)表示狀態(tài)；有向邊(弧)表示算符。例1：錢幣翻轉(zhuǎn)問題，如圖所示。設(shè)有三個(gè)錢幣，起初是狀態(tài)為（反正反），允許每次翻轉(zhuǎn)一個(gè)錢幣（只反一個(gè)，也必反一個(gè)），連反三次，問是否可達(dá)到目標(biāo)狀態(tài)？（正正正）或（反反反）？正反正正正反反反反設(shè)用Sk=(s1,s2,s3)表示問題的狀態(tài)，s=0表示錢幣正面，s=1表示錢幣反面。則錢幣可能出現(xiàn)的狀態(tài)有八種：

S0=(0,0,0),S1=(0,0,1),S2=(0,1,0),S3=(0,1,1)

S4=(1,0,0),S5=(1,0,1),S6=(1,1,0),S7=(1,1,1)

問題的初始狀態(tài)集合：S={S5}

目標(biāo)狀態(tài)集合：G={S0,S7}

算符：f1——把s1翻一面；f2——把s2翻一面；f3——把s3翻一面；上述問題的狀態(tài)空間“三元組”為：（{S5},{f1,f2,f3},{s0,s7}）相應(yīng)的狀態(tài)空間圖：000100001101111011110010S0S4S1S5S7S3S6S2從圖中看出：從S5不可能經(jīng)三次翻轉(zhuǎn)到達(dá)S0,從S5

可經(jīng)三次翻轉(zhuǎn)到達(dá)S7,且有七種操作方式。f1f1f1f1f2f2f2f2f3f3f3f32.與/或樹表示法與/或樹是用于表示問題及其求解過程的又一種形式化方法，通常用于表示比較復(fù)雜問題的求解。對(duì)于一個(gè)復(fù)雜問題，直接求解往往比較困難。此時(shí)，可通過下述方法進(jìn)行簡(jiǎn)化：(1)分解：“與”樹

把一個(gè)復(fù)雜問題分解為若干個(gè)較為簡(jiǎn)單的子問題，然后對(duì)每個(gè)子問題分別進(jìn)行求解，最后把各子問題的解復(fù)合起來就得到了原問題的解。這是“與”的問題。PP1P2P3P1,

P2,P3為子節(jié)點(diǎn)，子問題對(duì)應(yīng)子節(jié)點(diǎn)。P為“與”節(jié)點(diǎn)，只有當(dāng)三個(gè)子問題都有解時(shí)，P才可解。

如圖所示，稱為“與”樹。(2)等價(jià)變換：“或”樹利用等價(jià)變換，把它變換為若干個(gè)較容易求解的新問題。若新問題中有一個(gè)可求解，則就得到了原問題的解。這是“或”的問題。

如圖所示，稱為“或”樹。PP1P2P3與/或樹：將上述兩種方法也可結(jié)合起來使用，此時(shí)的圖稱為“與/或樹”，其中既有“與”節(jié)點(diǎn)，也有“或”節(jié)點(diǎn)。在此統(tǒng)稱為子節(jié)點(diǎn)。P1P11P12P3P31P32P33PP2(3)幾個(gè)基本概念：

Ⅰ.本原問題

不能再分解或變換，而且直接可解的子問題稱為本原問題。

Ⅱ.端節(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)：?它是一個(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)稱為不可解節(jié)點(diǎn)。

Ⅴ.解樹

由可解節(jié)點(diǎn)所構(gòu)成，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)(它對(duì)應(yīng)于原始問題)為可解節(jié)點(diǎn)的子樹稱為解樹。在解樹中一定包含初始節(jié)點(diǎn)。

例如：t標(biāo)出的節(jié)點(diǎn)是終止節(jié)點(diǎn)，根據(jù)可解節(jié)點(diǎn)的定義，原始問題P是可解的。ttP例：三階漢諾塔問題。設(shè)有A，B，C三個(gè)金片以及三根鋼針，三個(gè)金片按自上而下從小到大的順序穿在1號(hào)鋼針上，要求把它們?nèi)恳频?號(hào)鋼針上，而且每次只能移動(dòng)一個(gè)金片，任何時(shí)刻都不能把大的金片壓在小的金片上面，如圖所示。首先進(jìn)行問題分析：

(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è)子問題。ABCABC

為了用與/或樹把問題的分解過程表示出來，先要定義問題的形式化表示方法。

設(shè)仍用狀態(tài)表示問題在任一時(shí)刻的狀況；

用三元組(i，j，k)表示狀態(tài)：i代表金片C所在的鋼針號(hào)；j代表金片B所在的鋼針號(hào);

k代表金片A所在的鋼針號(hào)。用“

”表示狀態(tài)的變換；這樣原始問題就可表示為：(1,1,1)

(3，3，3)用與/或樹把分解過程表示出來。(1,1,1)(3,3,3)(1,2,2)(3,2,2)(1,1,1)(1,2,2)(3,2,2)(3,3,3)(3,2,2)(3,2,1)(3,2,1)(3,3,1)(3,3,1)(3,3,3)(1,1,1)(1,1,3)(1,1,3)(1,2,3)(1,2,3)(1,2,2)若把這些本原問題的解按從左至右的順序排列，就得到了原始問題的解：(1,1,1)

(1,l,3)，(1,1,3)

(1,2,3)，(1,2,3)

(1,2,2)，(1,2,2)

(3,2,2)，(3,2,2)

(3,2,1)，(3,2,1)

(3,3,1)，(3,3,1)

(3,3,3)它指出了移動(dòng)金片的次序。此圖共有七個(gè)終止節(jié)點(diǎn)，對(duì)應(yīng)于七個(gè)本原問題，它們是通過“分解”得到的。5.3狀態(tài)空間搜索策略

1.概述

(1)顯式圖與隱式圖為了求解問題，需要把知識(shí)存儲(chǔ)在計(jì)算機(jī)的知識(shí)庫中，有下列兩種存儲(chǔ)方式：

顯式存儲(chǔ)：把與問題有關(guān)的全部狀態(tài)空間圖，即相應(yīng)的全部知識(shí)（事實(shí)性知識(shí)、過程性知識(shí)，控制性知識(shí)）都直接存入知識(shí)庫，稱為“顯式存儲(chǔ)”或“顯式圖”。

隱式存儲(chǔ)：只存儲(chǔ)與問題有關(guān)的部分知識(shí)，在求解過程中，又初始狀態(tài)出發(fā)，運(yùn)用相應(yīng)的知識(shí)，逐步生成所需的部分狀態(tài)空間圖，通過搜索推理，找到所求目標(biāo)。這樣只需在知識(shí)庫中存儲(chǔ)局部狀態(tài)空間圖，稱為“隱式圖”。通常，為了節(jié)約計(jì)算機(jī)的存儲(chǔ)容量，提高搜索推理效率，采用隱式存儲(chǔ)方法，進(jìn)行隱士圖搜索推理。(2)搜索方法Ⅰ.運(yùn)用事實(shí)性知識(shí)，給出問題的部分狀態(tài)描述，包括：初始狀態(tài)S0，目標(biāo)狀態(tài)Sg，和某些中間狀態(tài)Sh；Ⅱ.運(yùn)用過程性知識(shí)，給出由狀態(tài)空間圖“父節(jié)點(diǎn)”生成“子節(jié)點(diǎn)”的操作“算符”；Ⅲ.運(yùn)用控制性知識(shí)（在此為搜索策略），選取適當(dāng)?shù)墓?jié)點(diǎn)，控制繼續(xù)搜索的方向。(3)搜索過程Ⅰ.給出初始狀態(tài)（初始節(jié)點(diǎn)）；Ⅱ.選擇選擇適用的算符對(duì)其進(jìn)行操作，生成一組子狀態(tài)(或稱后繼狀態(tài)、后繼節(jié)點(diǎn)、子節(jié)點(diǎn))；Ⅲ.檢查目標(biāo)狀態(tài)是否在其中出現(xiàn)。若出現(xiàn)，則搜索成功，找到了問題的解；若不出現(xiàn)，則按某種搜索策略從已生成的狀態(tài)中再選一個(gè)狀態(tài)作為當(dāng)前狀態(tài)。重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)或者不再有可供操作的狀態(tài)及算符時(shí)為止。(4)搜索過程中要用到的兩個(gè)數(shù)據(jù)結(jié)構(gòu)

OPEN表：用于存放剛生成的節(jié)點(diǎn)。對(duì)于不同的搜索策略，節(jié)點(diǎn)在OPEN表中的排列順序是不同的。

CLOSED表：用于存放將要擴(kuò)展或者已擴(kuò)展的節(jié)點(diǎn)，所謂對(duì)節(jié)點(diǎn)進(jìn)行“擴(kuò)展”是指：用合適的算符對(duì)該節(jié)點(diǎn)進(jìn)行操作，生成一組子節(jié)點(diǎn)。狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)OPEN表編號(hào)狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)CLOSED表(5)狀態(tài)空間法搜索策略

?廣度優(yōu)先搜索?深度優(yōu)先搜索?有界深度優(yōu)先搜索?代價(jià)樹的廣度優(yōu)先搜索?代價(jià)樹的深度優(yōu)先搜索

（以上屬于盲目搜索策略）?局部擇優(yōu)搜索?全局擇優(yōu)搜索（以上搜索屬于啟發(fā)式搜索）2.廣度優(yōu)先搜索法（Breadth-FirstSearch)

(1)基本思想從初始節(jié)點(diǎn)開始，按照某種生成規(guī)則（算符）逐步生成下一級(jí)各子節(jié)點(diǎn)，順序（先生成的子節(jié)點(diǎn)優(yōu)先檢查，優(yōu)先擴(kuò)展）地檢查是否出現(xiàn)目標(biāo)節(jié)點(diǎn)，在該級(jí)全部節(jié)點(diǎn)中沿廣度進(jìn)行“橫向”掃描，即：沿“廣度”遍歷所有節(jié)點(diǎn)，故稱“廣度優(yōu)先搜索法”。

(2)廣度優(yōu)先搜索法搜索過程

Ⅰ.把初始節(jié)點(diǎn)S0放人OPEN表，若S0為目標(biāo)節(jié)點(diǎn)，則得到問題的解，退出；

Ⅱ.如果OPEN表為空，則問題無解，退出；Ⅲ.把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入CLOSED表；Ⅳ.考察節(jié)點(diǎn)n，若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第Ⅱ步；Ⅴ.擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入0PEN表的尾部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針；Ⅵ.如果n的任一個(gè)后繼節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則找到問題的解，成功退出，否則轉(zhuǎn)向第Ⅱ步。開始把S0送入OPEN表把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)從表中移出，放入CLOSED表

OPEN表為空？擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)放入OPEN表的尾部，并為每個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針。是否有任何后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？節(jié)點(diǎn)n可擴(kuò)展？失敗，退出成功，退出YNYNYNS0為目標(biāo)節(jié)點(diǎn)？成功，退出YN狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)OPEN表編號(hào)狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)CLOSED表S012S0126345S0126345789(a)(b)(c)(d)S0S01121200034203356789411112233445S010203141Sg(9)S0491例：重排九宮問題。在3X3的方格棋盤上放置分別標(biāo)有數(shù)字1，2，3，4，5，6，7，8的八張牌，初始狀態(tài)為50，目標(biāo)狀態(tài)為S，如下圖所示。

可使用的算符有：空格左移，空格上移，空格右移，空格下移即，它們只允許把位于空格左，上，右，下邊的牌移入空格。

要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。

應(yīng)用廣度優(yōu)先搜索，可得到如圖所示的搜索樹。2831476512384765由圖可以看出，解的路徑是:S0381626(Sg)小結(jié)：

缺點(diǎn)：

廣度優(yōu)先搜索的盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無用節(jié)點(diǎn)，搜索效率低，這是它的缺點(diǎn)。優(yōu)點(diǎn)：

只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解，這是它的優(yōu)點(diǎn)。3.深度優(yōu)先搜索

(1)基本思想從初始節(jié)點(diǎn)S0開始，按生成規(guī)則生成下一級(jí)各子節(jié)點(diǎn)，若目標(biāo)節(jié)點(diǎn)未出現(xiàn)，則按“最晚生成的子節(jié)點(diǎn)優(yōu)先擴(kuò)展”的原則，生成再下一級(jí)的子節(jié)點(diǎn)，如此下去，沿著最晚生成的子節(jié)點(diǎn)分支，逐級(jí)向“縱向”深入發(fā)展，故稱為“深度優(yōu)先搜索法”。

(2)深度優(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表的首部。

僅此一點(diǎn)不同，就使得搜索的路線完全不一樣。開始把S0送入OPEN表把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)從表中移出，放入CLOSED表

OPEN表為空？擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)放入OPEN表的首部，并為每個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針。是否有任何后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？節(jié)點(diǎn)n可擴(kuò)展？失敗，退出成功，退出YNYNYNS0為目標(biāo)節(jié)點(diǎn)？成功，退出YN狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)OPEN表編號(hào)狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)CLOSED表S012S01234(a)(b)(c)S0S012345S0123465S012346578(d)020222032424254646476861Sg(8)S02468(e)例：對(duì)上節(jié)所示的重排九宮問題進(jìn)行深度優(yōu)先按索，可得如下圖所示的搜索樹。這只是搜索樹的一部分，尚未到達(dá)目標(biāo)節(jié)點(diǎn)，仍可繼續(xù)往下搜索。小結(jié)：在深度優(yōu)先搜索中，搜索一旦進(jìn)入某個(gè)分支，就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上，則可較快地得到解。但是，如果目標(biāo)節(jié)點(diǎn)不在此分支上，而該分支又是一個(gè)無窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的，即使問題有解，它也不一定能求得解。另外，用深度優(yōu)先搜索求得的解，不一定是路徑最短的解，其道理是顯然的。4.有界深度優(yōu)先搜索

(1)基本思想

為了解決深度優(yōu)先搜索不完備的問題，避免搜索過程陷入無窮分支的死循環(huán)，對(duì)深度優(yōu)先搜索引入搜索深度的界限（設(shè)為dm），當(dāng)搜索深度達(dá)到了深度界限，而尚未出現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，就換一個(gè)分支進(jìn)行搜索。

(2)有界深度優(yōu)先搜索的搜索過程開始把S0送入OPEN表,置S0的深度d(S0)=0S0為目標(biāo)節(jié)點(diǎn)？成功,退出YN把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)從表中移出，放入CLOSED表

OPEN表為空？擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)放入OPEN表的首部,并為每個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針,置d(n’)=d(n)+1是否有任何后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？節(jié)點(diǎn)n可擴(kuò)展？失敗,退出成功,退出YNYNYNd(節(jié)點(diǎn)n)=dm？NY例：設(shè)深度界度dm＝4，用有界深度優(yōu)先搜索方法求解重排九官問題。搜索樹如圖所示。解的路徑是：S0

20

25

26

28(Sg)

(3)有界深度優(yōu)先搜索法的改進(jìn)上述方法存在兩個(gè)問題：

?深度界限的選擇很重要

dm

若太小，則達(dá)不到解的深度，得不到解；若太大，則搜索時(shí)將產(chǎn)生許多無用的子節(jié)點(diǎn)，既浪費(fèi)了計(jì)算機(jī)的存儲(chǔ)空間與時(shí)間，又降低了搜索效率。由于解的路徑長(zhǎng)度事先難以預(yù)料，所以要恰當(dāng)?shù)亟o出dm的值是比較困難的。

?即使能求出解，它也不一定是最優(yōu)解。

解決方法：

Ⅰ.dm隨搜索深度不斷加大

先任意給定一個(gè)較小的數(shù)作為dm，然后進(jìn)行上述的有界深度優(yōu)先搜索，當(dāng)搜索達(dá)到了指定的深度界限dm仍未發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)，并且CLOSED表中仍有待擴(kuò)展節(jié)點(diǎn)時(shí)．就將這些節(jié)點(diǎn)送回OPEN表，同時(shí)增大深度界限dm，繼續(xù)向下搜索。如此不斷地增大dm，只要問題有解，就一定可以找到它。

Ⅱ.增加一個(gè)R表

此時(shí)找到的解不一定是最優(yōu)解。為找到最優(yōu)解，可增設(shè)一個(gè)表(R)，每找到一個(gè)目標(biāo)節(jié)點(diǎn)Sg后，就把它放入到R的前面，并令dm等于該目標(biāo)節(jié)點(diǎn)所對(duì)應(yīng)的路徑長(zhǎng)度，然后繼續(xù)搜索。由于后求得的解的路徑長(zhǎng)度不會(huì)超過先求得的解的路徑長(zhǎng)度，所以最后求得的解一定是最優(yōu)解。開始把S0送入OPEN表,置d(S0)=0,dm=任一初值,R表為空S0為目標(biāo)節(jié)點(diǎn)？成功,退出YN把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)從表中移出，放入CLOSED表

OPEN表為空？擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)放入OPEN表的首部,并為每個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針,令d(n’)=d(n)+1是否有任何后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？節(jié)點(diǎn)n可擴(kuò)展？失敗,退出YNYNYNd(節(jié)點(diǎn)n)>dm？NY記節(jié)點(diǎn)n為待擴(kuò)展節(jié)點(diǎn)把Sg放到R表的前端，且令：dm=d(Sg)把CLOSED表中的待擴(kuò)展節(jié)點(diǎn)取出放回到OPEN表中，取消標(biāo)記。若R表為空，則令dm=dm+?dCLOSED表中有待擴(kuò)展節(jié)點(diǎn)？成功，R表中最前面的節(jié)點(diǎn)為Sg*R表空？退出NYYN

求最優(yōu)解的有界深度優(yōu)先搜索過程如圖所示。其中Sg是目標(biāo)節(jié)點(diǎn)．Sg*是距離S0最近的目標(biāo)節(jié)點(diǎn)。5.代價(jià)樹的廣度優(yōu)先搜索(1)基本思想

代價(jià)：從一個(gè)節(jié)點(diǎn)，經(jīng)過一條支路，轉(zhuǎn)移到另一個(gè)節(jié)點(diǎn)，所需支付的代價(jià)（時(shí)間、費(fèi)用等）。

代價(jià)樹：邊上標(biāo)有代價(jià)的樹稱為代價(jià)樹。

在代價(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)

代價(jià)樹廣皮優(yōu)先搜索的基本思想是：

每次從OPEN表中選擇節(jié)點(diǎn)往CLOSED表傳送時(shí)，總是選擇其代價(jià)為最小的節(jié)點(diǎn)。也就是說，OPEN表中的節(jié)點(diǎn)在任一時(shí)刻都是按其代價(jià)從小至大排序的，代價(jià)小的節(jié)點(diǎn)排在前面，代價(jià)大的節(jié)點(diǎn)排在后面，而不管節(jié)點(diǎn)在代價(jià)樹中處于什么位置。

(2)代價(jià)樹的廣度優(yōu)先搜索過程開始把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)從表中移出，放入CLOSED表

OPEN表為空？擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)放入OPEN表，并為每個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針。計(jì)算各子節(jié)點(diǎn)的代價(jià)，把OPEN表的全部節(jié)點(diǎn)按代價(jià)排序。節(jié)點(diǎn)n為目標(biāo)節(jié)點(diǎn)？節(jié)點(diǎn)n可擴(kuò)展？失敗，退出成功，退出YNYYN把S0送入OPEN表N例：右圖是五城市間的交通路線圖，A城市是出發(fā)地，

E城市是目的地，兩城市間的交通費(fèi)用(代價(jià))如圖中數(shù)字所示。求從A到E的最小費(fèi)用交通路線。先將交通圖轉(zhuǎn)換為代價(jià)樹，轉(zhuǎn)換的方法是：?從起始節(jié)點(diǎn)A開始，把與它直接相鄰的節(jié)點(diǎn)作為它的子節(jié)點(diǎn)。對(duì)其它節(jié)點(diǎn)也做相同的處理。?若一個(gè)節(jié)點(diǎn)已作為某節(jié)點(diǎn)的直系先輩節(jié)點(diǎn)時(shí)，就不能再作為這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)。例如，與節(jié)點(diǎn)C相鄰的節(jié)點(diǎn)有A與D，但因A已作為C的父節(jié)點(diǎn)在代價(jià)樹中出現(xiàn)了，所以它不能再作為c的子節(jié)點(diǎn)。?圖中的節(jié)點(diǎn)除起始節(jié)點(diǎn)A外，其它節(jié)點(diǎn)都可能要在代價(jià)樹中出現(xiàn)多次，為區(qū)分它的多次出現(xiàn)，分別用下標(biāo)l，2，…標(biāo)出，其實(shí)它們都是因中的同一節(jié)點(diǎn)。例如El，E2，E3，E4都是圖中的節(jié)點(diǎn)E。

第一步擴(kuò)展A，得第1級(jí)子節(jié)點(diǎn)C1(3)，B1(4)，按C1，B1

排序，C1代價(jià)最小，優(yōu)先擴(kuò)展第二步擴(kuò)展C1得第2級(jí)子節(jié)點(diǎn)D1(5)，

按B1，D1

排序，B1代價(jià)最小，優(yōu)先擴(kuò)展第三步擴(kuò)展B1得第2級(jí)子節(jié)點(diǎn)D2(8)，E1(9)

按D1，D2，E1排序，D1代價(jià)最小，優(yōu)先擴(kuò)展第四步擴(kuò)展D1得第3級(jí)子節(jié)點(diǎn)E2(8)，B2(9)

E2

即為目標(biāo)節(jié)點(diǎn)對(duì)此代價(jià)樹進(jìn)行代價(jià)樹的廣度優(yōu)先搜索，可得到最優(yōu)解為：A

C1

D1

E2

代價(jià)為8。由此可知從A城市到E城市舶最小費(fèi)用路線為：

A

C

D

E6.代價(jià)樹的深度優(yōu)先搜索

(1)基本思想

?在代價(jià)樹的廣度優(yōu)先搜索中，每次都是從OPEN表的全體節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)送入CLOSED表進(jìn)行考察；?代價(jià)樹的深度優(yōu)先搜索是從剛擴(kuò)展出的子節(jié)點(diǎn)中選一個(gè)代價(jià)最小的節(jié)點(diǎn)送入CLOSED表進(jìn)行考察。

例如上例:第一步擴(kuò)展A，得第1級(jí)子節(jié)點(diǎn)C1(3)，B1(4)，按C1，B1

排序，C1代價(jià)最小，優(yōu)先擴(kuò)展

第二步擴(kuò)展C1得第2級(jí)子節(jié)點(diǎn)D1(5)，

按D1

排序，D1代價(jià)最小，優(yōu)先擴(kuò)展第三步擴(kuò)展D1得第3級(jí)子節(jié)點(diǎn)E2(8)，B2(9)

E2

即為目標(biāo)節(jié)點(diǎn)

?

由于代價(jià)樹的深度優(yōu)先搜索有可能進(jìn)入無窮分支路徑，因此它是不完備的。(2)代價(jià)樹深度優(yōu)先搜索的過程開始把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)從表中移出，放入CLOSED表

OPEN表為空？擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)按代價(jià)從小到大的順序放入OPEN表的首部，并為每個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針。節(jié)點(diǎn)n為目標(biāo)節(jié)點(diǎn)？節(jié)點(diǎn)n可擴(kuò)展？失敗，退出成功，退出YNYYN把S0送入OPEN表N7.啟發(fā)式搜索

啟發(fā)式搜索要用到問題自身的某些特性情息，以指導(dǎo)搜索朝著最有希望的方向前進(jìn)。由于這種搜索針對(duì)性較強(qiáng)，因而原則上只需要搜索問題的部分狀態(tài)空間，效率較高。

(1)啟發(fā)性信息與估價(jià)函數(shù)

啟發(fā)信息?在搜索過程中，關(guān)鍵的一步是如何確定下—‘個(gè)要考察的節(jié)點(diǎn)，確定的方法不同就形成了不同的搜索策略。?如果在確定節(jié)點(diǎn)時(shí)能充分利用與問題求解有關(guān)的特性情息，估計(jì)出節(jié)點(diǎn)的重要性，就能在搜索時(shí)選擇重要性較高的節(jié)點(diǎn)，以利于求得最優(yōu)解。

像這樣可用于指導(dǎo)搜索過程，且與具體問題求解有關(guān)的控制性信息稱為啟發(fā)性信息。

估價(jià)函數(shù)用于估價(jià)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)。其一般形式為:

f(x)＝g(x)+h(x)

其中：g(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à)。

h(x):稱為啟發(fā)函數(shù)，

它體現(xiàn)了問題的啟發(fā)性信息，其形式要根據(jù)問題的特性確定，例如：?它可以是節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的距離，?也可以是節(jié)點(diǎn)x處于最優(yōu)路徑上的概率等等。

f(x):估價(jià)函數(shù)，

它表示從初始節(jié)點(diǎn)經(jīng)過節(jié)點(diǎn)x到達(dá)目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑的代價(jià)估計(jì)值，它的作用是估價(jià)OPEN表中各節(jié)點(diǎn)的重要程度，決定它們?cè)贠PEN表中的次序。

g(x):

指出了搜索的橫向趨勢(shì)，它有利于搜索的完備性，但影響搜索的效率。如果我們只關(guān)心到達(dá)目標(biāo)節(jié)點(diǎn)的路徑，并且希望有較高的搜索效率，則g(x)可以忽略，但此時(shí)會(huì)影響搜索的完備件。

因此，在確定f(x)時(shí)，要權(quán)衡各種利弊得失，使g(x)與h(x)各占適當(dāng)?shù)谋戎亍?2)局部擇優(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)，由于它每次都只是在子節(jié)點(diǎn)的范圍內(nèi)選擇下一下要考察的節(jié)點(diǎn)，范圍比較狹窄，所以稱為局部擇優(yōu)搜索。

?搜索過程：

Ⅰ.把初始節(jié)點(diǎn)S0放入OPEN表，計(jì)算f(S0)；

Ⅱ.如果OPEN表為空，則問題無解，退出；Ⅲ.把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入CLOSED表；Ⅳ.考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出；Ⅴ.若節(jié)點(diǎn)”不可擴(kuò)展，則轉(zhuǎn)第Ⅱ步。Ⅵ.擴(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)第Ⅱ步。開始把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)從表中移出，放入CLOSED表

OPEN表為空？擴(kuò)展節(jié)點(diǎn)n,計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并按估價(jià)值從小到大的順序依次放入OPEN表的首部，為每個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針。節(jié)點(diǎn)n為目標(biāo)節(jié)點(diǎn)？節(jié)點(diǎn)n可擴(kuò)展？失敗，退出成功，退出YNYYN把S0送入OPEN表,計(jì)算f(S0)N

?深度優(yōu)先搜索、代價(jià)樹的深度優(yōu)先搜索以及局部擇優(yōu)搜索比較

共同處：都是以子節(jié)點(diǎn)為考察對(duì)象，逐級(jí)向“縱向”深入發(fā)展；

不同處：它們選擇節(jié)點(diǎn)的標(biāo)推不一樣：

深度優(yōu)先搜索以子節(jié)點(diǎn)的深度作為選擇標(biāo)準(zhǔn)，后生成的子節(jié)點(diǎn)先被考察；代價(jià)樹深度優(yōu)先搜索以各子節(jié)點(diǎn)到父節(jié)點(diǎn)的代價(jià)作為選擇標(biāo)準(zhǔn)，代價(jià)小者優(yōu)先被選擇；局部擇優(yōu)搜索以估價(jià)函數(shù)的值作為選擇標(biāo)準(zhǔn)，哪一個(gè)子節(jié)點(diǎn)的f值最小就優(yōu)先被選擇。

?三種方法的關(guān)系

在局部擇優(yōu)搜索中，若令f(x)=g(x)，則局部擇優(yōu)搜索就成為代價(jià)樹的深度優(yōu)先搜索；若令f(x)=d(x)，這里d(x)表示節(jié)點(diǎn)x的深度，則局部擇優(yōu)搜索就成為深度優(yōu)先搜索。

所以深度優(yōu)先搜索和代價(jià)樹的深度優(yōu)先搜索可看作局部擇優(yōu)搜索的兩個(gè)特例。(3)全局擇優(yōu)搜索

?基本思想

局部擇優(yōu)搜索，只是從剛生成的子點(diǎn)節(jié)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，選擇的范圍比較狹窄；全局擇優(yōu)搜索，每次從OPEN表的全體節(jié)點(diǎn)中選擇一個(gè)估價(jià)值最小的節(jié)點(diǎn)進(jìn)行考察。只此一點(diǎn)與局部擇優(yōu)搜索不同。?搜索過程：

Ⅰ.把初始節(jié)點(diǎn)S0放入OPEN表，計(jì)算f(S0)；

Ⅱ.如果OPEN表為空，則問題無解，退出；Ⅲ.把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入CLOSED表；Ⅳ.考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出；Ⅴ.若節(jié)點(diǎn)”不可擴(kuò)展，則轉(zhuǎn)第Ⅱ步。Ⅵ.擴(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à)值從小到大的排序，然后轉(zhuǎn)第Ⅱ步。?廣度優(yōu)先搜索、代價(jià)樹的廣度優(yōu)先搜索以及全局擇優(yōu)搜索比較

若令f(x)=g(x)，則全局擇優(yōu)搜索就成為代價(jià)樹的廣度優(yōu)先搜索；若令f(x)=d(x)，這里d(x)表示節(jié)點(diǎn)x的深度，則全局擇優(yōu)搜索就成為廣度優(yōu)先搜索。

所以廣度優(yōu)先搜索和代價(jià)樹的廣度優(yōu)先搜索可看作全局擇優(yōu)搜索的兩個(gè)特例。開始把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)從表中移出，放入CLOSED表

OPEN表為空？擴(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à)值從小到大的排序。節(jié)點(diǎn)n為目標(biāo)節(jié)點(diǎn)？節(jié)點(diǎn)n可擴(kuò)展？失敗，退出成功，退出YNYYN把S0送入OPEN表,計(jì)算f(S0)N例：用全局擇優(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ù)。解為：S0S1S2S3Sg8.狀態(tài)空間的一般搜索過程

講了前面的一些搜索策略后，我們總結(jié)一下搜索的一般過程。(1)把初始節(jié)點(diǎn)S0放入OPEN表，并建立目前只包含S0的圖，記為G；(2)檢查OPDN表是否為空，若為空則問題無解，退出；(3)把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入CLOSED表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n；(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出；(5)擴(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中。(6)針對(duì)M中子節(jié)點(diǎn)的不同情況，分別進(jìn)行如下處理：

①對(duì)于那些未曾在G中出現(xiàn)過的M成員設(shè)置一個(gè)指向父節(jié)點(diǎn)(即節(jié)點(diǎn)n)的指針，并把它們放入OPEN表;②對(duì)于那些先前已在G中出現(xiàn)過的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針；③對(duì)于那些先前已在G中出現(xiàn)并且已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針;(7)按某種搜索策略對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序;(8)轉(zhuǎn)第(2)步。5.4與/或樹的搜索策略

當(dāng)知識(shí)表達(dá)方式采用“與/或樹”時(shí)，知識(shí)推理相應(yīng)也要使用“與/或樹”搜索方法?！芭c/或樹”搜索策略包括：

?與/或樹的廣度優(yōu)先搜索?與/或樹的深度優(yōu)先搜索

（以上屬于盲目搜索策略）?與/或樹的有序搜索?博奕樹的啟發(fā)式搜索

（以上搜索屬于啟發(fā)式搜索）

1.與/或樹的一般搜索方法

(1)與或樹搜索的有關(guān)概念和定義

P1P11P12P3P31P32P33PP2可解節(jié)點(diǎn)：

?終止節(jié)點(diǎn)是可解節(jié)點(diǎn)；?當(dāng)子節(jié)點(diǎn)中至少有一個(gè)是可解節(jié)點(diǎn)時(shí)，“或”節(jié)點(diǎn)為可解節(jié)點(diǎn)；?當(dāng)子節(jié)點(diǎn)中全部是可解節(jié)點(diǎn)時(shí)，“與”節(jié)點(diǎn)為可解節(jié)點(diǎn)；不可解節(jié)點(diǎn)：

?沒有子節(jié)點(diǎn)的非終止節(jié)點(diǎn)是不可解節(jié)點(diǎn)；?當(dāng)子節(jié)點(diǎn)中全部節(jié)點(diǎn)是不可解節(jié)點(diǎn)時(shí)，“或”節(jié)點(diǎn)為不可解節(jié)點(diǎn)；?當(dāng)子節(jié)點(diǎn)中至少有一個(gè)是不可解節(jié)點(diǎn)時(shí)，“與”節(jié)點(diǎn)為不可解節(jié)點(diǎn)；

可解標(biāo)示過程：

一個(gè)節(jié)點(diǎn)是否為可解節(jié)點(diǎn)是由它的子節(jié)點(diǎn)確定的，由可解子節(jié)點(diǎn)來確定父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為可解節(jié)點(diǎn)的過程稱為可解標(biāo)示過程。不可解標(biāo)示過程：

由不可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為不可解節(jié)點(diǎn)的過程稱為不可解標(biāo)示過程。

在與/或樹的搜索過程中將反復(fù)使用這兩個(gè)過程，直到初始節(jié)點(diǎn)(即原始問題)被標(biāo)示為可解或不可解節(jié)點(diǎn)為止。(2)與/或樹的一般搜索道程：

Ⅰ.把原始問題作為初始節(jié)點(diǎn)S0，并把它作為當(dāng)前節(jié)點(diǎn)；

Ⅱ.應(yīng)用分解或等價(jià)變換算符對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展；

Ⅲ.為每個(gè)被擴(kuò)展的子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；

Ⅳ.選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第Ⅱ步和第Ⅲ步，在此期間要多次調(diào)用可解標(biāo)示過程和不可解標(biāo)示過程，直到初始節(jié)點(diǎn)被標(biāo)示為可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)為止。

(可解與不可解標(biāo)不過程都是自下而上進(jìn)行的，即由于節(jié)點(diǎn)的可解性確定父節(jié)點(diǎn)的可解性.)搜索樹——由上述搜索過程所形成的節(jié)點(diǎn)和指針結(jié)構(gòu)稱為搜索樹。解樹——如果在搜索的某一時(shí)刻，通過可解標(biāo)示過程可確定初始節(jié)點(diǎn)是可解的，則由此初始節(jié)點(diǎn)及其下屬的可解節(jié)點(diǎn)就構(gòu)成了解樹。(3)與/或樹搜索的兩個(gè)特性

由于與/或樹搜索的目標(biāo)是尋找解樹，因此：

?如果已確定某個(gè)節(jié)點(diǎn)為可解節(jié)點(diǎn)，則其不可解的后裔節(jié)點(diǎn)就不再有用，可從搜索樹中刪去；?如果已確定某個(gè)節(jié)點(diǎn)是不可解節(jié)點(diǎn)，則其全部后裔節(jié)點(diǎn)都不再有用，可從搜索樹中刪去，但當(dāng)前這個(gè)不可解節(jié)點(diǎn)還不能刪去，因?yàn)樵谂袛嗥湎容吂?jié)點(diǎn)的可解性時(shí)還要用到它。

這兩種特性，可用來提高搜索效率。2.與/或樹的廣度優(yōu)先搜索

與/或樹的廣度優(yōu)先搜索與狀態(tài)空間的廣度優(yōu)先搜索類似，也是按照“無產(chǎn)生的節(jié)點(diǎn)先擴(kuò)展”的原則進(jìn)行搜索，只是在搜索過程中要多次調(diào)用可解標(biāo)示過程和不可解標(biāo)示過程。搜索過程如圖

其中：應(yīng)用可解標(biāo)示過程為：如果考察的子節(jié)點(diǎn)為可解節(jié)點(diǎn)，則逆向?qū)ζ涓腹?jié)點(diǎn)、祖父節(jié)點(diǎn)等先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)示。應(yīng)用不可解標(biāo)示過程為：如果考察的子節(jié)點(diǎn)為不可解節(jié)點(diǎn)，則逆向?qū)ζ涓腹?jié)點(diǎn)、祖父節(jié)點(diǎn)等先輩節(jié)點(diǎn)中的不可解節(jié)點(diǎn)進(jìn)行標(biāo)示。例：設(shè)有如圖所示的與/或樹，節(jié)點(diǎn)按圖中所標(biāo)注的順序號(hào)進(jìn)行擴(kuò)展。其中標(biāo)有t1,t2,t3,t4的節(jié)點(diǎn)均為終止節(jié)點(diǎn)，A和E為不可解的端節(jié)點(diǎn)。

搜索過程為：

(1)首先擴(kuò)展1號(hào)節(jié)點(diǎn)——得到2號(hào)節(jié)點(diǎn)和3號(hào)節(jié)點(diǎn)。

（OPEN表中有2，3號(hào)節(jié)點(diǎn)）由于這兩個(gè)子節(jié)點(diǎn)均不是終止節(jié)點(diǎn)，所以接著擴(kuò)展2號(hào)節(jié)點(diǎn)。

（此時(shí)OPEN表中只剩下3號(hào)節(jié)點(diǎn)）(2)擴(kuò)展2號(hào)節(jié)點(diǎn)——得到4號(hào)節(jié)點(diǎn)和t1節(jié)點(diǎn)。

（此時(shí)OPEN表中的節(jié)點(diǎn)有：3號(hào)節(jié)點(diǎn)、4號(hào)節(jié)點(diǎn)及t1節(jié)點(diǎn)）

標(biāo)示t1節(jié)點(diǎn)：由于t1是終止節(jié)點(diǎn)，則標(biāo)示它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)示過程，對(duì)其先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)示。但t1的父節(jié)點(diǎn)是一個(gè)“與”節(jié)點(diǎn)，因此僅由t1可解尚不能確定2號(hào)節(jié)點(diǎn)是否為可解節(jié)點(diǎn)。所以繼續(xù)搜索，下一步擴(kuò)展的是3號(hào)節(jié)點(diǎn)。(3)擴(kuò)展3號(hào)節(jié)點(diǎn)——得到5號(hào)節(jié)點(diǎn)與B節(jié)點(diǎn)。兩者均不是終止節(jié)點(diǎn)，所以接著擴(kuò)展4號(hào)節(jié)點(diǎn)。(4)擴(kuò)展4號(hào)節(jié)點(diǎn)——得到節(jié)點(diǎn)A和t2節(jié)點(diǎn)。

標(biāo)示t2：由于t2是終止節(jié)點(diǎn)，所以標(biāo)示它為可解節(jié)點(diǎn)，

標(biāo)示4號(hào)、2號(hào)節(jié)點(diǎn)：

由于t2是可解節(jié)點(diǎn)，逆推，應(yīng)用可解標(biāo)示過程標(biāo)示出4號(hào)節(jié)點(diǎn)、2號(hào)節(jié)點(diǎn)均為可解節(jié)點(diǎn)，但l導(dǎo)節(jié)點(diǎn)目前還不能確定它是否為可解節(jié)點(diǎn)。

（此時(shí)5號(hào)節(jié)點(diǎn)是OPEN表中的第一個(gè)待考察的節(jié)點(diǎn)）所以下一步擴(kuò)展5號(hào)節(jié)點(diǎn)。(5)擴(kuò)展5號(hào)節(jié)點(diǎn)——得到t3和t4節(jié)點(diǎn)。

標(biāo)示t3和t4節(jié)點(diǎn)：由于t3和t4節(jié)點(diǎn)均為終止節(jié)點(diǎn)，所以被標(biāo)示為可解節(jié)點(diǎn)，

標(biāo)示5號(hào)、3號(hào)、1號(hào)節(jié)點(diǎn)：通過應(yīng)用可解標(biāo)示過程可得到5號(hào)、3號(hào)及1號(hào)節(jié)點(diǎn)均為可解節(jié)點(diǎn)。(6)搜索成功，得到了由1，2，3，4，5號(hào)節(jié)點(diǎn)及tl，t2，t3，t4節(jié)點(diǎn)構(gòu)成的解樹。如圖中粗線所示。3.與/或樹的深度優(yōu)先搜索

與/或樹的深度優(yōu)先搜索過程和與/或樹的廣度優(yōu)先搜索過程基本相同，注意：