人工智能(問題求解基本原理及搜索技術(shù)

)人工智能問題求解基本原理問題求解：在給定條件下，尋求一個(gè)能解決某類問題且能在有限步驟內(nèi)完成的算法。

問題求解特征：傳統(tǒng)軟件：

①求解的問題是能夠用數(shù)學(xué)精確描述的良結(jié)構(gòu)的問題（如，解方程）；②計(jì)算機(jī)執(zhí)行的繁雜的統(tǒng)計(jì)計(jì)算任務(wù)一般不能看成是人工智能活動(dòng)。AI軟件：①求解的是不可直接用數(shù)學(xué)模型描述的所謂不良結(jié)構(gòu)問題（如，幾何證明、求不定積分、邏輯演算等），通常需要采用弱方法進(jìn)行搜索求解；②

AI程序中符號(hào)的內(nèi)涵不僅局限于數(shù)值計(jì)算和數(shù)據(jù)處理中的一般數(shù)據(jù)信息，應(yīng)表現(xiàn)人類進(jìn)行推理所需要的各種知識(shí)。問題求解基本原理問題求解：在給定條件下，尋求一個(gè)能解決某類問問題求解基本原理一、問題求解的基本方法二、搜索技術(shù)問題求解基本原理一、問題求解的基本方法問題求解基本原理問題求解方法：基于狀態(tài)空間的問題求解方法基于問題空間的問題求解方法基于博弈搜索的問題求解方法問題求解基本原理問題求解方法：?jiǎn)栴}實(shí)例

桌上固定了3根柱子，按1，2，3次序排例。有n個(gè)大小全不一樣大的盤子d1，…，dn

，按從小到大，小的在上的次序依次插在第一根柱子上，要把這n個(gè)盤子全部搬到第三根柱子上，每次只許搬一個(gè)，任何時(shí)候都不允許把大盤子放在小盤子上面，問該如何搬法。設(shè)n=3，該如何搬法？1 23123梵塔問題問題實(shí)例桌上固定了3根柱子，按1，2，3次序基于狀態(tài)空間的問題求解方法（1，1，1）→（1，1，2）（1，1，1）→（1，1，3）（1，1，2）→（1，3，2）。。。。。狀態(tài)合法變換規(guī)則（滿足約束條件）：狀態(tài)定義-（i大C,j中B,k小A）:設(shè)向量下標(biāo)分別表示小盤A、中盤B、大盤C；向量值分別表示盤子所在柱子的編號(hào)。狀態(tài)描述-大盤C在第i根柱子上；中號(hào)盤B在第j根柱子上，小號(hào)盤A在第k根柱子上?；跔顟B(tài)空間的問題求解方法（1，1，1）→（1，1，2）狀基于問題空間的問題求解方法問題：如何將

i柱子上的m個(gè)盤子搬到k柱子上?將i柱子上的m–1個(gè)盤子搬到j(luò)柱子上；將i柱子上的第m個(gè)盤子搬到k柱子上；將j柱子上的m–1個(gè)盤子搬到k柱子上。

問題描述：?jiǎn)栴}（a,b,c):將b柱子上的a個(gè)盤子搬到c柱子上。問題分解合法規(guī)則： （3，1，3）--〉（2，1，2）(1，1，3）（2，2，3） 。。。。。?；趩栴}空間的問題求解方法問題：如何將i柱子上的m個(gè)基于問題空間的問題求解方法基于問題空間的問題求解方法狀態(tài)空間法有關(guān)概念

狀態(tài)空間法:從問題的初始狀態(tài)出發(fā)，通過一系列的狀態(tài)變換找到目標(biāo)狀態(tài)的問題求解方法。

狀態(tài)：描述問題中事物形狀或狀況的符號(hào)或數(shù)據(jù)結(jié)構(gòu)。

狀態(tài)空間：所有狀態(tài)的全體構(gòu)成的集合；用四元組（S,S0,O,G)表示:S:非空狀態(tài)子集，S0=初始狀態(tài)（非空）。G:非空目標(biāo)狀態(tài)子集。O:操作算子集合，一個(gè)狀態(tài)合法轉(zhuǎn)換為另一個(gè)狀態(tài)的描述規(guī)則

問題求解過程：隱含求一個(gè)普通有向圖，節(jié)點(diǎn)-狀態(tài)，邊–算子

搜索空間：?jiǎn)栴}求解過程中到達(dá)過的所有狀態(tài)（節(jié)點(diǎn)）的集合。狀態(tài)空間法有關(guān)概念狀態(tài)空間法:狀態(tài)：描述問題中事物形狀或狀態(tài)空間法有關(guān)概念狀態(tài)空間、搜索空間及解徑的關(guān)系：

問題的解（解徑）：初始狀態(tài)到目標(biāo)狀態(tài)通路上的每一條規(guī)則（或狀態(tài)）構(gòu)成序列，稱為解徑。解不唯一。S0

R1S2R2Sk…..RkG問題有解：從代表初始狀態(tài)s節(jié)點(diǎn)出發(fā)，存在一條通向目標(biāo)節(jié)點(diǎn)的路徑。狀態(tài)空間法有關(guān)概念狀態(tài)空間、搜索空間及解徑的關(guān)系：?jiǎn)栴}的解問題空間法有關(guān)概念問題空間法：首先產(chǎn)生待證問題的所有子問題，而后通過解決所有子問題達(dá)到問題求解目的的方法。

問題：描述問題及其子問題的符號(hào)或數(shù)據(jù)結(jié)構(gòu)。

問題空間：初始問題以及其所有子問題的全體構(gòu)成的集合，用四元組（S,S0,F,G)

表示:

S:問題和子問題；S0

