《人工智能》PPT課件本課件僅供大家學習學習學習完畢請自覺刪除謝謝本課件僅供大家學習學習學習完畢請自覺刪除謝謝?另外，可能存在多條線路都可實現對問題的求解，這就又出現按哪一條線路進行求解以獲得較高的運行效率的問題。

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

搜索分為盲目搜索和啟發式搜索。

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

啟發式搜索——在搜索中加入了與問題有關的啟發性信息，用以指導搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優解。5.2求解問題的表示方法

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

一般來說，有兩種方法：

狀態空間表示法；與/或樹表示法；

1.狀態空間表示法

狀態空間表示法是用來表示問題及其搜索過程的一種方法，它是人工智能中最基本的形式化方法。狀態空間表示法是用“狀態”和“算符”來表示問題的一種方法。其中，“狀態”——用以描述問題求解過程中不同時刻的狀況；“算符”——表示對狀態的操作，算符的每一次使用就使問題由一種狀態變換為另一種狀態;解——當到達目標狀態時，由初始狀態到目標狀態所用算符的序列就是問題的一個解。Ⅰ.狀態

狀態是描述問題求解過程中任一時刻狀況的數據結構，一般用一組變量的有序組合表示：

SK＝(SK0,SK1,…)當給每一個分量以確定的值時，就得到了一個具體的狀態。Ⅱ.算符

引起狀態中某些分量發生變化，從而使問題由一個狀態變為另一個狀態的操作稱為算符。在產生式系統中，每一條產生式規則就是一個算符。Ⅲ.狀態空間

由問題的全部狀態及一切可用算符所構成的集合稱為問題的狀態空間，—般用—個三元組表示：(S，F，G)其中,S是問題的所有初始狀態構成的集合；F是算符的集合；G是目標狀態的集合。狀態空間的圖示形式稱為狀態空間圖。其中，節點表示狀態；有向邊(弧)表示算符。例1：錢幣翻轉問題，如圖所示。設有三個錢幣，起初是狀態為（反正反），允許每次翻轉一個錢幣（只反一個，也必反一個），連反三次，問是否可達到目標狀態？（正正正）或（反反反）？正反正正正反反反反設用Sk=(s1,s2,s3)表示問題的狀態，s=0表示錢幣正面，s=1表示錢幣反面。則錢幣可能出現的狀態有八種：

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)

問題的初始狀態集合：S={S5}

目標狀態集合：G={S0,S7}

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

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

把一個復雜問題分解為若干個較為簡單的子問題，然后對每個子問題分別進行求解，最后把各子問題的解復合起來就得到了原問題的解。這是“與”的問題。PP1P2P3P1,

P2,P3為子節點，子問題對應子節點。P為“與”節點，只有當三個子問題都有解時，P才可解。

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

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

Ⅰ.本原問題

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

Ⅱ.端節點與終止節點

在與/或樹中，沒有子節點的節點稱為端節點；本原問題所對應的節點稱為終止節點。顯然終止節點一定是端節點，但端節點不一定是終止節點。Ⅲ.可解節點

在與/或樹中，滿足下列條件之一者，稱為可解節點：?它是一個終止節點。?它是一個“或”節點，且其子節點中至少有一個是可解節點。?它是一個“與”節點，且其子節點全部是可解節點。Ⅳ.不可解節點

關于可解節點的三個條件全部不滿足的節點稱為不可解節點。

Ⅴ.解樹

由可解節點所構成，并且由這些可解節點可推出初始節點(它對應于原始問題)為可解節點的子樹稱為解樹。在解樹中一定包含初始節點。

例如：t標出的節點是終止節點，根據可解節點的定義，原始問題P是可解的。ttP例：三階漢諾塔問題。設有A，B，C三個金片以及三根鋼針，三個金片按自上而下從小到大的順序穿在1號鋼針上，要求把它們全部移到3號鋼針上，而且每次只能移動一個金片，任何時刻都不能把大的金片壓在小的金片上面，如圖所示。首先進行問題分析：

(1)為了把三個金片全部移到3號針上，必須先把金片C移到3號針上。(2)為了移金片C，必須先把金片A及B移到2號針上。(3)當把金片c移到3號針上后，就可把A，B從2號移到3號針上，這樣就可完成問題的求解。

