第三章確定性推理

1、1 1什么是搜索什么是搜索(1)(1)搜索的引起搜索的引起: :人工智能要解決的問題大部分是人工智能要解決的問題大部分是結(jié)構(gòu)結(jié)構(gòu) 不良或非結(jié)構(gòu)化不良或非結(jié)構(gòu)化的問題的問題, ,而對(duì)這樣的問題一般不存在而對(duì)這樣的問題一般不存在 成熟的求解算法成熟的求解算法, ,只能用已有的知識(shí)一步步地摸索著只能用已有的知識(shí)一步步地摸索著前進(jìn)前進(jìn)(2)(2)搜索搜索: :根據(jù)問題的實(shí)際情況不斷尋找可利用的知識(shí)根據(jù)問題的實(shí)際情況不斷尋找可利用的知識(shí), ,從而構(gòu)成一條代價(jià)較少的推理路線從而構(gòu)成一條代價(jià)較少的推理路線, ,使問題得到圓滿使問題得到圓滿解決的過程解決的過程. .(3)(3)搜索分為搜索分為 盲目搜索盲目搜

2、索 啟發(fā)式搜索啟發(fā)式搜索( (好好) )盲目搜索盲目搜索:是按預(yù)定的控制策略進(jìn)行搜索,在搜索的過程獲得的中間信息不用來改進(jìn)控制策略,搜索具有盲目性,效率不高,不便于復(fù)雜問題的求解.啟發(fā)式搜索啟發(fā)式搜索:在搜索中加入了與問題有關(guān)的啟發(fā)式信息,用于指導(dǎo)搜索朝著最有希望的方向前進(jìn),加速問題的求解過程并找到最優(yōu)解.2狀態(tài)空間表示法狀態(tài)空間表示法狀態(tài)空間表示法是由”狀態(tài)”和”算符”來表示問題的一種方法.”狀態(tài)”用以描述問題求解過程中不同時(shí)刻的狀態(tài);”算符”表示對(duì)狀態(tài)的操作,算符的每一次使用就使問題由一種狀態(tài)變換為另一種狀態(tài).(1)狀態(tài)表示:描述問題求解過程中任一時(shí)刻狀況的數(shù)據(jù)結(jié)構(gòu),一般用一組變量的有序組

3、合表示: SK=(SK0,SK1) 當(dāng)每一個(gè)分量確定時(shí),就得到一個(gè)具體的狀態(tài)(2)算符:引起狀態(tài)中某些分量發(fā)生變化,從而使問題由一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)的操作稱為算符.(3)狀態(tài)空間:由問題的全部狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)空間,一般用一個(gè)三元組表示(S.F.G)初始狀態(tài)集合 算符集合 目標(biāo)狀態(tài)集合(4)狀態(tài)空間的圖示形式稱為狀態(tài)空間圖,節(jié)點(diǎn)表示狀態(tài),有向邊(弧)表示算符3狀態(tài)空間的一般搜索過程(1)基本思想 初始狀態(tài)作為當(dāng)前狀態(tài) 選擇適用的算符對(duì)其進(jìn)行操作,生成一組子狀態(tài) 檢查目標(biāo)狀態(tài)是否在其中出現(xiàn),若出現(xiàn),搜索成功,找到問題的解,若不出現(xiàn),按某種搜索策略從已生成的狀態(tài)中再選一

4、個(gè)狀態(tài)作為當(dāng)前狀態(tài) 重復(fù) ,直到目標(biāo)狀態(tài)出現(xiàn),或無可用的算符為止.(2)搜索過程 OPEN表:用于存放剛生成的節(jié)點(diǎn) CLOSED表:用于存放將要擴(kuò)展或已擴(kuò)展的節(jié)點(diǎn) G G：搜索圖，動(dòng)態(tài)變化：搜索圖，動(dòng)態(tài)變化把初始節(jié)點(diǎn)S0放入OPEN表,并建立只含S0的圖,記為G OPEN:=S0, G:=G0(G0=S0)檢查OPEN表是否為空,若為空則問題無解,退出 LOOP: IF(OPEN)=( ) THEN EXIT(FALL)把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入CLOSED表,記該節(jié)點(diǎn)為節(jié)點(diǎn)n n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED)觀察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)