:初始問題。G:具有平凡解的本原問題集合。F:操作算子集合，用于將問題分解成其若干個(gè)子問題的描述規(guī)則問題空間法有關(guān)概念問題空間法：?jiǎn)栴}：描述問題及其子問題的符問題空間法的有關(guān)概念（2）問題空間分解過程：隱含求一個(gè)與或圖

節(jié)點(diǎn)

–問題，邊

-

分解問題的算子。

“與”節(jié)點(diǎn)：如果節(jié)點(diǎn)A有邊通向一組節(jié)點(diǎn){B1，B2，…..Bn}，問題A的解決有待于A的子問題組{B1,B2…..Bn}的全部解決，則稱A為“與”節(jié)點(diǎn)。如圖a所示。

“或”節(jié)點(diǎn)：若節(jié)點(diǎn)Ａ有邊通向一組節(jié)點(diǎn){{Ｂ１},{Ｂ2}，…{Ｂn}}，問題Ａ的解決有待于子問題Ｂ１或Ｂ2或…或Ｂn中某一個(gè)子問題的解決，則稱A為“或”節(jié)點(diǎn)。如圖b所示?！?..a:AB1B2Bn…...b:AB1B2Bn問題空間法的有關(guān)概念（2）問題空間分解過程：隱含求一個(gè)與或圖問題空間法有關(guān)概念（2）問題的解（解圖）：從代表初始問題的節(jié)點(diǎn)出發(fā)，搜索到一個(gè)完整的‘與或’子圖，圖中所有葉節(jié)點(diǎn)均滿足問題求解的結(jié)束條件。例：（C,B,Z)-〉（M,…M)重寫規(guī)則:R1:C(D,L)

R2:C(B,M)

R3:B(M,M)

R4:Z(B,B,M)

解圖問題空間法有關(guān)概念（2）問題的解（解圖）：從代表初始問題的節(jié)小結(jié)–問題求解方法比較狀態(tài)空間法問題空間法問題求解狀態(tài)變換問題分解搜索過程隱含構(gòu)建普通有向圖隱含構(gòu)建與或圖節(jié)點(diǎn)狀態(tài)問題邊狀態(tài)變換規(guī)則（算子）問題分解規(guī)則（算子）

求解解徑解圖小結(jié)–問題求解方法比較狀態(tài)空間法問題空問題求解基本原理一、問題求解的基本方法二、搜索技術(shù)（一）問題求解基本原理一、問題求解的基本方法搜索技術(shù)預(yù)備狀態(tài)空間搜索有關(guān)概念盲目搜索策略啟發(fā)式搜索策略問題求解基本原理搜索技術(shù)預(yù)備問題求解基本原理搜索策略預(yù)備盲目搜索：不考慮給定問題所具有的特定知識(shí)，系統(tǒng)按照事先確定好的某種固定順序調(diào)用規(guī)則，或是隨機(jī)地調(diào)用規(guī)則。

常用的盲目搜索算法:

深度優(yōu)先搜索策略；寬度優(yōu)先搜索策略搜索策略預(yù)備盲目搜索：常用的盲目搜索算法:搜索策略預(yù)備啟發(fā)式信息：與問題求解有關(guān)的信息和知識(shí)。由于信息的片面性和不準(zhǔn)確性，應(yīng)用啟發(fā)式信息不能百分之百地保證找到問題的解，但能提高問題求解的可能性。

啟發(fā)式信息在問題求解過程中的作用：有助于加速求解過程；有助于找到“較優(yōu)”解。

啟發(fā)式搜索策略:考慮給定問題領(lǐng)域具有的特定知識(shí)（啟發(fā)式信息），系統(tǒng)動(dòng)態(tài)地規(guī)定規(guī)則調(diào)用順序，優(yōu)先使用“較”合適的規(guī)則。搜索策略預(yù)備啟發(fā)式信息：?jiǎn)l(fā)式信息在問題求解過程中的作用：搜索策略預(yù)備常用的基于狀態(tài)圖的啟發(fā)式搜索策略:爬山搜索策略(HillClimbing)大英博物館搜索策略(BritishMuseum)啟發(fā)式圖搜索策略(A)最佳啟發(fā)式圖搜索策略(A*

)常用的基于與或圖及博弈的啟發(fā)式搜索策略：最佳啟發(fā)式與或圖搜索策略(AO*)極大極小搜索策略(Minimax)α－β剪枝搜索策略(Alpha-BetaPruning)搜索策略預(yù)備常用的基于狀態(tài)圖的啟發(fā)式搜索策略:常用的基基于狀態(tài)空間的搜索技術(shù)：

有關(guān)搜索概念

盲目搜索策略