由此分析，得到了原問題的三個子問題：(1)把金片A及B移到2號針的雙金片問題。(2)把金片C移到3號針的單金片問題。(3)把金片A及B移到3號針的雙金片問題。

其中，子問題(1)與子問題(3)又分別可分解為三個子問題。ABCABC

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

設仍用狀態表示問題在任一時刻的狀況；

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

k代表金片A所在的鋼針號。用“

”表示狀態的變換；這樣原始問題就可表示為：(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)它指出了移動金片的次序。此圖共有七個終止節點，對應于七個本原問題，它們是通過“分解”得到的。5.3狀態空間搜索策略

1.概述

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

顯式存儲：把與問題有關的全部狀態空間圖，即相應的全部知識（事實性知識、過程性知識，控制性知識）都直接存入知識庫，稱為“顯式存儲”或“顯式圖”。

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

OPEN表：用于存放剛生成的節點。對于不同的搜索策略，節點在OPEN表中的排列順序是不同的。

CLOSED表：用于存放將要擴展或者已擴展的節點，所謂對節點進行“擴展”是指：用合適的算符對該節點進行操作，生成一組子節點。狀態節點父節點OPEN表編號狀態節點父節點CLOSED表(5)狀態空間法搜索策略

?廣度優先搜索?深度優先搜索?有界深度優先搜索?代價樹的廣度優先搜索?代價樹的深度優先搜索

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

(1)基本思想從初始節點開始，按照某種生成規則（算符）逐步生成下一級各子節點，順序（先生成的子節點優先檢查，優先擴展）地檢查是否出現目標節點，在該級全部節點中沿廣度進行“橫向”掃描，即：沿“廣度”遍歷所有節點，故稱“廣度優先搜索法”。

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

Ⅰ.把初始節點S0放人OPEN表，若S0為目標節點，則得到問題的解，退出；

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

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

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

要求尋找從初始狀態到目標狀態的路徑。

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

缺點：

廣度優先搜索的盲目性較大，當目標節點距離初始節點較遠時將會產生許多無用節點，搜索效率低，這是它的缺點。優點：

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

(1)基本思想從初始節點S0開始，按生成規則生成下一級各子節點，若目標節點未出現，則按“最晚生成的子節點優先擴展”的原則，生成再下一級的子節點，如此下去，沿著最晚生成的子節點分支，逐級向“縱向”深入發展，故稱為“深度優先搜索法”。

(2)深度優先搜索法搜索過程

該過程與廣度優先搜索的唯一區別是：

廣度優先搜索是將節點n的子節點放入到OPEN表的尾部，而深度優先搜索是把節點n的子節點放入到OPEN表的首部。

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

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

(1)基本思想

為了解決深度優先搜索不完備的問題，避免搜索過程陷入無窮分支的死循環，對深度優先搜索引入搜索深度的界限（設為dm），當搜索深度達到了深度界限，而尚未出現目標節點時，就換一個分支進行搜索。

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

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

20

25

26

28(Sg)

(3)有界深度優先搜索法的改進上述方法存在兩個問題：

?深度界限的選擇很重要

dm

若太小，則達不到解的深度，得不到解；若太大，則搜索時將產生許多無用的子節點，既浪費了計算機的存儲空間與時間，又降低了搜索效率。由于解的路徑長度事先難以預料，所以要恰當地給出dm的值是比較困難的。

?即使能求出解，它也不一定是最優解。

解決方法：

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

先任意給定一個較小的數作為dm，然后進行上述的有界深度優先搜索，當搜索達到了指定的深度界限dm仍未發現目標節點，并且CLOSED表中仍有待擴展節點時．就將這些節點送回OPEN表，同時增大深度界限dm，繼續向下搜索。如此不斷地增大dm，只要問題有解，就一定可以找到它。

Ⅱ.增加一個R表

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

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

求最優解的有界深度優先搜索過程如圖所示。其中Sg是目標節點．Sg*是距離S0最近的目標節點。5.代價樹的廣度優先搜索(1)基本思想

代價：從一個節點，經過一條支路，轉移到另一個節點，所需支付的代價（時間、費用等）。

