1、人工智能應用技術復習大綱一、人工智能概述略二、謂詞公式與邏輯推理定義2.1 命題(Proposition)，即具有真(T)假(F)意義的陳述性語句。定義2.2 所謂個體，是指可以獨立存在的某個事物。 定義2.3 謂詞：由定義的謂詞名、變元，共同構成了具有陳述性表達的形式化語句，稱為謂詞。一個謂詞可以有n（其中n=0,1,2, ）個變元，并稱之為n元謂詞。定義2.3 謂詞中包含個體或變元的數(shù)目，稱為謂詞的元或謂詞的目。定義2.4 謂詞表達形式中所包容相疊加的含義層次數(shù)數(shù)目，稱為謂詞的階。例2-2 比較下列謂詞或謂詞形式的命題：LIKE(john，mary)；ROBOT(john)；ROBOT(m

2、ary)； ADDQ(x，y，z)。試解釋具體含義，并指出它們各是幾元謂詞。解：上述謂詞意即“機器人約翰喜歡瑪麗”；和都只有一個個體，稱為一元謂詞；相應則稱為二元謂詞；表示為表達式“x+y=z”，其中包含有3個變元，故稱為三元謂詞。依此類推，可推出關于n元謂詞的概念。例2-3 為了說明謂詞的階，我們來比較下列謂詞形式的命題：LIFELESS(outer-stars)；外星球沒有智能生命。INCORRECT(lifeless(outer-stars)；說“外星球沒有智能生命”是不確切的。解：在上述謂詞形式的命題中，謂詞只有一層含義，稱為一階謂詞；謂詞在前一層含義基礎上，又增加了一層新意，共有二層

3、含義。故把謂詞稱為二階謂詞。依此類推，可推出關于n階謂詞的概念。注意：在謂詞邏輯演算中，最重要的有三大類：即：命題邏輯演算、 一階謂詞邏輯演算和二階謂詞演算。 命題邏輯表示比較簡單，只能表達具體固定的情況，命題是謂詞邏輯特殊事例的生動描述，謂詞邏輯可以靈活表現(xiàn)多種或變化的情況；謂詞表達是命題邏輯的抽象與推廣?？偟目磥?，命題和謂詞的知識表示形式可以相互轉換，而謂詞比命題有更強的表達能力。顯而易見，謂詞是一種描述個體群之間的相互關系、性質(zhì)及其邏輯結構的數(shù)學表示。人們把采用這種表示的運算，又稱為謂詞邏輯。比較起來：命題邏輯演算太簡單，只能解決具體容易的問題；二階謂詞演算又太復雜，以至迄今為止，尚未找

4、到最根本有效的算法。因此，在人工智能中，目前使用最多的還是一階謂詞邏輯演算。n 表2-1 連接詞定義真值表 P Q ¬P PQ PQ PQ P«Q F F T F F T T F T T T F T ? F T F F T F F F T T F T T T T2.1.3命題和謂詞邏輯舉例 例： 小張既聰明，又勤奮，所以他的學習成績一直很好。P：小張聰明Q：小張勤奮R：小張學習成績一直很好n （ P Q） R小王總是在圖書館看書，除非他病了或圖書館不開門。P：小王病了Q：圖書館開門R：小王在圖書館看書n ¬ （ P ¬ Q） « R若張先生是小

5、張的父親，則小張是王太太的兒子。解：先設定謂詞，再設定變元，并將變元代之以常量，用連接詞運算符連接并加以描述：設定謂詞：FATHER (x,y)： x是y的父親 SON (y,w)： y是w的兒子 常量： z 表示張先生；mz 表示小張；wtt王太太則可描述為： FATHER (z, mz) SON (mz, wtt)（2）若x是小張的父親，且y是小張的兄弟，則x也是y的父親。解：先設定謂詞，再設定變元，并將變元代之以常量，用連接詞運算符連接并加以描述：設定謂詞：FATHER (x,y)： x是y的父親 BROTHER (y,w)： y是w的兄弟 常量： mz 表示小張則可描述為： FATHE

6、R (x, mz) BROTHER (y, mz) FATHER (x, y) （3）*在那遙遠的地方，有位好姑娘，人們走過她的身旁，都要回頭留戀地張望。解： (彐x)好姑娘(x)居住的地方(z，x) 遙遠的(z)("y)人(y)行走經(jīng)過(y, z) 回頭留戀地張望(y)例4.1 設已知下述事實：A；B；AC；BCD；DQ. 求證：Q為真。 證明： A，AC Þ C (P規(guī)則及假言推理) B，C Þ BC (引入合取) BC，BCD Þ D (T規(guī)則及假言推理) D，DQ Þ Q (T規(guī)則及假言推理) Q為真 (證畢)例4.2 設已知如下事實：

7、 （1）凡是容易的課程小王（Wang）都喜歡； （2）C班的課程都是容易的； （3）ds是C班的一門課程. 求證：小王喜歡ds這門課程. 證明：首先定義謂詞： EASY（x）x是容易的課程； LIKE（x，y）x喜歡y課程； C（x）x是C班的一門課程.已知：EASY（x）LIKE（Wang，x） ("x)（C（x）EASY（x） C（ds） 求證：LIKE（Wang，ds） 證明：可應用推理規(guī)則進行推理證明。 由，得("x)(C(x)EASY(x) C(y)EASY(y) （全稱固化） 由，得C(ds)，C(y)EASY(y) Þ EASY(ds) (P規(guī)則及假

8、言推理) EASY(ds),EASY(x)LIKE(Wang，x) Þ LIKE(Wang，ds) (T規(guī)則及假言推理) 即小王喜歡ds這門課程。 (證畢)例4.3 設已知 （1）凡是人喜歡吃的東西狗也喜歡； （2）jasper是一條狗； （3）有人喜歡啃骨頭. 求證： jasper喜歡啃骨頭. 證明：首先定義謂詞： DOG（x）x是狗； xjasper，狗， LIKEEAT（y，z）y喜歡吃（啃）z ； yjasper，人， zbones，肉，魚，則得已知條件： ("x)("z)LIKEEAT（人，z）DOG（x） LIKEEAT（ x ，z） DOG（jasp

9、er） LIKEEAT（人，bones） 求證： LIKEEAT（jasper，bones） 證明：代入得("z)LIKEEAT（人，z）DOG（jasper） LIKEEAT（jasper，z） （全稱固化） 代入得LIKEEAT（人，bones）DOG（jasper） LIKEEAT（jasper，bones ） 由為真，得 LIKEEAT（人，bones）DOG（jasper） =T （引入合取詞） 由為真，得 LIKEEAT（jasper，bones）= T (P規(guī)則及假言推理) 即jasper喜歡啃骨頭.(證畢)謂詞公式概念復習與擴充： 使用連接詞和量詞，把若干謂詞連接組合

10、在一起，就得到了謂詞邏輯公式(PLF：Predicate Logic Formula)的表達。下面我們給出謂詞公式的相關各種概念與定義。定義2.5 僅能表達單一意義且不可再細劃分的簡單命題稱為原子命題。例如，一階零元(目)命題、一階一元命題、一階二元命題等都是原子命題。定義2.6 用連接詞或者量詞把若干原子命題聯(lián)結組合在一起，就得到了命題公式(PF：Proposition Formula)，又稱之為命題合式公式。定義2.7 采用參量變元來替代命題合式公式中的常量，就得到了原子謂詞公式，又稱之為謂詞合式公式（PWFF：Predicate Well-Formed Formula），簡稱合式公式或W

11、FF。三、狀態(tài)空間表示法 例1-1 設有三枚錢幣，分別處在“正”、“反”、“正”狀態(tài)。每次只能且必須翻一枚錢幣。問連翻三次后能否達到三枚全朝上或全朝下的狀態(tài)？首先應把問題形式化。設正面表示為1，反面表示為0，可引入一個三元組Q= (q0,q1,q2)來描述這三枚錢幣的狀態(tài)，每個qi的取值為0,1，因此共有23=8種不同的狀態(tài)。這8種狀態(tài)列舉如下：；于是問題就變?yōu)槿鐖D1-4所示。圖1-4 例1-1的問題示意接著應找出所有能改變狀態(tài)的操作。這里翻動一枚錢幣就稱為一種操作，則共有3種操作，即F=a,b,c。其中，a表示將錢幣q0翻轉一次，b表示將錢幣q1翻轉一次，c表示將錢幣q2翻轉一次。如圖1-5

12、所示是此問題的全部狀態(tài)空間圖。圖1-5 三枚錢幣的狀態(tài)空間圖圖1-5中結點表示狀態(tài)，有向邊表示操作，雙向箭頭表示兩個狀態(tài)在同一操作下是可逆的，這樣可以為三次操作提供方便。從圖1-5中可以看出，從Qs=Q5出發(fā)，不可能通過三次操作到達Q0=Qg1，這說明從Q5到Q0之間沒有所要求的解；而從Q5出發(fā)到達Qg2=Q7有7種操作序列，因而有7個解，它們是aab，aba，baa，bbb，bcc，cbc和ccb。例6-1設有分別由開關控制的一字排開的3盞信號燈，處在“亮、暗、亮”的初始狀態(tài)。每次操作允許并必須扳動一只開關，問：如果連扳三次開關后，是否可以出現(xiàn)錯“亮、亮、亮”或“暗、暗、暗”的狀態(tài)？解:首先

13、將該問題形式化：設開關“off”燈為“暗”，以0表示；開關“on”燈為“亮”，以1表示；再分別用A、B、C標識3盞燈亮或暗的狀態(tài)。這樣，可引入一三元數(shù)組Sk=（A,B,C）來描述這3盞信號燈的總狀態(tài)。全部可能的狀態(tài)計有8種： 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=（1,0,1）；目標狀態(tài)有2個： G =S0，S7=（0,0,0），（1,1,1）狀態(tài)的操作數(shù)，共3個，F(xiàn) =a,b,c,分別表示把各燈開

14、關扳動一次 ；問題的狀態(tài)空間可寫成S5,a,b,c,S0，S7.教材中圖6-3表示了全部可能的狀態(tài)及其相互關系。 （0，0，0）（1，0，0）（0，0，1）（1，0，1）（1，1，0）（1，1，1）（0，1，0）（0，1，1）aaabbbbcccca其中S5是初始狀態(tài)，S0和S7都是目標狀態(tài)。從圖中我們可以清楚地看出：從S5經(jīng)過三步搜索不可能恰好到達S0，即不存在從S5到達S0的解；但從S5出發(fā)搜索，到達S7的路徑有7條，它們的動作序列分別為aab、aba、baa、bbb、bcc、cbc和ccb等，共有七組解。 由上述利用狀態(tài)空間圖求解的舉例，對具體問題搜索求解可總結為如下的思路和步驟：（1）

15、設定狀態(tài)變量及確定值域；（2）確定狀態(tài)組，分別列出初始狀態(tài)集和目標狀態(tài)集；（3）定義并確定操作集； （4）估計全部狀態(tài)空間數(shù)，并盡可能列出全部狀態(tài)空間或予以描述之；（5）當狀態(tài)數(shù)量不是很大時，按問題的有序元組畫出狀態(tài)空間圖，依照狀態(tài)空間圖搜索求解。 例6-2 傳教士和野人問題（The Missionaries and Cannibals Problem）。在河的左岸有三個傳教士、一條船和三個野人，傳教士們想用這條船將所有的成員都運過河去，但是受到以下條件的限制：傳教士和野人都會劃船，但船一次最多只能裝運兩個；在任何岸邊野人數(shù)目都不得超過傳教士，否則傳教士就會遭遇危險：被野人攻擊甚至被吃掉。此外

16、，假定野人會服從任何一種過河安排，試規(guī)劃出一個確保全部成員安全過河的計劃。例1-2 修道士和野人問題。在河的左岸有3個修道士、3個野人和1條船，現(xiàn)在要渡河到右岸，但有如下限制條件：（1）船最多坐2人，修道士和野人都會劃船。（2）在任何岸邊野人人數(shù)都不能超過修道士人數(shù)，否則修道士就會被吃掉。請規(guī)劃出一個安全的渡河方案。解：我們按上述步驟來進行求解分析。（1）設定狀態(tài)變量及確定值域。為了建立這個問題的狀態(tài)空間，設左岸傳教士數(shù)為m，則 m =0,1,2,3；對應右岸的傳教士數(shù)為3m； 左岸的野人數(shù)為c，則有 c =0,1,2,3； 對應右岸野人數(shù)為3c；左岸船數(shù)為b，故又有b=0,1，右岸的船數(shù)為1

17、b.（2）確定狀態(tài)組，分別列出初始狀態(tài)集和目標狀態(tài)集。 問題的狀態(tài)可以用一個三元數(shù)組來描述，以左岸的狀態(tài)來標記，即 Sk =（m,c,b），右岸的狀態(tài)可以不必標出。初始狀態(tài)一個： S0 =（3,3,1），初始狀態(tài)表示全部成員在河的左岸；目標狀態(tài)也只一個： Sg =（0,0,0），表示全部成員從河左岸渡河完畢。（3）定義并確定操作集。 仍然以河的左岸為基點來考慮，把船從左岸劃向右岸定義為Pij操作。其中,第一下標i表示船載的傳教士數(shù), 第二下標j表示船載的野人數(shù)；同理，從右岸將船劃回左岸稱之為Qij操作，下標的定義同前。則共有10種操作，操作集為 F=P01，P10，P11，P02，P20，Q0

18、1，Q10，Q11，Q02，Q20（4）估計全部的狀態(tài)空間數(shù)，并盡可能列出全部的狀態(tài)空間或予以描述之。 在這個問題世界中，S0 =（3,3,1）為初始狀態(tài)，S31 = Sg =（0,0,0）為目標狀態(tài)。全部的可能狀態(tài)共有32個，如表6-1所示。表6-1傳教士和野人問題的全部可能狀態(tài)狀態(tài)m,c,b狀態(tài)m,c,b狀態(tài)m,c,b狀態(tài)m,c,bS0 3 3 1 S8 1 3 1 S16 3 3 0 S24 1 3 0S1 3 2 1 S9 1 2 1 S17 3 2 0 S25 1 2 0S2 3 1 1 S10 1 1 1 S18 3 1 0 S26 1 1 0S3 3 0 1 S11 1 0 1

19、S19 3 0 0 S27 1 0 0S4 2 3 1 S12 0 3 1 S20 2 3 0 S28 0 3 0S5 2 2 1 S13 0 2 1 S21 2 2 0 S29 0 2 0S6 2 1 1 S14 0 1 1 S22 2 1 0 S30 0 1 0S7 2 0 1 S15 0 0 1 S23 2 0 0 S31 0 0 0注意：按題目規(guī)定條件，應劃去非法狀態(tài)，從而加快搜索效率。 1）首先可以劃去左岸邊野人數(shù)目超過傳教士的情況，即S4、S8、S9、S20、S24、S25等6種狀態(tài)是不合法的； 2）應劃去右岸邊野人數(shù)目超過修道士的情況，即S6、S7、S11、S22、S23、S27

20、等情況；3）應劃去4種不可能出現(xiàn)狀態(tài)：劃去S15和S16船不可能?？吭跓o人的岸邊；劃去S3傳教士不可能在數(shù)量占優(yōu)勢的野人眼皮底下把船安全地劃回來；劃去S28傳教士也不可能在數(shù)量占優(yōu)勢的野人眼皮底下把船安全地劃向?qū)Π丁？梢?，在狀態(tài)空間中，真正符合題目規(guī)定條件的只有16個合理狀態(tài)。 （5）當狀態(tài)數(shù)量不是很大時，按問題的有序元組畫出狀態(tài)空間圖，依照狀態(tài)空間圖搜索求解。 根據(jù)上述分析，共有16個合法狀態(tài)和允許的操作，可以劃出傳教士和食人者問題的狀態(tài)空間圖，如圖6-4所示。300311110020221031010111000021011331310321220320S18 S24 S12 S10 S0

21、 S17 S1 S2 20 S29 02 S30 S14 S31S21 S19 S5 S13 圖6-4 傳教士和野人問題的狀態(tài)空間圖：四、搜索技術基本搜索策略主要分為四種類型：即1. 寬度優(yōu)先搜索;2. 深度優(yōu)先搜索;3. 有界搜索;4. 代價推進搜索。2.1 寬度優(yōu)先搜索(Breadth-first Search)又稱為廣度優(yōu)先搜索或橫向優(yōu)先搜索，顧名思義，即搜索任務是按照橫向逐步擴展向前推進而完成的。圖6-10 寬度優(yōu)先搜索過程之一 為了用算法來實現(xiàn)其搜索過程，需要預先建立兩個表，分別稱為OPEN表及CLOSED表。OPEN表：只用來登記存放新生成并待擴展的節(jié)點，不保留已擴展及已被考察的節(jié)

22、點；CLOSED表：用來存放已擴展并已被考察的節(jié)點，即登記已經(jīng)完成的搜索路徑。一般對于不同的搜索策略，在OPEN表中節(jié)點排列的順序是不同的。這里約定，OPEN表中按節(jié)點生成及進入的先后的順序排列，先生成的節(jié)點排在前面，后生成的節(jié)點排在后面，并實行先進先出(FIFO)的算法來進行搜索。n 寬度優(yōu)先搜索過程可用圖6-11的工作流程來表示。其步驟為：開始把S0送入OPEN表OPEN空？ 把OPEN表的第一個節(jié)點（節(jié)點n）從表中移出，放入CLOSED表節(jié)點n為目標節(jié)點？節(jié)點n可擴展？擴展節(jié)點n，將其子節(jié)點放入OPEN表，并為每個子節(jié)點配置指向n的指針成功，退出失敗，退出YNYNYN寬度優(yōu)先搜索流程示意

23、圖（1）把初始節(jié)點S0放入OPEN表；（2）如果OPEN表為空，則問題無解，退出。（3）把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表；（4）考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。（5）若節(jié)點n不可擴展，則轉第（2）步。（6）擴展節(jié)點n,將其子節(jié)點放入OPEN表，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉第（2）步 其得到的搜索的路徑為：S0S1S2S11S12S21S22S111S112S113S121S122（Sg.）n 算法特點：顯然，寬度優(yōu)先搜索法是一種遵循規(guī)則的盲目性搜索，它遍訪了目標節(jié)點前的每一層次每一個節(jié)點，即檢查了目標節(jié)點前的全部的狀態(tài)空間點

24、，只要問題有解，它就能最終找到解，且最先得到的將是最小深度的解。可見，寬度優(yōu)先搜索法很可靠。但是，當目標節(jié)點距離初始節(jié)點較遠時將會產(chǎn)生許多無用的中間節(jié)點。因此，速度慢，效率低，尤其對于龐大的狀態(tài)空間實用價值差。2.2 深度優(yōu)先搜索(Depth-first Search)又稱為縱向優(yōu)先搜索，顧名思義，即搜索任務是按照縱深方向，逐級地向下跨越推進而完成的。深度優(yōu)先搜索的基本方法為：從根節(jié)點S0開始，始終沿著縱深方向搜索，總是在其后繼子節(jié)點中選擇一節(jié)點來考察。若到達目標節(jié)點Sg，則搜索成功；若不是目標節(jié)點，則再在該節(jié)點的后繼子節(jié)點中選一考察，一直如此向下搜索，直到搜索找到目標節(jié)點才停下來。若到達某個

25、子節(jié)點時，發(fā)現(xiàn)該節(jié)點既不是目標節(jié)點又不能繼續(xù)擴展，就選擇其兄弟節(jié)點再進行考察。依此類推，直到找到目標節(jié)點或全部節(jié)點考察完畢，搜索過程才可以終止或結束。 例6-5如圖6-14所示，設法使用深度優(yōu)先搜索過程算法，尋找出從S0到達Sg的搜索路徑。 S0 S1 S2 S11 S12 S21 S22 S111 S112 S113 S121 S122 S211 S212 S221 S222S2212=Sg 解：假設圖中所標記的是全部的搜索樹。我們采用的一種深度優(yōu)先搜索過程算法是：發(fā)生器函數(shù)Q(x)按照每一層節(jié)點從左至右的優(yōu)先級，并按照“最晚生成的節(jié)點優(yōu)先擴展”并優(yōu)先考察搜索的原則。這里，就可獲得一種先擴展

26、(包括括號內(nèi)、外的節(jié)點)，再既而完成考察與搜索(不用括號的節(jié)點)，其路徑為：S0(S1)S2(S21)S22(S221)S222 (S2221)S2222S2221S221(S2211)S2212=Sg. 針對教材中圖6-12所示的重排九宮問題，按照上述“最晚生成的節(jié)點優(yōu)先擴展”并優(yōu)先考察搜索的原則，如圖6-15所示，則得到的搜索路徑是：S0=159132122，這里還只是搜索樹的一部分，尚未到達目標Sg ；而沿著分枝S0=1361014= Sg路徑的深度優(yōu)先搜索，卻可以高效率到達目標節(jié)點?？梢娚疃葍?yōu)先搜索的效率將隨著選擇路徑的不同而具有較大的區(qū)別。 看起來深度優(yōu)先搜索算法流程與寬度優(yōu)先搜索算

27、法過程幾乎完全相同。其主要區(qū)別在于采用的OPEN表結構不同：深度優(yōu)先搜索OPEN表，實行的是后進先出(LIFO) 的算法進行搜索；這與寬度優(yōu)先搜索算法實行先進先出(FIFO)的算法不同。深度優(yōu)先搜索的特點：方式靈活，規(guī)則易于實現(xiàn)，對于有限狀態(tài)空間并有解時，必能找到解。例如，當搜索到某個分支時，若目標節(jié)點恰好在此分支上，則可較快地得到解。故在一定條件下，可實現(xiàn)較高求解效率。但是，在深度優(yōu)先搜索中，一旦搜索進入某個分支，就將沿著該分支一直向下搜索。這時，如果目標節(jié)點不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。可見，深度優(yōu)先搜索算法不完備，風險大，易于掉入陷阱。因此，要使深度優(yōu)先搜索算

28、法可用，必須加以改造。2.3 有界搜索為了避免深度優(yōu)先搜索過程陷入無窮分支的死循環(huán)，人們又提出了有界深度優(yōu)先搜索算法基本思想：設定一個搜索深度的界限dm ，當搜索深度達到dm ，而尚未出現(xiàn)目標節(jié)點時，可回朔換一個分支進行搜索，直到dm的深度內(nèi)所有分支節(jié)點搜索完畢。有界深度優(yōu)先搜索過程可概括為：（1）把初始節(jié)點S0放入OPEN表中，置S0的深度d(S0)=0；（2）如果OPEN表為空，則問題無解，退出。（3）把OPEN表中的第一個節(jié)點（記為節(jié)點Sn）取出放入CLOSED表；（4）考察節(jié)點Sn是否為目標節(jié)點。若是，則求得了問題的解，退出。（5）如果節(jié)點Sn的深度d（Sn）= dm 或節(jié)點Sn不可擴

29、展，則轉到第（2）步；（6）擴展節(jié)點Sn，將其子節(jié)點放入OPEN表的首部，并為其配置指向父節(jié)點的指針，然后轉到第（2）步?；舅阉鞑呗缘木窒扌约捌涮攸c 概括起來，廣度優(yōu)先搜索、深度優(yōu)先搜索、有界深度優(yōu)先搜索和代價推進搜索法等，它們的局限性及其特點為：基本搜索策略普遍適用于樹狀問題求解，控制性知識簡單，容易編程在計算機上實現(xiàn)。但是，它表現(xiàn)出來的缺點也很突出：一般必須知道問題的全部狀態(tài)空間，搜索效果差，求解能力弱，故常被稱為弱方法。 它們都是依據(jù)某種固定規(guī)則運行的搜索，均屬于非啟發(fā)的強力搜索，沒有表現(xiàn)出智能搜索的活躍性與靈活性。也就是說，問題搜索樹的生成、擴展以及節(jié)點接受考察的次序等，都是由生硬死

30、板的搜索方法決定的，而不由具體問題狀態(tài)信息引導與經(jīng)驗分析來決定；由于基本搜索策略疏忽了對給定問題的特有知識的分析,沒有充分考慮所要求解問題的自身發(fā)展規(guī)律和特性，搜索完全是按事先確定好的固定排序來進行的，這是一種窮盡遍歷的大海撈針式的策略，沒有任何啟發(fā)式信息引導，往往使得實際搜索效率很低，故又被稱為盲目搜索。 2.4 啟發(fā)式搜索所謂啟發(fā)式搜索（Heuristic Search）策略,即利用與問題解有關的啟發(fā)信息來作引導的搜索策略。搜索效率及其評價：有一種比較直觀的評價搜索效率的方法，其定義公式為： P=L/T （6-4）L是從根節(jié)點到達目標節(jié)點的深度；T是在整個搜索過程中產(chǎn)生節(jié)點總數(shù)(不計根節(jié)點

31、)，因此，這里P反映的是朝著目標搜索時的搜索寬度。 討論：搜索效率定義公式為： P=L/T一般情況下，P1 因為總有TL；）當L=T時，則 P=L/T=1，表示搜索過程中每次只生成一個節(jié)點，并且它恰好是解路徑上的節(jié)點，表示了一種以單枝延伸的搜索樹。這時，啟發(fā)能力最強，效率最高，即所擴展的每一個節(jié)點都落在最佳路徑上，稱為最佳搜索。 當P=L/T1，幾近于零，沒有任何控制性知識作依據(jù)，搜索中的每一步都是完全隨意而進行的，稱為隨機搜索；通常搜索總是介于01之間。因此，為了快速地找到問題的解，總是使搜索盡可能利用啟發(fā)信息，努力使搜索路徑的每一步都盡可能與最佳搜索路徑重合一致，以便實現(xiàn)更高的搜索求解效率

32、。啟發(fā)式搜索的主要特點是：由于充分考慮到問題求解所應用到的各種啟發(fā)信息及知識，包括利用常識性推理和專家經(jīng)驗等信息與知識，啟發(fā)式搜索能夠動態(tài)地確定操作排序，優(yōu)先調(diào)用較合適的操作規(guī)則，擴展、比較并選擇最有希望的節(jié)點，使搜索盡可能以最快的速度，最短的距離，最小的代價，朝著最有利于達到目標節(jié)點的方向推進。即以智能思想調(diào)節(jié)搜索區(qū)，使盡量沿著最有希望找到解的路徑方向上，縱向小范圍地搜索前進。所謂估價函數(shù)，是指從問題樹根節(jié)點到達目標節(jié)點的搜索中，所要耗費全部代價的一種估計值，記為f (n)。n 估價函數(shù)以數(shù)學公式形式可表達為： f(n)=g(n)+h(n) （6-5） 其公式中各部分表達的意義如下：n f

33、(n)：表示從根節(jié)點So出發(fā)，經(jīng)過當前節(jié)點Sn，到達目標節(jié)點Sg已耗費及將要耗費代價總和的估計值。n g (n)：表示從根節(jié)點So，在到達目標節(jié)點Sg的搜索路徑上，已到達當前節(jié)點Sn，g (n) 即表示從SoSn已耗費的代價。n h (n)：指從當前節(jié)點Sn，預測估計到達目標節(jié)點Sg，將要耗費的可能代價。也就是說，h（n）表示了SnSg這一路徑搜索段上將要耗費代價的可能值。稱之為啟發(fā)函數(shù)。討論：h(n)=0，則f(n)= g(n) 表示沒有任何啟發(fā)信息的作用，該搜索也就簡化為基本搜索，又稱為盲目搜索或“弱” 搜索方法?？梢?，從某種意義上來說，基本搜索亦是普通搜索的一種特例。 2.4.1 瞎子爬

34、山法n 瞎子爬山過程：每搜索到達一個節(jié)點，其隨后選擇的下一節(jié)點不是按規(guī)則預定的或盲目選定的，而是按經(jīng)驗進行智能處理，使用估計函數(shù)f(x)來搜索當前最優(yōu)的節(jié)點。n 在實現(xiàn)瞎子爬山的局部擇優(yōu)搜索法中，可取消OPEN表，每次擴展后只保留符合估價函數(shù)f(x)的最優(yōu)子節(jié)點N，而將其它子節(jié)點全部丟掉，N下一次擴展的節(jié)點，可直接放入CLOSED表中。依次步步為營，搜索求解，直到到達目標節(jié)點Sg為止。顯而易見，局部擇優(yōu)搜索是對深度優(yōu)先搜索方法的一種改進。由于它每次都只是在子節(jié)點的范圍內(nèi)選擇下一個要考察的節(jié)點，范圍較窄，所以稱為局部擇優(yōu)搜索。n 估價函數(shù): f(n)= g(n)+ h(n)，n 其中啟發(fā)函數(shù) h

35、(n)=grad H(r)，即為高度函數(shù)H(r)梯度的絕對值。n 其生成函數(shù)按選擇方向深度搜索，逐點生成。瞎子爬山法的主要特點n 瞎子爬山法在許多情況下是有效的。n 優(yōu)點:方法簡單，由于取消了OPEN表，要處理的數(shù)據(jù)量減少了，所以占用內(nèi)存空間少、速度快。n 缺點:但瞎子爬山法主要只在單因素，單極值的情況下使用，而在多極值情況下會遇到許多困難，導致找不到最佳解。n 例如在二維或三維的情況下，就會遇到“多峰”問題、“盆地”或“平臺”、“山脊”問題等，使搜索失?。ㄒ妶D6-21）。 瞎子爬山法的局限性n 所謂“多峰”問題：數(shù)學多局部極值問題，即發(fā)現(xiàn)使一階導數(shù)（或偏導數(shù)）為零的節(jié)點有好幾個，導致瞎子有可

36、能只爬上某個次高峰而誤以為是最高峰；n 所謂“盆地”或“平臺”問題：指周圍都是平地，使得導數(shù)處處為零，搜索無所適從而不知道選擇那個前進方向才能獲得最佳效果；n “山脊”問題：指搜索區(qū)域因斷層而形成一條凸起連接，使得一階導數(shù)不連續(xù)，前后左右遇到的都是斜率減小方向而誤以為到達了目的地。2.4.2 全局擇優(yōu)搜索法n 進行全局擇優(yōu)搜索時，要求仍然保留OPEN表。在這種方法搜索中, 每當要選擇一個節(jié)點進行考察時,首先總是依照次序來比較OPEN表中所有節(jié)點的估價值，設法從中選擇一個估價值最小或最優(yōu)的節(jié)點來搜索求解；n 其次，若有多個解路徑存在時，要依照次序來比較每個解路徑的代價值，以便從中找到總代價最小的

37、搜索解路徑，即盡可能得到最優(yōu)解。全局擇優(yōu)搜索又稱為有序搜索法。n 全局擇優(yōu)搜索的搜索過程如下:(1) 把初始節(jié)點So放入OPEN表,計算f(So)；(2) 如果OPEN表為空,則轉到步(8)。 (3 )把OPEN表中的第一個節(jié)點(記節(jié)點n)從表中移出，放入CLOSED表；(4) 考察節(jié)點n是否為目標節(jié)點。若是,則成功得到問題的一個解,標記其解路徑。并標記目標節(jié)點順序，記為Sgk,轉步(2)，以便搜索下一個解。(5) 若節(jié)點n不可擴展,則轉步(7)。(6) 擴展節(jié)點n,用估價函數(shù)f(n)計算每個子節(jié)點的估價值,并為每個子節(jié)點配置指向父節(jié)點的指針,把這些子節(jié)點都送人OPEN表中,然后對OPEN表中

38、的全部節(jié)點按估價從小至大進行排序；(7) 轉步(2)；(8) 分別計算每一個目標節(jié)點的代價值，按照代價值從小至大進行排序。則排在最前面的目標節(jié)點優(yōu)于排在后面的目標節(jié)點。2.5 與/或樹、搜索樹及其解樹 n 與/或樹(And/Or Trees)：是樹表達的推廣，與/或圖的特例。問題的狀態(tài)可以借用樹及其根、枝、葉等名稱來表示；也可按照祖先與后代諸如子、孫等層次或輩份關系來定義。其中根節(jié)點是唯一的，輩份最高；葉是端節(jié)點，輩份最低。枝、干及其分枝介于根與葉之間。n 與樹：把一個難于直接求解的復雜問題分解為若干個比較簡單的子問題，各個子問題的全部解決等價為該問題的解決；而對于困難的子問題求解，同樣依照這

39、種方法處理。這樣就形成了一種與結構的關系樹，稱之為與樹；并把相關節(jié)點及其邊用一弧線連接，稱之為與關系表示。如下圖所示，其S0節(jié)點及其子節(jié)點所形成的分枝樹的結構關系。n 或樹：使用類似的思想方法，我們可以引出或樹的概念。也就是說，把一個難于直接求解的問題分解為若干個與之等價而又更簡單的子問題，每個子問題的解決等價為該問題的解決，就形成了一種或結構的關系樹，稱之為或樹?；蜿P系樹的表達可以不必特別加以標志。n 與/或樹：如果問題狀態(tài)空間既有或結構，又有與結構的復合關系，就得到了與/或混合樹，簡稱與/或樹，如上圖6-25所示。若把前面所研究的搜索策略再應用于與/或樹，自然也就形成了與/或樹全部的搜索策

40、略了。 與樹及其表示S S S S S S S1 S1 S1 S11 S S1S11 S113 S S11 五、神經(jīng)網(wǎng)絡一般地,人工神經(jīng)元的結構模型如圖3所示。 它是一個多輸入單輸出的非線性閾值器件。其中 x1，x2，xn表示神經(jīng)元的n個輸入信號量； w1，w2，wn表示對應輸入的權值,它表示各信號源神經(jīng)元與該神經(jīng)元的連接強度； A表示神經(jīng)元的輸入總和,它相應于生物神經(jīng)細胞的膜電位,稱為激活函數(shù);y為神經(jīng)元的輸出;表示神經(jīng)元的閾值。 函數(shù)y=f(A)稱為特性函數(shù)(亦稱作用函數(shù)或傳遞函數(shù))。特性函數(shù)可以看作是神經(jīng)元的數(shù)學模型。如果將多個神經(jīng)元按某種的拓撲結構連接起來，就構成了神經(jīng)網(wǎng)絡。 根據(jù)連接

41、的拓撲結構不同，神經(jīng)網(wǎng)絡可分為四大類：分層前向網(wǎng)絡、反饋前向網(wǎng)絡、互連前向網(wǎng)絡、廣泛互連網(wǎng)絡。 神經(jīng)網(wǎng)絡至少可以實現(xiàn)如下功能： 數(shù)學上的映射逼近 通過一組映射樣本(x1，y1)(x2，y2)，(xn，yn)，網(wǎng)絡以自組織方式尋找輸入與輸出之間的映射關系：yi=f(xi)。 數(shù)據(jù)聚類、壓縮通過自組織方式對所選輸入模式聚類。 聯(lián)想記憶 實現(xiàn)模式完善、恢復，相關模式的相互回憶等。 優(yōu)化計算和組合優(yōu)化問題求解 利用神經(jīng)網(wǎng)絡的漸進穩(wěn)定態(tài)，特別是反饋網(wǎng)絡的穩(wěn)定平衡態(tài)，進行優(yōu)化計算或求解組合優(yōu)化問題的近似最優(yōu)解。 網(wǎng)絡學習一般是利用一組稱為樣本的數(shù)據(jù),作為網(wǎng)絡的輸入(和輸出),網(wǎng)絡按照一定的訓練規(guī)則(又稱學

42、習規(guī)則或?qū)W習算法)自動調(diào)節(jié)神經(jīng)元之間的連接強度或拓撲結構,當網(wǎng)絡的實際輸出滿足期望的要求,或者趨于穩(wěn)定時,則認為學習成功。例 9.3 設計一個BP網(wǎng)絡，對表9.2所示的樣本數(shù)據(jù)進行學習，使學成的網(wǎng)絡能解決類似的模式分類問題。設網(wǎng)絡的輸入層有三個節(jié)點，隱層四個節(jié)點，輸出層三個節(jié)點，拓撲結構如圖9-11所示。輸入輸出X1 x2 x3Y1 y2 y30.3 0.8 0.10.7 0.1 0.30.6 0.6 0.61 0 00 1 0 0 0 1用樣本數(shù)據(jù)按BP算法對該網(wǎng)絡進行訓練，訓練結束后，網(wǎng)絡就可作為一種模式分類器使用。因為網(wǎng)絡的輸出向量(1，0，0)、(0，1，0)、(0，0，1)可以表示多