啟發(fā)式搜索策略問題求解基本原理基于狀態(tài)空間的搜索技術(shù)：?jiǎn)栴}求解基本原理狀態(tài)空間搜索有關(guān)概念狀態(tài)圖特點(diǎn)：多條路徑通向同一節(jié)點(diǎn)。例：E狀態(tài)空間搜索有關(guān)概念狀態(tài)圖特點(diǎn)：多條路徑通向同一節(jié)點(diǎn)。例：狀態(tài)空間搜索有關(guān)概念狀態(tài)空間搜索有關(guān)概念狀態(tài)空間搜索有關(guān)概念節(jié)點(diǎn)深度：根節(jié)點(diǎn)的深度為0，其它節(jié)點(diǎn)的深度規(guī)定為其父節(jié)點(diǎn)的深度加1，即dn+1=dn+1。標(biāo)記節(jié)點(diǎn)n：利用指針把后繼節(jié)點(diǎn)連接到父節(jié)點(diǎn)n的操作。節(jié)點(diǎn)：對(duì)應(yīng)狀態(tài)圖中有關(guān)狀態(tài)的描述。擴(kuò)展節(jié)點(diǎn)n：算符（規(guī)則）作用于節(jié)點(diǎn)n生成的新節(jié)點(diǎn)稱為節(jié)點(diǎn)n的后繼節(jié)點(diǎn)。生成節(jié)點(diǎn)n的所有后繼節(jié)點(diǎn)并計(jì)算生成這些后繼節(jié)點(diǎn)所使用的花費(fèi)的過程叫做擴(kuò)展節(jié)點(diǎn)n。狀態(tài)空間搜索有關(guān)概念節(jié)點(diǎn)深度：根節(jié)點(diǎn)的深度為0，其它節(jié)點(diǎn)路徑：對(duì)于一個(gè)節(jié)點(diǎn)序列（n0,n1,…,nl,…,nk），如若每一節(jié)點(diǎn)ni-1都有一個(gè)后繼節(jié)點(diǎn)ni（i=1,2,…,k），則稱該節(jié)點(diǎn)序列為一條從節(jié)點(diǎn)n0到節(jié)點(diǎn)nk、長(zhǎng)度為k的路徑；路徑還可表示為與節(jié)點(diǎn)序列對(duì)應(yīng)的規(guī)則序列。狀態(tài)空間搜索有關(guān)概念路徑花費(fèi)：設(shè)C（ni，nj）為節(jié)點(diǎn)ni到nj這段路徑（或弧線）的花費(fèi)。一條路徑的花費(fèi)等于連接這條路徑各節(jié)點(diǎn)間所有弧線花費(fèi)值的總和。路徑ni

→nj→t的花費(fèi)值C（ni，t）可遞歸計(jì)算如下:

C（ni，t）=C(ni，nj)+C（nj，t)。路徑：對(duì)于一個(gè)節(jié)點(diǎn)序列（n0,n1,…,nl,…,基于狀態(tài)空間的盲目搜索算法:寬度優(yōu)先搜索策略深度優(yōu)先搜索策略問題求解基本原理基于狀態(tài)空間的盲目搜索算法:問題求解基本原理盲目搜索算法的符號(hào)及數(shù)據(jù)結(jié)構(gòu)

s：

初始節(jié)點(diǎn)；n：當(dāng)前節(jié)點(diǎn)。

open：

已被生成但未被擴(kuò)展的節(jié)點(diǎn)序列表；closed：已被生成且已被擴(kuò)展的節(jié)點(diǎn)序列表；{mi}={mj}∪{mk}∪{ml}：擴(kuò)展n后所得的n的后繼節(jié)點(diǎn)其中，{mk}：在OPEN表中出現(xiàn)過的待擴(kuò)展節(jié)點(diǎn)，{ml}：在CLOSED表中出現(xiàn)過的已擴(kuò)展節(jié)點(diǎn)。{mj}：第一次生成的節(jié)點(diǎn)，mj∈OPEN且mj∈CLOSED表，盲目搜索算法的符號(hào)及數(shù)據(jù)結(jié)構(gòu)s：初始節(jié)點(diǎn)寬度優(yōu)先搜索算法

open:=[S];closed:=[];whileopen≠[]do{ n:=first(open); remove(first(open));

add(n,closed)；

ifn=goalthenexit(success); expand(n)->{mi}; delete((mi)(mi∈

{mk}∨

(mi∈{ml}

)

);

add(open,mj)};exit(fail);寬度優(yōu)先搜索算法open:=[S];cl寬度優(yōu)先搜索算法

1、S,A,D2、A,D,B,D3、D,B,A,E………Open表為隊(duì)操作：先進(jìn)先出！寬度優(yōu)先搜索算法1、S,A,D2、A,D,B,DG節(jié)點(diǎn)擴(kuò)展順序?qū)挾葍?yōu)先搜索算法

G節(jié)點(diǎn)擴(kuò)展順序?qū)挾葍?yōu)先搜索算法

open:=[S];closed:=[];d=深度限制值whileopen≠[]do{ n:=first(open); remove(first(open)); add(n,closed)；

ifn=goalthenexit(success); ifdepth(n)>dthencontinue; expand(n)->{mi}; delete((mi)(mi∈{mk}∨(mi∈{ml}

));

add(mj,open)};exit(fail);深度優(yōu)先搜索算法 open:=[S];closed:=深度優(yōu)先搜索算法

1、S2、A,D3、B,

D,D………Open表為棧操作：后進(jìn)先出！4、C,

E,D深度優(yōu)先搜索算法1、S2、A,D3、B,D,D………節(jié)點(diǎn)擴(kuò)展順序深度優(yōu)先搜索算法

節(jié)點(diǎn)擴(kuò)展順序深度優(yōu)先搜索算法盲目搜索算法應(yīng)用實(shí)例-8數(shù)碼問題描述狀態(tài)：

矩陣(Sij)，其中

1≤i,j≤3，Sij∈{0,1,…,8};盲目搜索算法應(yīng)用實(shí)例-8數(shù)碼問題描述狀態(tài)：盲目搜索算法應(yīng)用實(shí)例-

合法走步規(guī)則：設(shè)(i0、j0)為空格所在行列數(shù)值，

Si0j0=0R1:ifj-1≥1thenSi0j0:=

Si0(j0-1),Si0(j0-1):=0空格左移；R2:ifi-1≥1thenSi0j0:=

S(i0-1)j0,S(i0-1)j0:=0空格上移；R3:ifj+1≤3thenSi0j0:=

Si0(j0+1),Si0(j0+1):=0空格右移；R4:ifi+1≤3thenSi0j0:=

S(i0+1)j0,S(i0+1)j0:=0空格下移。8數(shù)碼問題盲目搜索算法應(yīng)用實(shí)例-合法走步規(guī)則：設(shè)(i0、j0)為寬度優(yōu)先策略求解8數(shù)碼問題：目標(biāo)R1R2R3R2R1R2R3R2R2R3R2R4R1R3寬度優(yōu)先策略求解8數(shù)碼問題：目標(biāo)R1R2R3R2R1R2R3深度優(yōu)先策略求解8數(shù)碼問題：說明：

設(shè)規(guī)則固定使用順序：R1-左移、R2-上移、R3-右移、R4-下移；設(shè)節(jié)點(diǎn)深度限制值：6；合法的走步規(guī)則重復(fù)節(jié)點(diǎn)–造成循環(huán)深度優(yōu)先策略求解8數(shù)碼問題：說明：合法的走步規(guī)則重復(fù)節(jié)點(diǎn)問題求解基本原理基于狀態(tài)空間的啟發(fā)式搜索算法:

A算法；A*算法問題求解基本原理基于狀態(tài)空間的啟發(fā)式搜索算法:啟發(fā)式圖搜索算法假設(shè)：

f(n)=g(n)+h(n)

–任意節(jié)點(diǎn)n的評(píng)價(jià)函數(shù)：指迄今為止已找到的從初始節(jié)點(diǎn)s，到達(dá)節(jié)點(diǎn)n，再?gòu)墓?jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)t的路徑全程的最小費(fèi)用，是對(duì)f*(n)的一個(gè)估計(jì)。