代價樹：邊上標有代價的樹稱為代價樹。

在代價樹中，若用g(x)表示從初始節點S0到節點x的代價，用c(x1,x2)表示從父節點x1到子節點x2的代價，則有：

g(x2)=g(x1)十c(x1,x2)

代價樹廣皮優先搜索的基本思想是：

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

(2)代價樹的廣度優先搜索過程開始把OPEN表的第一個節點(記為節點n)從表中移出，放入CLOSED表

OPEN表為空？擴展節點n,將其子節點放入OPEN表，并為每個子節點配置指向節點n的指針。計算各子節點的代價，把OPEN表的全部節點按代價排序。節點n為目標節點？節點n可擴展？失敗，退出成功，退出YNYYN把S0送入OPEN表N例：右圖是五城市間的交通路線圖，A城市是出發地，

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

第一步擴展A，得第1級子節點C1(3)，B1(4)，按C1，B1

排序，C1代價最小，優先擴展第二步擴展C1得第2級子節點D1(5)，

按B1，D1

排序，B1代價最小，優先擴展第三步擴展B1得第2級子節點D2(8)，E1(9)

按D1，D2，E1排序，D1代價最小，優先擴展第四步擴展D1得第3級子節點E2(8)，B2(9)

E2

即為目標節點對此代價樹進行代價樹的廣度優先搜索，可得到最優解為：A

C1

D1

E2

代價為8。由此可知從A城市到E城市舶最小費用路線為：

A

C

D

E6.代價樹的深度優先搜索

(1)基本思想

?在代價樹的廣度優先搜索中，每次都是從OPEN表的全體節點中選擇一個代價最小的節點送入CLOSED表進行考察；?代價樹的深度優先搜索是從剛擴展出的子節點中選一個代價最小的節點送入CLOSED表進行考察。

例如上例:第一步擴展A，得第1級子節點C1(3)，B1(4)，按C1，B1

排序，C1代價最小，優先擴展

第二步擴展C1得第2級子節點D1(5)，

按D1

排序，D1代價最小，優先擴展第三步擴展D1得第3級子節點E2(8)，B2(9)

E2

即為目標節點

?

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

OPEN表為空？擴展節點n,將其子節點按代價從小到大的順序放入OPEN表的首部，并為每個子節點配置指向節點n的指針。節點n為目標節點？節點n可擴展？失敗，退出成功，退出YNYYN把S0送入OPEN表N7.啟發式搜索

啟發式搜索要用到問題自身的某些特性情息，以指導搜索朝著最有希望的方向前進。由于這種搜索針對性較強，因而原則上只需要搜索問題的部分狀態空間，效率較高。

(1)啟發性信息與估價函數

啟發信息?在搜索過程中，關鍵的一步是如何確定下—‘個要考察的節點，確定的方法不同就形成了不同的搜索策略。?如果在確定節點時能充分利用與問題求解有關的特性情息，估計出節點的重要性，就能在搜索時選擇重要性較高的節點，以利于求得最優解。

像這樣可用于指導搜索過程，且與具體問題求解有關的控制性信息稱為啟發性信息。

估價函數用于估價節點重要性的函數稱為估價函數。其一般形式為:

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

其中：g(x)為從初始節點S0到節點x已經實際付出的代價；h(x)是從節點x到目標節點Sg的最優路徑的估計代價。

h(x):稱為啟發函數，

它體現了問題的啟發性信息，其形式要根據問題的特性確定，例如：?它可以是節點x到目標節點的距離，?也可以是節點x處于最優路徑上的概率等等。

f(x):估價函數，

它表示從初始節點經過節點x到達目標節點的最優路徑的代價估計值，它的作用是估價OPEN表中各節點的重要程度，決定它們在OPEN表中的次序。

g(x):

指出了搜索的橫向趨勢，它有利于搜索的完備性，但影響搜索的效率。如果我們只關心到達目標節點的路徑，并且希望有較高的搜索效率，則g(x)可以忽略，但此時會影響搜索的完備件。

因此，在確定f(x)時，要權衡各種利弊得失，使g(x)與h(x)各占適當的比重。(2)局部擇優搜索局部擇優搜索是一種啟發式搜索方法，是對深度優先搜索方法的一種改進。