43、種模式或狀態(tài)。如可以分別表示凸、凹和直三種曲線，或者三種筆劃，也可以表示某公司的銷售情況：高峰、低谷和持平等等。當然，要使網(wǎng)絡有很好的模式分類能力，必須給以足夠多的范例使其學習，本例僅是一個簡單的示例。按學習方式分類神經(jīng)網(wǎng)絡的學習方式包括三種，有導師學習、強化學習和無導師學習。按學習方式進行神經(jīng)網(wǎng)絡模型分類時，可以分為相應的三種，即有導師學習網(wǎng)絡、強化學習網(wǎng)絡及無導師學習網(wǎng)絡。3、利用神經(jīng)網(wǎng)絡的結構和權值及閾值，請寫神經(jīng)元yi和z的計算公式，對4個例子的輸入值計算出輸出值。Zy1y2T1=1T2=1X1X21111其中作用函數(shù)為： 例子：X1X2Z00？10？01？11？（1）計算公式為（2）

44、4個例子的計算值為：（a） (b) （c） (d) 六、 專家系統(tǒng)n 須滿足的基本功能（共六大功能）: 存儲問題求解所需的專家知識; 存儲具體領域內(nèi)的初始數(shù)據(jù)和推理過程中所涉及到的各種信息如中間結果、目標、子目標、條件、假設等等。 根據(jù)當前輸入的數(shù)據(jù)，利用已有的知識，按照一定的推理策略，去解決當前問題，并能控制、協(xié)調(diào)整個系統(tǒng)。 能對推理過程、結論或系統(tǒng)自身做出必要的解釋如解題步驟、處理策略、選擇處理方法、求解某種問題的能力、系統(tǒng)如何組織和管理其自身知識等。這樣既便于用戶的理解和接受，同時也便于系統(tǒng)的維護。 提供知識獲取、機器學習、修改、擴充和完善等其它維護手段。這樣才能更有效地提高系統(tǒng)的問題求