h(n)

：迄今為止從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)t最佳分段路徑將要花費(fèi)的未知估計(jì)費(fèi)用，是對(duì)h*(n)的一個(gè)估計(jì)，可視為啟發(fā)式分量函數(shù)，有h(n)≥0。

g(n)

：迄今為止搜索到的從初始節(jié)點(diǎn)s到當(dāng)前節(jié)點(diǎn)n最佳路徑分段的已知費(fèi)用，是對(duì)g*(n)的一個(gè)估計(jì)。

f*(n)=g*(n)+h*(n)：從初始節(jié)點(diǎn)s出發(fā)，經(jīng)過最佳路徑上任意節(jié)點(diǎn)n，到達(dá)目標(biāo)節(jié)點(diǎn)t的最小費(fèi)用。

h*(n)：n→t最佳路徑的分段費(fèi)用。

g*(n)：s→n最佳路徑的分段費(fèi)用。

s：初始節(jié)點(diǎn)；n：當(dāng)前節(jié)點(diǎn)；t：目標(biāo)節(jié)點(diǎn)。啟發(fā)式圖搜索算法假設(shè)：f(n)=g(n)+h啟發(fā)式圖搜索算法-A算法

定義：按照f(n)=g(n)+h(n)估價(jià)函數(shù)值由小到大地排列待擴(kuò)展節(jié)點(diǎn)順序的圖搜索算法，稱為A算法。

A算法流程。A算法應(yīng)用實(shí)例:

普通有向圖A算法搜索實(shí)例；

8數(shù)碼問題A算法搜索實(shí)例。啟發(fā)式圖搜索算法-A算法定義：按照f(n)啟發(fā)式圖搜索算法-A算法算法中符號(hào)：s：初始節(jié)點(diǎn)；G：搜索圖的節(jié)點(diǎn)集合；OPEN表：已生成但尚未被擴(kuò)展的節(jié)點(diǎn)序列表；CLOSED表：已生成且已被擴(kuò)展的節(jié)點(diǎn)序列表；n：待擴(kuò)展的當(dāng)前節(jié)點(diǎn)；{mi}={mj}∪{mk}∪{ml}：擴(kuò)展n后生成的后繼節(jié)點(diǎn)其中，mj：第一次生成的節(jié)點(diǎn)，mj∈OPEN且mj∈CLOSED表，mk：在OPEN表中出現(xiàn)過的待擴(kuò)展節(jié)點(diǎn)，ml：在CLOSED表中出現(xiàn)過的已擴(kuò)展節(jié)點(diǎn)。啟發(fā)式圖搜索算法-A算法算法中符號(hào)：A算法n為目標(biāo)t?取當(dāng)前節(jié)點(diǎn)nn:=first(OPEN),從OPEN中刪除n,CLOSED:=CLOSED∪{n}初始化G:=G0∪S,OPEN:=(S)CLOSED:=(),f(S):=g(S)+h(S)OPEN=Φ

^未發(fā)現(xiàn)目標(biāo)tReturn(Fail)AyesNoyesNoBExit(Success)輸出解徑A算法n為目標(biāo)t?取當(dāng)前節(jié)點(diǎn)n初始化OPEN=Φ擴(kuò)展節(jié)點(diǎn)n：生成n的后繼節(jié)點(diǎn)；計(jì)算后繼節(jié)點(diǎn)的花費(fèi)。{mi}:=Expand(n),計(jì)算:f(n,mi):=g(n,mi)+h(mi)比較花費(fèi)，修改連接標(biāo)記

對(duì)于{mj}∈{mi}:OPEN:=OPEN∪{mj},mj->n;

對(duì)于{mk}∈{mi}:

iff(n,mk)<f(mk)thenf(mk):=f(n,mk),mk->n;

對(duì)于{ml}∈{mi}:iff(n,ml)<f(ml)thenf(ml):=f(n,ml),ml->n,OPEN:=OPEN∪{ml}將OPEN表中節(jié)點(diǎn)按f值從小到大重新排序AB擴(kuò)展節(jié)點(diǎn)n：生成n的后繼節(jié)點(diǎn)；計(jì)算后繼節(jié)點(diǎn)的花費(fèi)。比較花費(fèi)，啟發(fā)式最佳圖搜索算法-A*算法A*算法定義：

若將A算法中評(píng)價(jià)函數(shù)f(n)的啟發(fā)式分量函數(shù)h（n）的值限制在h*（n）的下界范圍內(nèi)，亦即對(duì)所有節(jié)點(diǎn)n，都滿足h（n）≤h*（n），則稱此時(shí)的A算法為A*算法。