5、,若是,則求得問題的解,退出 IF GOAL(n) THEN EXIT(SUCCESS)擴(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中. EXPAND(n)M(mi),G:=ADD(mi,G) 針對(duì)M中子節(jié)點(diǎn)的不同情況,分別進(jìn)行如下處理 對(duì)于那些未曾在G中出現(xiàn)過的M成員設(shè)置一個(gè)指向父節(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)的指針按某種搜索策略對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序轉(zhuǎn)第步

6、 GO LOOP擴(kuò)展節(jié)點(diǎn)1,生成單一后繼節(jié)點(diǎn)2,2已有父節(jié)點(diǎn)3,從S0-2的代價(jià)為4,從S0-2的代價(jià)為2,后者代價(jià)小,修改節(jié)點(diǎn)2指向父節(jié)點(diǎn)的指針擴(kuò)展節(jié)點(diǎn)4,節(jié)點(diǎn)4是節(jié)點(diǎn)6的后繼節(jié)點(diǎn), S0-4的代價(jià)為4,從S0-4的代價(jià)為3, 修改節(jié)點(diǎn)4的父節(jié)點(diǎn)代表已擴(kuò)展節(jié)點(diǎn)代表已擴(kuò)展節(jié)點(diǎn), ,位于位于CLOSEDCLOSED表上表上代表未擴(kuò)展節(jié)點(diǎn)代表未擴(kuò)展節(jié)點(diǎn), ,位于位于OPENOPEN表上表上有向邊旁的箭頭是指向父節(jié)點(diǎn)的指有向邊旁的箭頭是指向父節(jié)點(diǎn)的指針針, ,每邊代價(jià)為每邊代價(jià)為1 11S026453開始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)

7、嗎？把n的后繼節(jié)點(diǎn)放入OPEN表中，提供返回節(jié)點(diǎn)n的指針修改指針方向重排OPEN表失敗成功是是否否 若對(duì)若對(duì)OPENOPEN表中節(jié)點(diǎn)的排序不使用關(guān)于問題的探表中節(jié)點(diǎn)的排序不使用關(guān)于問題的探索性信息，則必須任意規(guī)定一種排序方式，所得到索性信息，則必須任意規(guī)定一種排序方式，所得到 的搜索過程叫作無信息搜索，也叫盲目搜索。的搜索過程叫作無信息搜索，也叫盲目搜索。 一般有兩種無信息的圖搜索過程：深度優(yōu)先搜一般有兩種無信息的圖搜索過程：深度優(yōu)先搜索與寬度優(yōu)先搜索索與寬度優(yōu)先搜索 在人工智能中，一般說來人們對(duì)無信息的過程在人工智能中，一般說來人們對(duì)無信息的過程不感興趣不感興趣（1 1）基本思想：從基本思想

8、：從S S0 0開始，逐層地對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展，考察它開始，逐層地對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展，考察它是否為目標(biāo)節(jié)點(diǎn)，在第是否為目標(biāo)節(jié)點(diǎn)，在第n n層的節(jié)點(diǎn)沒有全部擴(kuò)展并考察之前，層的節(jié)點(diǎn)沒有全部擴(kuò)展并考察之前，不對(duì)第不對(duì)第n+1n+1層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。OpenOpen表中的節(jié)點(diǎn)總是按進(jìn)入表中的節(jié)點(diǎn)總是按進(jìn)入的先后順序排列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。的先后順序排列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。（2 2）搜索過程搜索過程 OPEN:=S OPEN:=S0 0 LOOP: IF(OPEN)=( ) THEN EXIT(FALL) LOOP: IF(OPEN)=( ) TH

9、EN EXIT(FALL) n:=FIRST(OPEN),REMOVE( n:=FIRST(OPEN),REMOVE(n,OPENn,OPEN),ADD(),ADD(n,CLOSEDn,CLOSED) ) IF GOAL(n) THEN EXIT(SUCCESS) IF GOAL(n) THEN EXIT(SUCCESS) IF EXPAND(n)=( ) GO LOOPIF EXPAND(n)=( ) GO LOOP EXPAND(n)M(m EXPAND(n)M(mi i),ADD(),ADD(mmi i,OPEN,OPEN), m), mi in;n; GO LOOP GO LOOP12

10、/26/202112一個(gè)簡單二叉樹的一個(gè)簡單二叉樹的寬度優(yōu)先搜索寬度優(yōu)先搜索過程過程ABFCGEDABFCGEDABFCGEDABFCGED在每一個(gè)階段，下一個(gè)要擴(kuò)展的節(jié)點(diǎn)由箭頭指示在每一個(gè)階段，下一個(gè)要擴(kuò)展的節(jié)點(diǎn)由箭頭指示出來。出來。28314765123847652 8 31 47 6 52 3 41 8 7 6 51 2 3 8 47 6 52 8 37 1 46 58 32 1 47 6 52 8 31 6 7 5 42 8 3 6 41 7 5 2 8 1 4 37 6 52 8 31 4 5 7 6 2 3 1 8 47 6 5 2 31 8 47 6 52 8 37 1 4 6