?基本思想：當一個節點被擴展以后，按f(x)對每一個子節點計算估價值，并選擇最小者作為下一個要考察的節點，由于它每次都只是在子節點的范圍內選擇下一下要考察的節點，范圍比較狹窄，所以稱為局部擇優搜索。

?搜索過程：

Ⅰ.把初始節點S0放入OPEN表，計算f(S0)；

Ⅱ.如果OPEN表為空，則問題無解，退出；Ⅲ.把OPEN表的第一個節點(記為節點n)取出放入CLOSED表；Ⅳ.考察節點n是否為目標節點。若是，則求得了問題的解，退出；Ⅴ.若節點”不可擴展，則轉第Ⅱ步。Ⅵ.擴展節點n，用估價函數f(x)計算每個子節點的估價值，并按估價值從小到大的順序依次放到OPEN表的首部，為每個子節點配置指向父節點的指針。然后轉第Ⅱ步。開始把OPEN表的第一個節點(記為節點n)從表中移出，放入CLOSED表

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

?深度優先搜索、代價樹的深度優先搜索以及局部擇優搜索比較

共同處：都是以子節點為考察對象，逐級向“縱向”深入發展；

不同處：它們選擇節點的標推不一樣：

深度優先搜索以子節點的深度作為選擇標準，后生成的子節點先被考察；代價樹深度優先搜索以各子節點到父節點的代價作為選擇標準，代價小者優先被選擇；局部擇優搜索以估價函數的值作為選擇標準，哪一個子節點的f值最小就優先被選擇。

?三種方法的關系

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

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

?基本思想

局部擇優搜索，只是從剛生成的子點節中選擇一個節點進行考察，選擇的范圍比較狹窄；全局擇優搜索，每次從OPEN表的全體節點中選擇一個估價值最小的節點進行考察。只此一點與局部擇優搜索不同。?搜索過程：

Ⅰ.把初始節點S0放入OPEN表，計算f(S0)；

Ⅱ.如果OPEN表為空，則問題無解，退出；Ⅲ.把OPEN表的第一個節點(記為節點n)取出放入CLOSED表；Ⅳ.考察節點n是否為目標節點。若是，則求得了問題的解，退出；Ⅴ.若節點”不可擴展，則轉第Ⅱ步。Ⅵ.擴展節點n，用估價函數f(x)計算每個子節點的估價值，為每個子節點配置指向父節點的指針,把這些節點都送入OPEN表，然后對OPEN表中的全部節點按估價值從小到大的排序，然后轉第Ⅱ步。?廣度優先搜索、代價樹的廣度優先搜索以及全局擇優搜索比較

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

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

OPEN表為空？擴展節點n,用估價函數f(x)計算每個子節點的估價值,為每個子節點配置指向父節點的指針,把這些節點送入OPEN表，并對OPEN表中的全部節點按估價值從小到大的排序。節點n為目標節點？節點n可擴展？失敗，退出成功，退出YNYYN把S0送入OPEN表,計算f(S0)N例：用全局擇優搜索求解重排九宮問題。設估價函數為

f(x)＝d(x)+h(x)其中，d(x)表示節點x的深度，h(x)表示節點x的格局與目標節點格局不相同的牌數。解為：S0S1S2S3Sg8.狀態空間的一般搜索過程

講了前面的一些搜索策略后，我們總結一下搜索的一般過程。(1)把初始節點S0放入OPEN表，并建立目前只包含S0的圖，記為G；(2)檢查OPDN表是否為空，若為空則問題無解，退出；(3)把OPEN表的第一個節點取出放入CLOSED表，并記該節點為節點n；(4)考察節點n是否為目標節點。若是，則求得了問題的解，退出；(5)擴展節點n，生成一組子節點。把其中不是節點n先輩的那些子節點記作集合M，并把這些子節點作為節點n的子節點加入G中。(6)針對M中子節點的不同情況，分別進行如下處理：

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

當知識表達方式采用“與/或樹”時，知識推理相應也要使用“與/或樹”搜索方法。“與/或樹”搜索策略包括：

?與/或樹的廣度優先搜索?與/或樹的深度優先搜索

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