A*算法作用：?jiǎn)栴}有解時(shí)，A*算法一定能夠找到從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的最佳解徑。啟發(fā)式最佳圖搜索算法-A*算法A*算法定義：A*算法信息性定理：有兩個(gè)A*算法A1和A2,若A2比A1有較多的啟發(fā)式信息（即對(duì)所有非目標(biāo)節(jié)點(diǎn)均有：

h1（n）≤h2（n）≤h*（n）），則在具有一條從s到t的隱含狀態(tài)圖上，搜索結(jié)束時(shí)，由A2擴(kuò)展的每一個(gè)節(jié)點(diǎn)，也必定由A1所擴(kuò)展，即A1擴(kuò)展的節(jié)點(diǎn)數(shù)至少和A2一樣多。啟發(fā)式最佳圖搜索算法-A*算法A*算法應(yīng)用驗(yàn)證:

8數(shù)碼問題A*算法搜索實(shí)例。信息性定理：?jiǎn)l(fā)式最佳圖搜索算法-A*算法A*算法8數(shù)碼問題搜索策略比較：

寬度優(yōu)先A算法A*算法8數(shù)碼問題搜索策略比較：寬度優(yōu)先A算法小結(jié)啟發(fā)式搜索策略g:

考慮當(dāng)前路徑已經(jīng)花費(fèi)的費(fèi)用，及時(shí)拋棄已經(jīng)經(jīng)過的花費(fèi)太大且距目標(biāo)仍遠(yuǎn)的路徑;h:

估計(jì)當(dāng)前路徑上節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)還需要的費(fèi)用，引導(dǎo)搜索向最有希望的路徑前進(jìn)。

A算法：定義估計(jì)函數(shù)：f=g+h；

A*算法：定義估計(jì)函數(shù)：f=g+h； 滿足h（n）≤h*（n）。小結(jié)啟發(fā)式搜索策略g:h:A算法：定義估計(jì)函數(shù)：f程序?qū)崿F(xiàn)寬度優(yōu)先法和深度優(yōu)先法求解High-waymap問題，給出求解過程（Open，Closed內(nèi)容），標(biāo)出解徑。作業(yè):作業(yè):給定兩個(gè)油桶,一個(gè)可裝4公斤油,一個(gè)可裝3公斤油,油桶上無任何度量標(biāo)記。問：怎樣才能使4公斤油桶里恰好只裝2公斤油？ 設(shè)狀態(tài)定義：(x,y)，其中， x：4公斤油桶中實(shí)際裝油公斤數(shù)； y：3公斤油桶中實(shí)際裝油公斤數(shù)。 問題表示：(0,0)-〉(2,y) 要求定義合法的裝油規(guī)則，利用盲目搜索策略畫出狀態(tài)圖。作業(yè):給定兩個(gè)油桶,一個(gè)可裝4公斤油,一個(gè)可裝3公斤油,油人工智能(問題求解基本原理及搜索技術(shù)

)人工智能問題求解基本原理問題求解：在給定條件下，尋求一個(gè)能解決某類問題且能在有限步驟內(nèi)完成的算法。

問題求解特征：傳統(tǒng)軟件：

①求解的問題是能夠用數(shù)學(xué)精確描述的良結(jié)構(gòu)的問題（如，解方程）；②計(jì)算機(jī)執(zhí)行的繁雜的統(tǒng)計(jì)計(jì)算任務(wù)一般不能看成是人工智能活動(dòng)。AI軟件：①求解的是不可直接用數(shù)學(xué)模型描述的所謂不良結(jié)構(gòu)問題（如，幾何證明、求不定積分、邏輯演算等），通常需要采用弱方法進(jìn)行搜索求解；②

AI程序中符號(hào)的內(nèi)涵不僅局限于數(shù)值計(jì)算和數(shù)據(jù)處理中的一般數(shù)據(jù)信息，應(yīng)表現(xiàn)人類進(jìn)行推理所需要的各種知識(shí)。問題求解基本原理問題求解：在給定條件下，尋求一個(gè)能解決某類問問題求解基本原理一、問題求解的基本方法二、搜索技術(shù)問題求解基本原理一、問題求解的基本方法問題求解基本原理問題求解方法：基于狀態(tài)空間的問題求解方法基于問題空間的問題求解方法基于博弈搜索的問題求解方法問題求解基本原理問題求解方法：?jiǎn)栴}實(shí)例

桌上固定了3根柱子，按1，2，3次序排例。有n個(gè)大小全不一樣大的盤子d1，…，dn

，按從小到大，小的在上的次序依次插在第一根柱子上，要把這n個(gè)盤子全部搬到第三根柱子上，每次只許搬一個(gè)，任何時(shí)候都不允許把大盤子放在小盤子上面，問該如何搬法。設(shè)n=3，該如何搬法？1 23123梵塔問題問題實(shí)例桌上固定了3根柱子，按1，2，3次序基于狀態(tài)空間的問題求解方法（1，1，1）→（1，1，2）（1，1，1）→（1，1，3）（1，1，2）→（1，3，2）。。。。。狀態(tài)合法變換規(guī)則（滿足約束條件）：狀態(tài)定義-（i大C,j中B,k小A）:設(shè)向量下標(biāo)分別表示小盤A、中盤B、大盤C；向量值分別表示盤子所在柱子的編號(hào)。狀態(tài)描述-大盤C在第i根柱子上；中號(hào)盤B在第j根柱子上，小號(hào)盤A在第k根柱子上。基于狀態(tài)空間的問題求解方法（1，1，1）→（1，1，2）狀基于問題空間的問題求解方法問題：如何將

i柱子上的m個(gè)盤子搬到k柱子上?將i柱子上的m–1個(gè)盤子搬到j(luò)柱子上；將i柱子上的第m個(gè)盤子搬到k柱子上；將j柱子上的m–1個(gè)盤子搬到k柱子上。