11、5 8 32 1 47 6 52 8 31 6 47 5 2 8 31 6 4 7 52 8 31 4 57 6 2 8 1 4 37 6 52 8 31 6 47 52 8 31 4 7 6 5 2 3 1 8 4 7 6 52 8 3 1 47 6 51 2 3 8 4 7 6 52 8 37 1 46 5 2 8 37 46 1 58 1 32 47 6 58 3 2 1 4 7 6 51234567891011121314151617181920212223242526（1）基本思想：從S0開始，在其子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，若不是目標(biāo)節(jié)點(diǎn)，則再在該子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，一

12、直如此向下搜索。當(dāng)?shù)竭_(dá)某個(gè)子節(jié)點(diǎn)，且該子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)又不能繼續(xù)擴(kuò)展時(shí)，才選擇兄弟節(jié)點(diǎn)進(jìn)行考察。（2）搜索過程 OPEN:=S0 LOOP: IF(OPEN)=( ) THEN EXIT(FALL) n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED) IF GOAL(n) THEN EXIT(SUCCESS) IF EXPAND(n)=( ) GO LOOP EXPAND(n)M(mi),ADD(mi,OPEN), min; GO LOOP12/26/202116ABFCGEDHIJ K L M N OABFCGEDHIJ K L M N OOABFCG

13、EDHIJ K L M NABFCGEDHIJ K L M N OABFCGEDHIJ K L M N OABFCGEDHIJ K L M N O深深度優(yōu)先搜索度優(yōu)先搜索過程過程等代價(jià)搜索：寬度優(yōu)先搜索可被推廣用來解決尋找從起始狀態(tài)至目標(biāo)狀態(tài)的具有最小代價(jià)的路徑問題，這種推廣了的寬度優(yōu)先搜索稱等代價(jià)搜索代價(jià)樹：邊上標(biāo)有代價(jià)或費(fèi)用若i的后繼節(jié)點(diǎn)是j,則l i與j之間的弧線記為c(i,j)l S到i的路徑代價(jià)記為g(i)l g(j)=g(i)+ c(i,j)基本思想：每次從OPEN表中選擇節(jié)點(diǎn)往CLOSED表傳送時(shí)，總是選擇其代價(jià)為最小的節(jié)點(diǎn)搜索過程 OPEN:=S0,g(S0):=0 LOOP:

14、 IF OPEN=( ) THEN EXIT(FALL) n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED) IF GOAL(n) THEN EXIT(SUCCESS) IF EXPAND(n)=( ) GO LOOP IF EXPAND(n)Mmi,ADD(mi,OPEN) min; g(j):=g(i)+ c(i,j), (OPEN) , GO LOOP例：五城市間的交通間路圖，A是出發(fā)地，E是目的地，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示，求從A到E的最小路費(fèi)用交通路線方法：從初始節(jié)A 開始，把與它直接相鄰的節(jié)點(diǎn)作為它的子節(jié)點(diǎn)若一個(gè)節(jié)點(diǎn)已作為某節(jié)點(diǎn)的

15、直系先輩節(jié)點(diǎn)時(shí)，就不能再作為這個(gè)節(jié)點(diǎn)的子節(jié)圖中除起始節(jié)點(diǎn)外，其它節(jié)點(diǎn)都可能要在代價(jià)樹中出現(xiàn)多次，為區(qū)別之，用下標(biāo)1，2，3等標(biāo)出ABCDE443325AC1C2B1D1E2E1B2E4E3D2333244455交通代價(jià)樹A-C1-D1-E2=8A-C-D-E 無信息的搜索方式需要產(chǎn)生大量的節(jié)點(diǎn)才能找到無信息的搜索方式需要產(chǎn)生大量的節(jié)點(diǎn)才能找到解路徑。這些節(jié)點(diǎn)都需要在內(nèi)存中保存起來。由此可解路徑。這些節(jié)點(diǎn)都需要在內(nèi)存中保存起來。由此可見無信息搜索方式所需存儲(chǔ)空間是相當(dāng)大的。而實(shí)際見無信息搜索方式所需存儲(chǔ)空間是相當(dāng)大的。而實(shí)際上計(jì)算機(jī)所能提供的存儲(chǔ)總是有限的，因此我們須尋上計(jì)算機(jī)所能提供的存儲(chǔ)總是

