《人工智能》課件

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

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

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

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

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

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

一般來說，有兩種方法：

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

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

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

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

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

引起狀態(tài)中某些分量發(fā)生變化，從而使問題由一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作稱為算符。在產(chǎn)生式系統(tǒng)中，每一條產(chǎn)生式規(guī)則就是一個算符。Ⅲ.狀態(tài)空間

由問題的全部狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)空間，—般用—個三元組表示：(S，F(xiàn)，G)其中,S是問題的所有初始狀態(tài)構(gòu)成的集合；F是算符的集合；G是目標狀態(tài)的集合。狀態(tài)空間的圖示形式稱為狀態(tài)空間圖。其中，節(jié)點表示狀態(tài)；有向邊(弧)表示算符。例1：錢幣翻轉(zhuǎn)問題，如圖所示。設有三個錢幣，起初是狀態(tài)為（反正反），允許每次翻轉(zhuǎn)一個錢幣（只反一個，也必反一個），連反三次，問是否可達到目標狀態(tài)？（正正正）或（反反反）？正反正正正反反反反設用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}

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

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

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

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

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

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

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

Ⅰ.本原問題

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

Ⅱ.端節(jié)點與終止節(jié)點

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

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

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

Ⅴ.解樹

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

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

(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

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

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

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

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

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

1.概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

缺點：

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

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

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

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

該過程與廣度優(yōu)先搜索的唯一區(qū)別是：

廣度優(yōu)先搜索是將節(jié)點n的子節(jié)點放入到OPEN表的尾部，而深度優(yōu)先搜索是把節(jié)點n的子節(jié)點放入到OPEN表的首部。

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

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

(1)基本思想

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

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

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

20

25

26

28(Sg)

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

?深度界限的選擇很重要

dm

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

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

解決方法：

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

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

Ⅱ.增加一個R表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

按B1，D1

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

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

E2

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

C1

D1

E2

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

A

C

D

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

(1)基本思想

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

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

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

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

按D1

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

E2

即為目標節(jié)點

?

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

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

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

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

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

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

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

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

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

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

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

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

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

g(x):

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

因此，在確定f(x)時，要權(quán)衡各種利弊得失，使g(x)與h(x)各占適當?shù)谋戎亍?2)局部擇優(yōu)搜索局部擇優(yōu)搜索是一種啟發(fā)式搜索方法，是對深度優(yōu)先搜索方法的一種改進。

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

?搜索過程：

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

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

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

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

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

不同處：它們選擇節(jié)點的標推不一樣：

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

?三種方法的關系

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

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

?基本思想

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P1P11P12P3P31P32P33PP2可解節(jié)點：

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

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

可解標示過程：

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

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

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

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

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

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

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

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

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

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

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

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

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

搜索過程為：

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

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

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

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

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

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

標示4號、2號節(jié)點：

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

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

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

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

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