45、解能力及準確性。 提供一種人機接口，能分析、理解用戶的各種請求。 其中，存放知識和使用知識是專家系統(tǒng)的兩個基本功能，用于實現(xiàn)該功能的知識庫和推理機構成了專家系統(tǒng)的兩個核心部件，如圖7-2所示。n 基于規(guī)則的專家系統(tǒng)的結構：一般包括知識與數(shù)據(jù)庫、推理機、黑板、人機接口、解釋器和知識獲取機等六部分。知識庫推理機輸入或提問答案專家知識專家系統(tǒng)的基本結構 人 機 接 口推理機解釋器知識獲取知識與數(shù)據(jù)庫黑 板專家系統(tǒng)的一般結構專家系統(tǒng)的一般結構 專家系統(tǒng)的結構知識與數(shù)據(jù)庫：包括專家知識庫和事實數(shù)據(jù)庫兩部分，存儲著求解領域中問題所需的專家知識及數(shù)據(jù)，它是專家系統(tǒng)的組成基礎。主要用途：用于存放相關領域或問題

46、的初始數(shù)據(jù)、中間結果、最終結論等。它能對知識和全局數(shù)據(jù)施行存儲、管理，并以規(guī)則形式表達專家級知識。一類是領域中的定義、事實和理論等，通常收錄于相關學術著作和教科書中；另一類是專家個人在工作經(jīng)歷中所獲得的實踐經(jīng)驗等。這使得專家們在錯綜復雜關鍵時刻，能臨機決斷，做出正確決策。特性： 它可被所有的規(guī)則訪問； 規(guī)則之間的聯(lián)系只有通過數(shù)據(jù)庫才能發(fā)生。推理機：推理機實際上就是一組計算機程序，它是專家系統(tǒng)的“思維”機構，是構成專家系統(tǒng)的核心部分。主要功能：協(xié)調(diào)控制整個系統(tǒng)，模擬領域?qū)＜业乃季S過程，控制并執(zhí)行對問題的求解。它能根據(jù)當前已知的事實，利用知識庫中的知識，按一定的推理方法和控制策略進行推理，求得問題