（以上搜索屬于啟發式搜索）

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

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

P1P11P12P3P31P32P33PP2可解節點：

?終止節點是可解節點；?當子節點中至少有一個是可解節點時，“或”節點為可解節點；?當子節點中全部是可解節點時，“與”節點為可解節點；不可解節點：

?沒有子節點的非終止節點是不可解節點；?當子節點中全部節點是不可解節點時，“或”節點為不可解節點；?當子節點中至少有一個是不可解節點時，“與”節點為不可解節點；

可解標示過程：

一個節點是否為可解節點是由它的子節點確定的，由可解子節點來確定父節點、祖父節點等為可解節點的過程稱為可解標示過程。不可解標示過程：

由不可解子節點來確定其父節點、祖父節點等為不可解節點的過程稱為不可解標示過程。

在與/或樹的搜索過程中將反復使用這兩個過程，直到初始節點(即原始問題)被標示為可解或不可解節點為止。(2)與/或樹的一般搜索道程：

Ⅰ.把原始問題作為初始節點S0，并把它作為當前節點；

Ⅱ.應用分解或等價變換算符對當前節點進行擴展；

Ⅲ.為每個被擴展的子節點設置指向父節點的指針；

Ⅳ.選擇合適的子節點作為當前節點，反復執行第Ⅱ步和第Ⅲ步，在此期間要多次調用可解標示過程和不可解標示過程，直到初始節點被標示為可解節點或不可解節點為止。

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

由于與/或樹搜索的目標是尋找解樹，因此：

?如果已確定某個節點為可解節點，則其不可解的后裔節點就不再有用，可從搜索樹中刪去；?如果已確定某個節點是不可解節點，則其全部后裔節點都不再有用，可從搜索樹中刪去，但當前這個不可解節點還不能刪去，因為在判斷其先輩節點的可解性時還要用到它。

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

與/或樹的廣度優先搜索與狀態空間的廣度優先搜索類似，也是按照“無產生的節點先擴展”的原則進行搜索，只是在搜索過程中要多次調用可解標示過程和不可解標示過程。搜索過程如圖

其中：應用可解標示過程為：如果考察的子節點為可解節點，則逆向對其父節點、祖父節點等先輩節點中的可解節點進行標示。應用不可解標示過程為：如果考察的子節點為不可解節點，則逆向對其父節點、祖父節點等先輩節點中的不可解節點進行標示。例：設有如圖所示的與/或樹，節點按圖中所標注的順序號進行擴展。其中標有t1,t2,t3,t4的節點均為終止節點，A和E為不可解的端節點。

搜索過程為：

(1)首先擴展1號節點——得到2號節點和3號節點。

（OPEN表中有2，3號節點）由于這兩個子節點均不是終止節點，所以接著擴展2號節點。

（此時OPEN表中只剩下3號節點）(2)擴展2號節點——得到4號節點和t1節點。

（此時OPEN表中的節點有：3號節點、4號節點及t1節點）

標示t1節點：由于t1是終止節點，則標示它為可解節點，并應用可解標示過程，對其先輩節點中的可解節點進行標示。但t1的父節點是一個“與”節點，因此僅由t1可解尚不能確定2號節點是否為可解節點。所以繼續搜索，下一步擴展的是3號節點。(3)擴展3號節點——得到5號節點與B節點。兩者均不是終止節點，所以接著擴展4號節點。(4)擴展4號節點——得到節點A和t2節點。

標示t2：由于t2是終止節點，所以標示它為可解節點，

標示4號、2號節點：

由于t2是可解節點，逆推，應用可解標示過程標示出4號節點、2號節點均為可解節點，但l導節點目前還不能確定它是否為可解節點。

（此時5號節點是OPEN表中的第一個待考察的節點）所以下一步擴展5號節點。(5)擴展5號節點——得到t3和t4節點。

標示t3和t4節點：由于t3和t4節點均為終止節點，所以被標示為可解節點，

標示5號、3號、1號節點：通過應用可解標示過程可得到5號、3號及1號節點均為可解節點。(6)搜索成功，得到了由1，2，3，4，5號節點及tl，t2，t3，t4節點構成的解樹。如圖中粗線所示。3.與/或樹的深度優先搜索

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