搜索策略搜索是人工智能中的一個(gè)基本問題是推理課件

第六章搜索策略

搜索是人工智能中的一個(gè)基本問題，是推理不可分割的一部分，它直接關(guān)系到智能系統(tǒng)的性能與運(yùn)行效率，因而尼爾遜把它列為人工智能研究中的四個(gè)核心問題之一。5.1基本概念

1.什么是搜索

人工智能所要解決的大部分問題是結(jié)構(gòu)不良或非結(jié)構(gòu)化的問題，對這樣的問題一般不存在成熟的求解算法可供利用，而只能是利用已有的知識一步步摸索著前進(jìn)。

在此過程中，存在著如何尋找可用知識的問題，即如何確定推理路線，使其付出的代價(jià)盡可能的少，而問題又能得到較好的解決。

如：在正向推理中，

?對已知的初始事實(shí)，需要在知識庫中尋找可使用的知識，這就存在按何種線路進(jìn)行尋找的問題。第六章搜索策略1?另外，可能存在多條線路都可實(shí)現(xiàn)對問題的求解，這就又出現(xiàn)按哪一條線路進(jìn)行求解以獲得較高的運(yùn)行效率的問題。

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

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

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

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

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

一般來說，有兩種方法：

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

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

狀態(tài)空間表示法是用來表示問題及其搜索過程的一種方法，它是人工智能中最基本的形式化方法。狀態(tài)空間表示法是用“狀態(tài)”和“算符”來表示問題的一種方法。其中，“狀態(tài)”——用以描述問題求解過程中不同時(shí)刻的狀況；“算符”——表示對狀態(tài)的操作，算符的每一次使用就使問題由一種狀態(tài)變換為另一種狀態(tài);解——當(dāng)?shù)竭_(dá)目標(biāo)狀態(tài)時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所用算符的序列就是問題的一個(gè)解。5.2求解問題的表示方法3Ⅰ.狀態(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)；有向邊(弧)表示算符。Ⅰ.狀態(tài)4例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翻一面；例1：錢幣翻轉(zhuǎn)問題，如圖所示。設(shè)有三個(gè)錢幣，起初是狀態(tài)為（反5上述問題的狀態(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,且有七種操作方式。f1f1f1f1f2f2f2f2f3f3f3f3上述問題的狀態(tài)空間“三元組”為：（{S5},{f1,f262.與/或樹表示法與/或樹是用于表示問題及其求解過程的又一種形式化方法，通常用于表示比較復(fù)雜問題的求解。對于一個(gè)復(fù)雜問題，直接求解往往比較困難。此時(shí)，可通過下述方法進(jìn)行簡化：(1)分解：“與”樹

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

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

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

如圖所示，稱為“或”樹。PP1P2P32.與/或樹表示法PP1P2P3P1,P2,P3為子7與/或樹：將上述兩種方法也可結(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)；本原問題所對應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)。顯然終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)不一定是終止節(jié)點(diǎn)。與/或樹：P1P11P12P3P31P32P33PP8Ⅲ.可解節(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)(它對應(yīng)于原始問題)為可解節(jié)點(diǎn)的子樹稱為解樹。在解樹中一定包含初始節(jié)點(diǎn)。

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

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

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

其中，子問題(1)與子問題(3)又分別可分解為三個(gè)子問題。ABCABC例：三階漢諾塔問題。設(shè)有A，B，C三個(gè)金片以及三根鋼針，三個(gè)10

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

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

用三元組(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)它指出了移動金片的次序。此圖共有七個(gè)終止節(jié)點(diǎn)，對應(yīng)于七個(gè)本原問題，它們是通過“分解”得到的。為了用與/或樹把問題的分解過程表示出來，先要定義問題的形115.3狀態(tài)空間搜索策略

1.概述

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

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

隱式存儲：只存儲與問題有關(guān)的部分知識，在求解過程中，又初始狀態(tài)出發(fā)，運(yùn)用相應(yīng)的知識，逐步生成所需的部分狀態(tài)空間圖，通過搜索推理，找到所求目標(biāo)。這樣只需在知識庫中存儲局部狀態(tài)空間圖，稱為“隱式圖”。通常，為了節(jié)約計(jì)算機(jī)的存儲容量，提高搜索推理效率，采用隱式存儲方法，進(jìn)行隱士圖搜索推理。5.3狀態(tài)空間搜索策略12(2)搜索方法Ⅰ.運(yùn)用事實(shí)性知識，給出問題的部分狀態(tài)描述，包括：初始狀態(tài)S0，目標(biāo)狀態(tài)Sg，和某些中間狀態(tài)Sh；Ⅱ.運(yùn)用過程性知識，給出由狀態(tài)空間圖“父節(jié)點(diǎn)”生成“子節(jié)點(diǎn)”的操作“算符”；Ⅲ.運(yùn)用控制性知識（在此為搜索策略），選取適當(dāng)?shù)墓?jié)點(diǎn)，控制繼續(xù)搜索的方向。(3)搜索過程Ⅰ.給出初始狀態(tài)（初始節(jié)點(diǎn)）；Ⅱ.選擇選擇適用的算符對其進(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í)為止。(2)搜索方法13(4)搜索過程中要用到的兩個(gè)數(shù)據(jù)結(jié)構(gòu)

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

CLOSED表：用于存放將要擴(kuò)展或者已擴(kuò)展的節(jié)點(diǎn)，所謂對節(jié)點(diǎn)進(jìn)行“擴(kuò)展”是指：用合適的算符對該節(jié)點(diǎn)進(jìn)行操作，生成一組子節(jié)點(diǎn)。狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)OPEN表編號狀態(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ā)式搜索）(4)搜索過程中要用到的兩個(gè)數(shù)據(jù)結(jié)構(gòu)狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)OPEN142.廣度優(yōu)先搜索法（Breadth-FirstSearch)

(1)基本思想從初始節(jié)點(diǎn)開始，按照某種生成規(guī)則（算符）逐步生成下一級各子節(jié)點(diǎn)，順序（先生成的子節(jié)點(diǎn)優(yōu)先檢查，優(yōu)先擴(kuò)展）地檢查是否出現(xiàn)目標(biāo)節(jié)點(diǎn)，在該級全部節(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)向第Ⅱ步。2.廣度優(yōu)先搜索法（Breadth-FirstSearc15開始把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開始把S0送入OPEN表把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)16狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)OPEN表編號狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)CLOSED表S012S0126345S0126345789(a)(b)(c)(d)S0S01121200034203356789411112233445S010203141Sg(9)S0491狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)OPEN表編號狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)CLOSED表S017例：重排九宮問題。在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例：重排九宮問題。在3X3的方格棋盤上放置分別標(biāo)有數(shù)字1，18由圖可以看出，解的路徑是:S0381626(Sg)小結(jié)：

缺點(diǎn)：

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

只要問題有