16、有限的，因此我們須尋找效率更高的搜索方法。找效率更高的搜索方法。 啟發(fā)式信息用在對(duì)啟發(fā)式信息用在對(duì)OPENOPEN表中的節(jié)點(diǎn)進(jìn)行排序，表中的節(jié)點(diǎn)進(jìn)行排序，把最有希望的節(jié)點(diǎn)排在最前面，使搜索圖沿著有利于把最有希望的節(jié)點(diǎn)排在最前面，使搜索圖沿著有利于獲得解的方向擴(kuò)展。獲得解的方向擴(kuò)展。 啟發(fā)式搜索：啟發(fā)式搜索：使用啟發(fā)信息指導(dǎo)的搜索過程叫做啟使用啟發(fā)信息指導(dǎo)的搜索過程叫做啟 發(fā)式搜索。發(fā)式搜索。估價(jià)函數(shù)f(i)的定義：從初始節(jié)點(diǎn)s0出發(fā)，約束經(jīng)過節(jié)點(diǎn)i到達(dá)目標(biāo)節(jié)點(diǎn)中的所有路徑中最小路徑代價(jià)的估價(jià)值。估價(jià)函數(shù)一般形式：f(i)=g(i)+h(i)g(i):從S0到節(jié)點(diǎn)i已經(jīng)實(shí)際付出的代價(jià)。指出了搜索

17、的橫向趨勢、完備性好、但效率差。h(i):是從節(jié)點(diǎn)i到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價(jià)稱為啟發(fā)函數(shù)f(i):從S0經(jīng)過節(jié)點(diǎn)i到達(dá)目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的代價(jià)估計(jì)值，作用是估價(jià)OPEN表中各節(jié)點(diǎn)的重要性，決定OPEN表的次序。g(i)和h(i)各占適當(dāng)?shù)谋戎?估價(jià)函數(shù)f是這樣確定的：一個(gè)節(jié)點(diǎn)的希望程度越大，其值就越小，被選為擴(kuò)展的節(jié)點(diǎn)，是估價(jià)函數(shù)最小的節(jié)點(diǎn)。 有序狀態(tài)空間搜索算法如下： OPEN:=S0,f:=f(S0) LOOP: IF OPEN=( ) THEN EXIT(FALL) n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED) IF GOAL(n)

18、 THEN EXIT(SUCCESS)C IF EXPAND(n)=( ) GO LOOP IF EXPAND(n)M(mi),f(xi):=d(xi)+h(xi) min, ADD(mi,OPEN), (OPEN) GO LOOP例：八數(shù)碼難題初始狀態(tài)，設(shè)問題的初始狀態(tài)S0和目標(biāo) 狀態(tài)Sg如圖所示，且估價(jià)函數(shù)為： f(n)= d(n)+W(n)其中，d(n)表示節(jié)點(diǎn)n在搜索樹中的深度； W(n)表示節(jié)點(diǎn)n中“不在位”的數(shù)碼個(gè)數(shù)問題：請(qǐng)計(jì)算初始狀態(tài)S0的估價(jià)函數(shù)值f(S0)2831476528314765231847652831476528316475S02318476523184765123

19、847651238476512378465sg定義下面幾個(gè)函數(shù)：ff* *(n):(n):從初始節(jié)點(diǎn)s0出發(fā)，約束經(jīng)過節(jié)點(diǎn)n到達(dá)目 標(biāo)節(jié)點(diǎn)的最小代價(jià)值；f(n)是對(duì)f*(n)的估價(jià)值；gg* *(n):(n):從初始節(jié)點(diǎn)s0到節(jié)點(diǎn)n的最小代價(jià)； g(n)是對(duì)g*(n)的估計(jì)； g(n)=g*(n)hh* *(n):(n):從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最小代價(jià)； h(n)是對(duì)h*(n)的估價(jià)；因此有： f f* * (n)=g (n)=g* *(n)+h(n)+h* *(n)(n) A A算法：算法： f(n)=g (n)+h (n) f(n)=g (n)+h (n)我們對(duì)A算法的全局擇優(yōu)啟發(fā)式搜索算法中的g(n)和h(n)分別提出如下限制：（1）g(n)是對(duì)g*(n)的估計(jì)，且g(n)0;（2）h(n)是對(duì)h*(n)的下界，即對(duì)任意的節(jié)點(diǎn)n均有 h(n)0（2） W (n)=h*(n)1.A*算法的可納性 可納性：可納性：一般來說，對(duì)任意一個(gè)狀態(tài)空間圖，從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)