47、的答案或證明某個假設的正確性?？傊R庫和推理機構成了一個專家系統(tǒng)的基本框架。同時，這兩部分又是相輔相成、密切相關的。因為不同的知識表示有不同的推理方式，所以，推理機的推理方式和工作效率不僅與推理機本身的算法有關，還與知識庫中的知識以及知識庫的組織有關。黑板：黑板是一種可讀、可刷新重寫的裝置，用于描述記錄專家系統(tǒng)的中間推理過程、數(shù)據(jù)的變換與演算，又稱為暫存器。許多專家系統(tǒng)結構把黑板并入數(shù)據(jù)庫中，但它只是系統(tǒng)運行中間的一些動態(tài)信息的集合，是系統(tǒng)運行期間產(chǎn)生和變化的，因此，它只是數(shù)據(jù)庫中“動態(tài)”變化的那一部分。有了黑板，便于進行系統(tǒng)跟蹤、調(diào)試與解釋。解釋模塊（解釋器）： 這是實現(xiàn)系統(tǒng)透明性的重要

48、模塊。它負責回答用戶提出的各種問題，解釋系統(tǒng)的推理過程，使系統(tǒng)向用戶透明。 解釋程序模塊由一組程序構成，它是專家系統(tǒng)區(qū)別于一般程序的重要特征之一。它可對推理路線和提問的含義給出必要的清晰的解釋，使用戶了解推理過程；并能跟蹤并記錄推理過程，也為系統(tǒng)維護提供了方便的手段。知識獲取模塊： 這是專家系統(tǒng)中能將某專業(yè)領域內(nèi)的事實性知識和領域?qū)＜宜赜械慕?jīng)驗性知識轉化為計算機可利用的形式并送入知識庫的功能模塊。同時也負責知識庫中知識的修改、刪除和更新，并對知識庫的完整性和一致性進行維護。知識獲取模塊是實現(xiàn)系統(tǒng)靈活性的主要部分，它使領域?qū)＜铱梢孕薷闹R庫而不必了解知識庫中知識的表示方法、知識庫的組織結構等實