問題描述：?jiǎn)栴}（a,b,c):將b柱子上的a個(gè)盤子搬到c柱子上。問題分解合法規(guī)則： （3，1，3）--〉（2，1，2）(1，1，3）（2，2，3） 。。。。。。基于問題空間的問題求解方法問題：如何將i柱子上的m個(gè)基于問題空間的問題求解方法基于問題空間的問題求解方法狀態(tài)空間法有關(guān)概念

狀態(tài)空間法:從問題的初始狀態(tài)出發(fā)，通過一系列的狀態(tài)變換找到目標(biāo)狀態(tài)的問題求解方法。

狀態(tài)：描述問題中事物形狀或狀況的符號(hào)或數(shù)據(jù)結(jié)構(gòu)。

狀態(tài)空間：所有狀態(tài)的全體構(gòu)成的集合；用四元組（S,S0,O,G)表示:S:非空狀態(tài)子集，S0=初始狀態(tài)（非空）。G:非空目標(biāo)狀態(tài)子集。O:操作算子集合，一個(gè)狀態(tài)合法轉(zhuǎn)換為另一個(gè)狀態(tài)的描述規(guī)則

問題求解過程：隱含求一個(gè)普通有向圖，節(jié)點(diǎn)-狀態(tài)，邊–算子

搜索空間：?jiǎn)栴}求解過程中到達(dá)過的所有狀態(tài)（節(jié)點(diǎn)）的集合。狀態(tài)空間法有關(guān)概念狀態(tài)空間法:狀態(tài)：描述問題中事物形狀或狀態(tài)空間法有關(guān)概念狀態(tài)空間、搜索空間及解徑的關(guān)系：

問題的解（解徑）：初始狀態(tài)到目標(biāo)狀態(tài)通路上的每一條規(guī)則（或狀態(tài)）構(gòu)成序列，稱為解徑。解不唯一。S0

R1S2R2Sk…..RkG問題有解：從代表初始狀態(tài)s節(jié)點(diǎn)出發(fā)，存在一條通向目標(biāo)節(jié)點(diǎn)的路徑。狀態(tài)空間法有關(guān)概念狀態(tài)空間、搜索空間及解徑的關(guān)系：?jiǎn)栴}的解問題空間法有關(guān)概念問題空間法：首先產(chǎn)生待證問題的所有子問題，而后通過解決所有子問題達(dá)到問題求解目的的方法。

問題：描述問題及其子問題的符號(hào)或數(shù)據(jù)結(jié)構(gòu)。

問題空間：初始問題以及其所有子問題的全體構(gòu)成的集合，用四元組（S,S0,F,G)

表示:

S:問題和子問題；S0

:初始問題。G:具有平凡解的本原問題集合。F:操作算子集合，用于將問題分解成其若干個(gè)子問題的描述規(guī)則問題空間法有關(guān)概念問題空間法：?jiǎn)栴}：描述問題及其子問題的符問題空間法的有關(guān)概念（2）問題空間分解過程：隱含求一個(gè)與或圖

節(jié)點(diǎn)

–問題，邊

-

分解問題的算子。

“與”節(jié)點(diǎn)：如果節(jié)點(diǎn)A有邊通向一組節(jié)點(diǎn){B1，B2，…..Bn}，問題A的解決有待于A的子問題組{B1,B2…..Bn}的全部解決，則稱A為“與”節(jié)點(diǎn)。如圖a所示。

“或”節(jié)點(diǎn)：若節(jié)點(diǎn)Ａ有邊通向一組節(jié)點(diǎn){{Ｂ１},{Ｂ2}，…{Ｂn}}，問題Ａ的解決有待于子問題Ｂ１或Ｂ2或…或Ｂn中某一個(gè)子問題的解決，則稱A為“或”節(jié)點(diǎn)。如圖b所示?！?..a:AB1B2Bn…...b:AB1B2Bn問題空間法的有關(guān)概念（2）問題空間分解過程：隱含求一個(gè)與或圖問題空間法有關(guān)概念（2）問題的解（解圖）：從代表初始問題的節(jié)點(diǎn)出發(fā)，搜索到一個(gè)完整的‘與或’子圖，圖中所有葉節(jié)點(diǎn)均滿足問題求解的結(jié)束條件。例：（C,B,Z)-〉（M,…M)重寫規(guī)則:R1:C(D,L)

R2:C(B,M)

R3:B(M,M)

R4:Z(B,B,M)

解圖問題空間法有關(guān)概念（2）問題的解（解圖）：從代表初始問題的節(jié)小結(jié)–問題求解方法比較狀態(tài)空間法問題空間法問題求解狀態(tài)變換問題分解搜索過程隱含構(gòu)建普通有向圖隱含構(gòu)建與或圖節(jié)點(diǎn)狀態(tài)問題邊狀態(tài)變換規(guī)則（算子）問題分解規(guī)則（算子）

求解解徑解圖小結(jié)–問題求解方法比較狀態(tài)空間法問題空問題求解基本原理一、問題求解的基本方法二、搜索技術(shù)（一）問題求解基本原理一、問題求解的基本方法搜索技術(shù)預(yù)備狀態(tài)空間搜索有關(guān)概念盲目搜索策略啟發(fā)式搜索策略問題求解基本原理搜索技術(shù)預(yù)備問題求解基本原理搜索策略預(yù)備盲目搜索：不考慮給定問題所具有的特定知識(shí)，系統(tǒng)按照事先確定好的某種固定順序調(diào)用規(guī)則，或是隨機(jī)地調(diào)用規(guī)則。

常用的盲目搜索算法:

深度優(yōu)先搜索策略；寬度優(yōu)先搜索策略搜索策略預(yù)備盲目搜索：常用的盲目搜索算法:搜索策略預(yù)備啟發(fā)式信息：與問題求解有關(guān)的信息和知識(shí)。由于信息的片面性和不準(zhǔn)確性，應(yīng)用啟發(fā)式信息不能百分之百地保證找到問題的解，但能提高問題求解的可能性。

啟發(fā)式信息在問題求解過程中的作用：有助于加速求解過程；有助于找到“較優(yōu)”解。

啟發(fā)式搜索策略:考慮給定問題領(lǐng)域具有的特定知識(shí)（啟發(fā)式信息），系統(tǒng)動(dòng)態(tài)地規(guī)定規(guī)則調(diào)用順序，優(yōu)先使用“較”合適的規(guī)則。搜索策略預(yù)備啟發(fā)式信息：?jiǎn)l(fā)式信息在問題求解過程中的作用：搜索策略預(yù)備常用的基于狀態(tài)圖的啟發(fā)式搜索策略:爬山搜索策略(HillClimbing)大英博物館搜索策略(BritishMuseum)啟發(fā)式圖搜索策略(A)最佳啟發(fā)式圖搜索策略(A*

)常用的基于與或圖及博弈的啟發(fā)式搜索策略：最佳啟發(fā)式與或圖搜索策略(AO*)極大極小搜索策略(Minimax)α－β剪枝搜索策略(Alpha-BetaPruning)搜索策略預(yù)備常用的基于狀態(tài)圖的啟發(fā)式搜索策略:常用的基基于狀態(tài)空間的搜索技術(shù)：

有關(guān)搜索概念

盲目搜索策略

啟發(fā)式搜索策略問題求解基本原理基于狀態(tài)空間的搜索技術(shù)：?jiǎn)栴}求解基本原理狀態(tài)空間搜索有關(guān)概念狀態(tài)圖特點(diǎn)：多條路徑通向同一節(jié)點(diǎn)。例：E狀態(tài)空間搜索有關(guān)概念狀態(tài)圖特點(diǎn)：多條路徑通向同一節(jié)點(diǎn)。例：狀態(tài)空間搜索有關(guān)概念狀態(tài)空間搜索有關(guān)概念狀態(tài)空間搜索有關(guān)概念節(jié)點(diǎn)深度：根節(jié)點(diǎn)的深度為0，其它節(jié)點(diǎn)的深度規(guī)定為其父節(jié)點(diǎn)的深度加1，即dn+1=dn+1。標(biāo)記節(jié)點(diǎn)n：利用指針把后繼節(jié)點(diǎn)連接到父節(jié)點(diǎn)n的操作。節(jié)點(diǎn)：對(duì)應(yīng)狀態(tài)圖中有關(guān)狀態(tài)的描述。擴(kuò)展節(jié)點(diǎn)n：算符（規(guī)則）作用于節(jié)點(diǎn)n生成的新節(jié)點(diǎn)稱為節(jié)點(diǎn)n的后繼節(jié)點(diǎn)。生成節(jié)點(diǎn)n的所有后繼節(jié)點(diǎn)并計(jì)算生成這些后繼節(jié)點(diǎn)所使用的花費(fèi)的過程叫做擴(kuò)展節(jié)點(diǎn)n。狀態(tài)空間搜索有關(guān)概念節(jié)點(diǎn)深度：根節(jié)點(diǎn)的深度為0，其它節(jié)點(diǎn)路徑：對(duì)于一個(gè)節(jié)點(diǎn)序列（n0,n1,…,nl,…,nk），如若每一節(jié)點(diǎn)ni-1都有一個(gè)后繼節(jié)點(diǎn)ni（i=1,2,…,k），則稱該節(jié)點(diǎn)序列為一條從節(jié)點(diǎn)n0到節(jié)點(diǎn)nk、長(zhǎng)度為k的路徑；路徑還可表示為與節(jié)點(diǎn)序列對(duì)應(yīng)的規(guī)則序列。狀態(tài)空間搜索有關(guān)概念路徑花費(fèi)：設(shè)C（ni，nj）為節(jié)點(diǎn)ni到nj這段路徑（或弧線）的花費(fèi)。一條路徑的花費(fèi)等于連接這條路徑各節(jié)點(diǎn)間所有弧線花費(fèi)值的總和。路徑ni

→nj→t的花費(fèi)值C（ni，t）可遞歸計(jì)算如下:

C（ni，t）=C(ni，nj)+C（nj，t)。路徑：對(duì)于一個(gè)節(jié)點(diǎn)序列（n0,n1,…,nl,…,基于狀態(tài)空間的盲目搜索算法:寬度優(yōu)先搜索策略深度優(yōu)先搜索策略問題求解基本原理基于狀態(tài)空間的盲目搜索算法:問題求解基本原理盲目搜索算法的符號(hào)及數(shù)據(jù)結(jié)構(gòu)

s：

初始節(jié)點(diǎn)；n：當(dāng)前節(jié)點(diǎn)。

open：

已被生成但未被擴(kuò)展的節(jié)點(diǎn)序列表；closed：已被生成且已被擴(kuò)展的節(jié)點(diǎn)序列表；{mi}={mj}∪{mk}∪{ml}：擴(kuò)展n后所得的n的后繼節(jié)點(diǎn)其中，{mk}：在OPEN表中出現(xiàn)過的待擴(kuò)展節(jié)點(diǎn)，{ml}：在CLOSED表中出現(xiàn)過的已擴(kuò)展節(jié)點(diǎn)。{mj}：第一次生成的節(jié)點(diǎn)，mj∈OPEN且mj∈CLOSED表，盲目搜索算法的符號(hào)及數(shù)據(jù)結(jié)構(gòu)s：初始節(jié)點(diǎn)寬度優(yōu)先搜索算法