49、現(xiàn)上的細節(jié)問題，這大大地提高了系統(tǒng)的可擴充性。人機接口： 人機接口負責把領域?qū)＜?、知識工程師或一般用戶輸入的信息轉換成系統(tǒng)內(nèi)規(guī)范化的表示形式，然后把這些內(nèi)部表示交給相應的模塊去處理。系統(tǒng)輸出的內(nèi)部信息也由人機接口轉換成用戶易于理解的外部表示形式顯示給用戶。 n 求解過程大致有如下幾個步驟： 根據(jù)用戶的問題對知識庫進行搜索，尋找有關的知識。 根據(jù)有關的知識和系統(tǒng)的控制策略形成解決問題的途徑，即知識操作算子序列，從而構成一個假設集合。 對解決問題的一組可能假設方案進行排序，并挑選其中在某些準則下為最優(yōu)的假設方案。 根據(jù)挑選的解決問題的假設方案去求解具體問題。 如果該方案不能真正解決問題，則回溯到假設方案序列中的下一個假設方案，重復求解問題。 上述過程循環(huán)執(zhí)行，直到問題已經(jīng)解決或所有可能的求解方案都不能解決問題而宣告“本系統(tǒng)該問題無解”為止。n 設有規(guī)則 R: (AB)(CD)(EF)G) S產(chǎn)生式結構可轉換為與/或樹結構來表示：SBA S1S S3 S4 C D S5 S6 E F G n 專家系統(tǒng)的性能需要從四方面來考慮：即方便性、有效性、可靠性和可維護性。n 專家系統(tǒng)設計的準則： 知識庫和推理機分離。這是設計專家系統(tǒng)的基本原則。 盡量使用統(tǒng)一的知識表示方法。以便于系統(tǒng)對知識進行統(tǒng)一的處理、解釋和管理。 推理機應盡量簡化。把啟發(fā)性知識也盡可能地獨立