open:=[S];closed:=[];whileopen≠[]do{ n:=first(open); remove(first(open));

add(n,closed)；

ifn=goalthenexit(success); expand(n)->{mi}; delete((mi)(mi∈

{mk}∨

(mi∈{ml}

)

);

add(open,mj)};exit(fail);寬度優(yōu)先搜索算法open:=[S];cl寬度優(yōu)先搜索算法

1、S,A,D2、A,D,B,D3、D,B,A,E………Open表為隊(duì)操作：先進(jìn)先出！寬度優(yōu)先搜索算法1、S,A,D2、A,D,B,DG節(jié)點(diǎn)擴(kuò)展順序?qū)挾葍?yōu)先搜索算法

G節(jié)點(diǎn)擴(kuò)展順序?qū)挾葍?yōu)先搜索算法

open:=[S];closed:=[];d=深度限制值whileopen≠[]do{ n:=first(open); remove(first(open)); add(n,closed)；

ifn=goalthenexit(success); ifdepth(n)>dthencontinue; expand(n)->{mi}; delete((mi)(mi∈{mk}∨(mi∈{ml}

));

add(mj,open)};exit(fail);深度優(yōu)先搜索算法 open:=[S];closed:=深度優(yōu)先搜索算法

1、S2、A,D3、B,

D,D………Open表為棧操作：后進(jìn)先出！4、C,

E,D深度優(yōu)先搜索算法1、S2、A,D3、B,D,D………節(jié)點(diǎn)擴(kuò)展順序深度優(yōu)先搜索算法

節(jié)點(diǎn)擴(kuò)展順序深度優(yōu)先搜索算法盲目搜索算法應(yīng)用實(shí)例-8數(shù)碼問題描述狀態(tài)：

矩陣(Sij)，其中

1≤i,j≤3，Sij∈{0,1,…,8};盲目搜索算法應(yīng)用實(shí)例-8數(shù)碼問題描述狀態(tài)：盲目搜索算法應(yīng)用實(shí)例-

合法走步規(guī)則：設(shè)(i0、j0)為空格所在行列數(shù)值，

Si0j0=0R1:ifj-1≥1thenSi0j0:=

Si0(j0-1),Si0(j0-1):=0空格左移；R2:ifi-1≥1thenSi0j0:=

S(i0-1)j0,S(i0-1)j0:=0空格上移；R3:ifj+1≤3thenSi0j0:=

Si0(j0+1),Si0(j0+1):=0空格右移；R4:ifi+1≤3thenSi0j0:=

S(i0+1)j0,S(i0+1)j0:=0空格下移。8數(shù)碼問題盲目搜索算法應(yīng)用實(shí)例-合法走步規(guī)則：設(shè)(i0、j0)為寬度優(yōu)先策略求解8數(shù)碼問題：目標(biāo)R1R2R3R2R1R2R3R2R2R3R2R4R1R3寬度優(yōu)先策略求解8數(shù)碼問題：目標(biāo)R1R2R3R2R1R2R3深度優(yōu)先策略求解8數(shù)碼問題：說明：

設(shè)規(guī)則固定使用順序：R1-左移、R2-上移、R3-右移、R4-下移；設(shè)節(jié)點(diǎn)深度限制值：6；合法的走步規(guī)則重復(fù)節(jié)點(diǎn)–造成循環(huán)深度優(yōu)先策略求解8數(shù)碼問題：說明：合法的走步規(guī)則重復(fù)節(jié)點(diǎn)問題求解基本原理基于狀態(tài)空間的啟發(fā)式搜索算法:

A算法；A*算法問題求解基本原理基于狀態(tài)空間的啟發(fā)式搜索算法:啟發(fā)式圖搜索算法假設(shè)：

f(n)=g(n)+h(n)

–任意節(jié)點(diǎn)n的評(píng)價(jià)函數(shù)：指迄今為止已找到的從初始節(jié)點(diǎn)s，到達(dá)節(jié)點(diǎn)n，再?gòu)墓?jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)t的路徑全程的最小費(fèi)用，是對(duì)f*(n)的一個(gè)估計(jì)。

h(n)

：迄今為止從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)t最佳分段路徑將要花費(fèi)的未知估計(jì)費(fèi)用，是對(duì)h*(n)的一個(gè)估計(jì)，可視為啟發(fā)式分量函數(shù)，有h(n)≥0。

g(n)

：迄今為止搜索到的從初始節(jié)點(diǎn)s到當(dāng)前節(jié)點(diǎn)n最佳路徑分段的已知費(fèi)用，是對(duì)g*(n)的一個(gè)估計(jì)。

f*(n)=g*(n)+h*(n)：從初始節(jié)點(diǎn)s出發(fā)，經(jīng)過最佳路徑上任意節(jié)點(diǎn)n，到達(dá)目標(biāo)節(jié)點(diǎn)t的最小費(fèi)用。

h*(n)：n→t最佳路徑的分段費(fèi)用。

g*(n)：s→n最佳路徑的分段費(fèi)用。

s：初始節(jié)點(diǎn)；n：當(dāng)前節(jié)點(diǎn)；t：目標(biāo)節(jié)點(diǎn)。啟發(fā)式圖搜索算法假設(shè)：f(n)=g(n)+h啟發(fā)式圖搜索算法-A算法

定義：按照f(n)=g(n)+h(n)估價(jià)函數(shù)值由小到大地排列待擴(kuò)展節(jié)點(diǎn)順序的圖搜索算法，稱為A算法。

A算法流程。A算法應(yīng)用實(shí)例:

普通有向圖A算法搜索實(shí)例；

8數(shù)碼問題A算法搜索實(shí)例。啟發(fā)式圖搜索算法-A算法定義：按照f(n)啟發(fā)式圖搜索算法-A算法算法中符號(hào)：s：初始節(jié)點(diǎn)；G：搜索圖的節(jié)