人工智能ppt精品課件

1、人工智能及其應(yīng)用,第1章緒論,1、重點(diǎn)掌握人工智能的幾種定義。 2、掌握目前人工智能的三個(gè)主要學(xué)派及 其認(rèn)知觀。 3、一般了解人工智能的主要研究范圍和 應(yīng)用領(lǐng)域,定義2 人工智能(學(xué)科) 人工智能(學(xué)科)是計(jì)算機(jī)科學(xué)中涉及研究、設(shè)計(jì)和應(yīng)用智能機(jī)器的一個(gè)分支。它的近期主要目標(biāo)在于研究用機(jī)器來(lái)模仿和執(zhí)行人腦的某些智力功能，并開(kāi)發(fā)相關(guān)理論和技術(shù)。 定義3 人工智能(能力) 人工智能(能力)是智能機(jī)器所執(zhí)行的通常與人類(lèi)智能有關(guān)的智能行為，如判斷、推理、證明、識(shí)別、感知、理解、通信、設(shè)計(jì)、思考、規(guī)劃、學(xué)習(xí)和問(wèn)題求解等思維活動(dòng),人工智能的三大學(xué)派及其認(rèn)知觀： (1)符號(hào)主義 認(rèn)為人工智能起源于數(shù)理邏輯。

2、(2)連接主義 認(rèn)為人工智能起源于仿生學(xué)，特別是對(duì)人腦模型的研究。 (3)行為主義 認(rèn)為人工智能起源于控制論,第2章知識(shí)表示方法,重點(diǎn)掌握用狀態(tài)空間法、問(wèn)題歸約法、謂詞邏輯法、語(yǔ)義網(wǎng)絡(luò)法、框架表示法來(lái)描述問(wèn)題，解決問(wèn)題,2.1 狀態(tài)空間法,許多問(wèn)題求解方法是采用試探搜索方法的。也就是說(shuō)，這些方法是通過(guò)在某個(gè)可能的解空間內(nèi)尋找一個(gè)解來(lái)求解問(wèn)題的。這種基于解答空間的問(wèn)題表示和求解方法就是狀態(tài)空間法，它是以狀態(tài)和算符(operator)為基礎(chǔ)來(lái)表示和求解問(wèn)題的,2.1 狀態(tài)空間法,狀態(tài)空間法三要點(diǎn) (1) 狀態(tài)（state）：表示問(wèn)題解法中每一步問(wèn)題狀況的數(shù)據(jù)結(jié)構(gòu)； (2) 算符（operator）

3、：把問(wèn)題從一種狀態(tài)變換為另一種狀態(tài)的手段； (3) 狀態(tài)空間方法：基于解答空間的問(wèn)題表示和求解方法，它是以狀態(tài)和算符為基礎(chǔ)來(lái)表示和求解問(wèn)題的,2.1 狀態(tài)空間法,由上可知，對(duì)一個(gè)問(wèn)題的狀態(tài)描述，必須確定3件事： (1) 該狀態(tài)描述方式，特別是初始狀態(tài)描述； (2) 操作符集合及其對(duì)狀態(tài)描述的作用； (3) 目標(biāo)狀態(tài)描述的特性,例2：(分油問(wèn)題) 有A、B、C三個(gè)不帶刻度的瓶子，分別能裝8kg, 5kg和3kg油。如果A瓶裝滿油，B和C是空瓶，怎樣操作三個(gè)瓶，使A中的油平分兩份？(假設(shè)分油過(guò)程中不耗油,解：第一步： 定義問(wèn)題狀態(tài)的描述形式： 設(shè)Sk=(b,c)表示B瓶和C瓶中的油量的狀態(tài)。 其中

4、： b表示B瓶中的油量。 c表示C瓶中的油量。 初始狀態(tài)集：S=(0,0) 目標(biāo)狀態(tài)集：G=(4,0,第二步： 定義操作符： 操作：把瓶子倒?jié)M油，或把瓶子的油倒空。 f1：從A瓶往B瓶倒油，把B瓶倒?jié)M。 f2：從C瓶往B瓶倒油，把B瓶倒?jié)M。 f3：從A瓶往C瓶倒油，把C瓶倒?jié)M。 f4：從B瓶往C瓶倒油，把C瓶倒?jié)M。 f5：從B瓶往A瓶倒油，把B瓶倒空。 f6：從B瓶往C瓶倒油，把B瓶倒空。 f7：從C瓶往A瓶倒油，把C瓶倒空。 f8：從C瓶往B瓶倒油，把C瓶倒空,第三步： 求解過(guò)程,0,3,3,0,2,3,f1,f1,f1：從A瓶往B瓶倒油， 把B瓶倒?jié)M。 f2：從C瓶往B瓶倒油， 把B瓶倒?jié)M

5、。 f3：從A瓶往C瓶倒油， 把C瓶倒?jié)M。 f4：從B瓶往C瓶倒油， 把C瓶倒?jié)M。 f5：從B瓶往A瓶倒油， 把B瓶倒空。 f6：從B瓶往C瓶倒油， 把B瓶倒空。 f7：從C瓶往A瓶倒油， 把C瓶倒空。 f8：從C瓶往B瓶倒油， 把C瓶倒空,由上述狀態(tài)空間圖，可見(jiàn)從初始狀態(tài)(0,1)到目標(biāo)狀態(tài)(4,0)的任何一條通路都是問(wèn)題的一個(gè)解。其中： f1, f4, f7, f6, f1, f4, f7是算符最少的解之一,例：設(shè)有3個(gè)傳教士和3個(gè)野人來(lái)到河邊，打算乘一只船從右岸渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，那么野人就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全地把

6、所有人都渡過(guò)河去,解：第一步： 定義問(wèn)題狀態(tài)的描述形式： 設(shè)Sk=(M,C,B)表示傳教士和野人在河右岸的狀態(tài)。 其中： M表示傳教士在右岸的人數(shù)。 C表示野人在右岸的人數(shù)。 B用來(lái)表示船是不是在右岸。 (B=1表示在右岸，B=0表示在左岸)。 初始狀態(tài)集：S=(3,3,1) 目標(biāo)狀態(tài)集：G=(0,0,0,第二步：定義算符。 算符R(i, j)表示劃船將i個(gè)傳教士和j個(gè)野人送到左岸的操作。 算符L(i, j)表示劃船從左岸將i個(gè)傳教士和j個(gè)野人帶回右岸的操作。 由于過(guò)河的船每次最多載兩個(gè)人，所以i+j2。這樣定義的算符集F中只可能有如下10個(gè)算符。 F：R(1,0), R(2,0), R(1,

7、1), R(0,1), R(0,2) L(1,0), L(2,0), L(1,1), L(0,1), L(0,2,第三步：求解過(guò)程,1,1,0,2,2,1,3,1,1,0,2,0,3,0,0,R(2,0,L(2,0,R(1,1,L(1,1,L(0,1,R(0,1,L(2,0,R(2,0,2,2,0,3,3,1,3,2,1,3,2,0,3,1,0,L(0,2,R(0,2,R(0,1,L(0,1,L(1,0,R(1,0,L(0,1,R(0,1,L(1,1,R(1,1,L(0,2,R(0,2,1,1,1,0,0,0,0,1,0,0,1,1,0,2,1,R(0,1,L(1,0,L(0,1,R(0,1,

8、R(1,0,L(1,0,R(0,1,L(0,1,R(1,1,L(1,1,R(0,2,L(0,2,0,3,1,R(0,2,L(0,2,由上述狀態(tài)空間圖，可見(jiàn)從初始狀態(tài)(3,3,1)到目標(biāo)狀態(tài)(0,0,0)的任何一條通路都是問(wèn)題的一個(gè)解。 其中： R(1,1), L(1,0), R(0,2), L(0,1), R(2,0), L(1,1), R(2,0), L(0,1), R(0,2), L(1,0), R(1,1)是算符最少的解之一,2.2 問(wèn)題歸約法,問(wèn)題歸約法的概念 已知問(wèn)題的描述，通過(guò)一系列變換把此問(wèn)題最終變?yōu)橐粋€(gè)子問(wèn)題集合；這些子問(wèn)題的解可以直接得到，從而解決了初始問(wèn)題。 該方法也就是從

9、目標(biāo)(要解決的問(wèn)題)出發(fā)逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集合。這就是問(wèn)題歸約的實(shí)質(zhì),2.2 問(wèn)題歸約法,問(wèn)題歸約法的組成部分 （1）一個(gè)初始問(wèn)題描述； （2）一套把問(wèn)題變換為子問(wèn)題的操作符； （3）一套本原問(wèn)題描述,2.3 謂詞邏輯法,一階謂詞邏輯表示法適于表示確定性的知識(shí)。它具有自然性、精確性、嚴(yán)密性及易實(shí)現(xiàn)等特點(diǎn),2.3 謂詞邏輯法,用一階謂詞邏輯法表示知識(shí)的步驟如下： （1）定義謂詞及個(gè)體，確定每個(gè)謂詞及個(gè)體的確切含義。 （2）根據(jù)所要表達(dá)的事物或概念，為每個(gè)謂詞中的變?cè)x以特定的值。 （3）根據(jù)所要表達(dá)的知識(shí)的語(yǔ)義，用適當(dāng)?shù)倪B接符號(hào)將各

10、個(gè)謂詞連接起來(lái)，形成謂詞公式,例1：設(shè)有下列事實(shí)性知識(shí)： 張曉輝是一名計(jì)算機(jī)系的學(xué)生，但他不喜歡編程序。李曉鵬比他父親長(zhǎng)得高。 請(qǐng)用謂詞公式表示這些知識(shí)。 （1）定義謂詞及個(gè)體。 Computer(x):x是計(jì)算機(jī)系的學(xué)生。 Like(x,y):x喜歡y。 Higher(x,y):x比y長(zhǎng)得高。 這里涉及的個(gè)體有：張曉輝(zhangxh),編程序(programming), 李曉鵬(lixp)，以及函數(shù)father(lixp)表示李曉鵬的父親,第二步：將這些個(gè)體代入謂詞中，得到 Computer(zhangxh), Like(zhangxh, programming), Higher(lixp

11、, father(lixp) 第三步：根據(jù)語(yǔ)義，用邏輯聯(lián)結(jié)詞將它們聯(lián)結(jié)起來(lái)，就得到了表示上述知識(shí)的謂詞公式。 Computer(zhangxh) Like(zhangxh, programming) Higher(lixp, father(lixp,例2：設(shè)有下列語(yǔ)句，請(qǐng)用相應(yīng)的謂詞公式把它們表示出來(lái)： （1）人人愛(ài)勞動(dòng)。 （2）自然數(shù)都是大于零的整數(shù)。 （3）西安市的夏天既干燥又炎熱。 （4）喜歡讀三國(guó)演義的人必讀水滸。 （5）有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。 （6）他每天下午都去打籃球,解：（1）人人愛(ài)勞動(dòng)。 定義謂詞如下： Man(x):x是人。 Love(x

12、,y):x愛(ài)y。 （x)(Man(x)Love(x,勞動(dòng),2）自然數(shù)都是大于等于零的整數(shù)。 定義謂詞如下： N(x):x是自然數(shù)。 I(x):x是整數(shù)。 GZ(x):x大于等于零。 （x)(N(x)(GZ(x）I(x),3) 西安市的夏天既干燥又炎熱。 定義謂詞： SUMMER(x):x處于夏天。 DRY(x):x很干燥。 HOT(x):x很炎熱。 SUMMER(Xian)DRY(Xian)HOT(Xian,4）喜歡讀三國(guó)演義的人必讀水滸。 定義謂詞： MAN(x)：x是人。 LIKE(x,y)：x喜歡讀y。 (x)(MAN(x)LIKE(x, SANGUOYANYI) LIKE(x, SHU

13、IHU,5）有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。 定義謂詞： MAN(x):x是人。 LIKE(x,y): x喜歡y。 Meihua表示梅花，Juhua表示菊花， (x)(MAN(x) LIKE(x, Meihua) (y)(MAN(y) LIKE(y, Juhua) (z)(MAN(z) (LIKE(z, Meihua) LIKE(z,Juhua,6）他每天下午都去打籃球。 定義謂詞及個(gè)體： 設(shè)TIME(x):x是下午。 PLAY(x,y):x去打y， Liming表示李明， Basketball表示足球，則: （x）TIME(x)PLAY(Liming,Basket

14、ball,2.4 語(yǔ)義網(wǎng)絡(luò)法,語(yǔ)義網(wǎng)絡(luò)是1968年J.R.Quillian在研究人類(lèi)聯(lián)想記憶時(shí)提出的心理學(xué)模型,2.4 語(yǔ)義網(wǎng)絡(luò)法,語(yǔ)義網(wǎng)絡(luò)的概念 語(yǔ)義網(wǎng)絡(luò)是通過(guò)概念及其語(yǔ)義關(guān)系來(lái)表示知識(shí)的一種結(jié)構(gòu)化網(wǎng)絡(luò)圖，它由節(jié)點(diǎn)和弧線或鏈線組成，節(jié)點(diǎn)用來(lái)表示各種概念、事物、屬性、情況、動(dòng)作、狀態(tài)等，每個(gè)節(jié)點(diǎn)可以帶有若干個(gè)屬性，以表征其所代表的對(duì)象的特性?；【€用于表示節(jié)點(diǎn)間的關(guān)系，其上的標(biāo)注則表示被連接的兩個(gè)節(jié)點(diǎn)間的某種語(yǔ)義聯(lián)系或語(yǔ)義關(guān)系,2.4 語(yǔ)義網(wǎng)絡(luò)法,語(yǔ)義網(wǎng)絡(luò)表示知識(shí)的方法及步驟 （a）確定問(wèn)題中的所有對(duì)象以及各對(duì)象的屬性。 （b）確定所討論對(duì)象間的關(guān)系。 （c）語(yǔ)義網(wǎng)絡(luò)中，如果節(jié)點(diǎn)間的聯(lián)系是ISA

15、/AKO，則下層節(jié)點(diǎn)對(duì)上層節(jié)點(diǎn)的屬性具有繼承性。整理同一層節(jié)點(diǎn)的共同屬性，并抽出這些屬性，加入上層節(jié)點(diǎn)中，以免造成屬性信息的冗余,d）將各對(duì)象作為語(yǔ)義網(wǎng)絡(luò)的一個(gè)節(jié)點(diǎn)，而各對(duì)象間的關(guān)系作為網(wǎng)絡(luò)中各節(jié)點(diǎn)間的弧，連接形成語(yǔ)義網(wǎng)絡(luò)。節(jié)點(diǎn)可代表一個(gè)事物或一個(gè)具體概念，也可代表某種情況、事件或某一動(dòng)作。當(dāng)節(jié)點(diǎn)表示某種事件或某一動(dòng)作時(shí)，可以從該節(jié)點(diǎn)引出一組向外的弧，用于指出事件的因果或動(dòng)作的主體及客體,例1、用一個(gè)語(yǔ)義網(wǎng)絡(luò)表示下列命題。 樹(shù)和草都是植物； 樹(shù)和草是有根有葉的； 水草是草，且長(zhǎng)在水中； 果樹(shù)是樹(shù)，且會(huì)結(jié)果； 蘋(píng)果樹(shù)是果樹(shù)中的一種，它結(jié)蘋(píng)果,分析： 問(wèn)題涉及的對(duì)象有： 植物、樹(shù)、草、水草、果樹(shù)、

16、蘋(píng)果樹(shù) 各對(duì)象的屬性分別為： 樹(shù)和草的屬性：有根、有葉； 水草的屬性：長(zhǎng)在水中； 果樹(shù)的屬性：會(huì)結(jié)果； 蘋(píng)果樹(shù)的屬性：結(jié)蘋(píng)果,植物,蘋(píng)果樹(shù),水草,果樹(shù),草,樹(shù),AKO,AKO,AKO,AKO,AKO,有根,有葉,有根,有葉,會(huì)結(jié)果,結(jié)蘋(píng)果,長(zhǎng)在水中,例：用語(yǔ)義網(wǎng)絡(luò)表示下列知識(shí)： 獵狗是一種狗，而狗是一種動(dòng)物。狗除了動(dòng)物的有生命、能吃食物、有繁殖能力、能運(yùn)動(dòng)外，還有以下特點(diǎn)：身上有毛、有尾巴、四條腿；獵狗的特點(diǎn)是吃肉、奔跑速度快、能狩獵、個(gè)頭大；而獅子狗也是一種狗，它的特點(diǎn)是吃飼料、身體小、奔跑速度慢、不咬人、供觀賞,解題分析 （1）本知識(shí)涉及的對(duì)象有4個(gè)：獵狗、獅子狗、狗、動(dòng)物。獵狗和獅子狗都

17、是一種狗，除了它們本身的屬性外，具有狗的一般特性：身上有毛、有尾巴、四條腿。而狗是一種動(dòng)物，動(dòng)物所具有的屬性它也具有。 （2）獵狗與狗之間是一種類(lèi)屬關(guān)系，狗和動(dòng)物之間也是一種類(lèi)屬關(guān)系，它們都可以用AKO表示。 （3）整理各對(duì)象節(jié)點(diǎn)之間的屬性，使上層節(jié)點(diǎn)所具有的屬性不在下層節(jié)點(diǎn)中標(biāo)出。 （4）將各對(duì)象作為一個(gè)節(jié)點(diǎn)，而它們之間的關(guān)系作為弧，得到如下圖所示的語(yǔ)義網(wǎng)絡(luò),動(dòng)物,獅子狗,獵狗,狗,AKO,AKO,AKO,身上有毛,有尾巴,有四條腿,跑得快,能獰獵,有生命,吃飼料,能吃食物,有繁殖能力,能運(yùn)動(dòng),個(gè)頭大,吃肉,個(gè)頭小,跑得慢,不咬人,供觀賞,2.5 框架表示,1974年，由Minsky在“A

18、framework for representing knowledge”中提出。 框架是一種描述所論對(duì)象屬性的數(shù)據(jù)結(jié)構(gòu)。所論對(duì)象可以是一個(gè)事物、一個(gè)事件或者一個(gè)概念。一個(gè)框架由若干個(gè)“槽”組成，每個(gè)“槽”又可劃分為若干個(gè)“側(cè)面”。一個(gè)槽用于描述所論及對(duì)象的某一方面的屬性，一個(gè)側(cè)面用于描述相應(yīng)屬性的一個(gè)方面。槽和側(cè)面所具有的屬性值分別稱(chēng)為槽值和側(cè)面值。槽值可以是邏輯型或數(shù)字型的，具體的值可以是程序、條件、默認(rèn)值或是一個(gè)子框架,框架表示,用框架表示法表示知識(shí)的步驟如下： （1）分析待表達(dá)知識(shí)中的對(duì)象及其屬性，對(duì)框架中的槽進(jìn)行合理設(shè)置。 （2）對(duì)各對(duì)象間的各種聯(lián)系進(jìn)行考察。使用一些常用的名稱(chēng)或根據(jù)

19、具體需要定義一些表達(dá)聯(lián)系的槽名，來(lái)描述上、下層框架間的聯(lián)系。 （3）對(duì)各層對(duì)象的“槽”及“側(cè)面”進(jìn)行合理的組織安排，避免信息描述的重復(fù),例：用框架表示下述報(bào)道的地震事件 【虛擬新華社3月15日電】昨日，在云南玉溪地區(qū)發(fā)生地震，造成財(cái)產(chǎn)損失約10萬(wàn)元，統(tǒng)計(jì)部門(mén)如果需要詳細(xì)的損失數(shù)字，可電詢62332931。另?yè)?jù)專(zhuān)家認(rèn)為震級(jí)不會(huì)超過(guò)4級(jí)，并認(rèn)為地處無(wú)人區(qū)，不會(huì)造成人員傷亡。 提示：分析概括用下劃線標(biāo)出的要點(diǎn)，經(jīng)過(guò)概念化形成槽（slot）、側(cè)面（facet）值。特別要注意，“值”（value）、“默認(rèn)值”（default）、“如果需要值”（if-needed）、“如果附加值”（if-added）的區(qū)

20、別與應(yīng)用，建議采用格式如下，不用的側(cè)面值可刪,解： 第一步：確定框架的名字和框架的槽。 本報(bào)道中，涉及地震的發(fā)生時(shí)間、地點(diǎn)、財(cái)產(chǎn)損失、傷亡人數(shù)、震級(jí)大小等屬性，所以，可將時(shí)間、地點(diǎn)、震級(jí)、傷亡人數(shù)、財(cái)產(chǎn)損失等作為槽名。 第二步：分析本報(bào)道中各對(duì)象間的關(guān)系。 由于報(bào)道中只涉及地震一件事，所以該步可省略,第3章搜索推理技術(shù),重點(diǎn)掌握一般圖搜索策略和消解原理，掌握各種搜索方法和產(chǎn)生式系統(tǒng)原理，了解規(guī)則演繹系統(tǒng)的基本原理，對(duì)系統(tǒng)組織技術(shù)、不確定性推理和非單調(diào)推理等高級(jí)推理技術(shù)作一般性了解,第3章搜索推理技術(shù),從問(wèn)題表示到問(wèn)題的解決，有一個(gè)求解的過(guò)程。而實(shí)現(xiàn)求解的過(guò)程，采用的基本方法包括搜索和推理,第3

21、章搜索推理技術(shù),和搜索相對(duì)應(yīng)的知識(shí)表示法一般有兩種： 狀態(tài)空間法：（S，F(xiàn)，G） 與或圖表示法：基于一種分解與變換的思想，利用樹(shù)狀結(jié)構(gòu)對(duì)復(fù)雜問(wèn)題進(jìn)行表示，使復(fù)雜問(wèn)題簡(jiǎn)單化,第3章搜索推理技術(shù),圖搜索策略是一種在圖中尋找路徑的方法。 搜索種類(lèi)： 盲目搜索：只按預(yù)先規(guī)定的搜索控制策略進(jìn)行搜索。 啟發(fā)式搜索：根據(jù)問(wèn)題本身的特性或搜索過(guò)程中產(chǎn)生的一些信息來(lái)不斷改變和調(diào)整搜索的方向,圖搜索過(guò)程框圖,3.2盲目搜索,盲目搜索又叫做無(wú)信息搜索，一般只適用于求解比較簡(jiǎn)單的問(wèn)題。寬度優(yōu)先搜索和深度優(yōu)先搜索，屬于盲目搜索方法,3.2.1寬度優(yōu)先搜索,搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，如左圖所示。從圖可見(jiàn)，

22、這種搜索是逐層進(jìn)行的；在對(duì)下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn),s,L,O,M,F,P,Q,N,F,F,F,例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹(shù)，這個(gè)問(wèn)題就是要把初始棋局變?yōu)槿缬覉D所示的目標(biāo)棋局問(wèn)題,3.2.2 深度優(yōu)先搜索,分析深度優(yōu)先搜索示意圖可看出，在深度優(yōu)先搜索中，我們首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。深度相等的節(jié)點(diǎn)可以任意排列。我們定義節(jié)點(diǎn)的深度如下：(1) 起始節(jié)點(diǎn)(即根節(jié)點(diǎn))的深度為0。(2) 任何其它節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)深度加上1,3.2.2 深度優(yōu)先搜索,有界深度優(yōu)先搜索 給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度深度界限。 有界深度優(yōu)先搜索過(guò)程是沿著一

23、條路徑進(jìn)行下去，直到深度界限為止，然后再考慮只有最后一步有差別的相同深度或較淺深度可供選擇的路徑，接著再考慮最后兩步有差別的那些路徑，等等,3.2.3 等代價(jià)搜索,寬度優(yōu)先搜索的推廣 用來(lái)解決從起始狀態(tài)至目標(biāo)狀態(tài)的具有最小代價(jià)的路徑問(wèn)題。 從起始節(jié)點(diǎn)S到任一節(jié)點(diǎn)i的路徑代價(jià)記為g(i)。 從節(jié)點(diǎn)i到它的后繼節(jié)點(diǎn)j的連接弧線代價(jià)記為c(i，j)； 則節(jié)點(diǎn)j的路徑代價(jià)為g(j)=g(i)+c(i,j)。 待擴(kuò)展的節(jié)點(diǎn)是路徑代價(jià)最小的節(jié)點(diǎn),3.3 啟發(fā)式搜索,盲目搜索的不足：效率低，耗費(fèi)過(guò)多的計(jì)算空間與時(shí)間。 分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價(jià)搜索算法,其主要的差別是OPEN表中待擴(kuò)展節(jié)

24、點(diǎn)的順序問(wèn)題。人們就試圖找到一種方法用于排列待擴(kuò)展節(jié)點(diǎn)的順序，即選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展，那么，搜索效率將會(huì)大為提高。 啟發(fā)信息：進(jìn)行搜索技術(shù)一般需要某些有關(guān)具體問(wèn)題領(lǐng)域的特性的信息，把此種信息叫做啟發(fā)信息。 把利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索方法,3.3 啟發(fā)式搜索,啟發(fā)式搜索策略 啟發(fā)信息用于決定要擴(kuò)展的下一個(gè)節(jié)點(diǎn)，以免象在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地?cái)U(kuò)展。 這種搜索總是選擇“最有希望”的節(jié)點(diǎn)作為下一個(gè)被擴(kuò)展的節(jié)點(diǎn)。這種搜索叫做有序搜索(ordered search,3.2.1 有序搜索,有序搜索又稱(chēng)為最好優(yōu)先搜索，它總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。 估價(jià)函數(shù)f的

25、確定：一個(gè)節(jié)點(diǎn)的希望程度越大，則其f值越小。為此，被選為擴(kuò)展的節(jié)點(diǎn)，是估價(jià)函數(shù)最小的節(jié)點(diǎn)。 f是從起始節(jié)點(diǎn)約束地通過(guò)節(jié)點(diǎn)n而到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑上的一個(gè)估算代價(jià),3.3.1 有序搜索,寬度優(yōu)先搜索、等代價(jià)搜索和深度優(yōu)先搜索統(tǒng)統(tǒng)是有序搜索技術(shù)的特例。 對(duì)于寬度優(yōu)先搜索，我們選擇f(i)作為節(jié)點(diǎn)i的深度。對(duì)于等代價(jià)搜索，f(i)是從起始節(jié)點(diǎn)至節(jié)點(diǎn)i這段路徑的代價(jià),3.3.2 A*算法,A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。 估價(jià)函數(shù)f： f(n)=g(n)+h(n) g(n)：就是到目前為止用搜索算法找到的從S到n的最小路徑代價(jià)。 h(n)：依賴(lài)于有關(guān)問(wèn)題的領(lǐng)域的啟發(fā)信息

26、。 從節(jié)點(diǎn)n到某目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)的估計(jì),例：八數(shù)碼難題,解：采用估價(jià)函數(shù)f(n)=d(n)+W(n) 其中：d(n)是搜索樹(shù)中節(jié)點(diǎn)n的深度； W(n)用來(lái)計(jì)算對(duì)應(yīng)于節(jié)點(diǎn)n的數(shù)據(jù)庫(kù)中錯(cuò)放的棋子個(gè)數(shù)。 因此，起始節(jié)點(diǎn)棋局的f值等于0+3=3,Sg,S0,3,4,4,5,5,5,6,4,6,4,4,6,3.4 消解原理,重點(diǎn)掌握子句集的求解步驟和消解反演過(guò)程，掌握消解推理的規(guī)則,3.4.1 子句集的求取,例、將下列謂詞演算公式化為一個(gè)子句集 (x)P(x)(y)P(y) P(f(x,y)(y)Q(x,y) P(y,1) (x)P(x)(y)P(y) P(f(x,y)(y)Q(x,y) P

27、(y,2) (x)P(x)(y)P(y) P(f(x,y) (y)Q(x,y) P(y) (x)P(x)(y)P(y) P(f(x,y) (y)Q(x,y) P(y,4) (x)P(x)(y)P(y) P(f(x,y) Q(x,g(x) P(g(x) 式中w=g(x)為一個(gè)Skolem函數(shù),5) (x)(y)P(x) P(y) P(f(x,y) Q(x,g(x) P(g(x,3) (x)P(x)(y)P(y) P(f(x,y) (w)Q(x,w) P(w,6) (x)(y)P(x)P(y) P(f(x,y) P(x) Q(x,g(x)P(x) P(g(x,8) P(x)P(y) P(f(x,y

28、) P(x) Q(x,g(x) P(x) P(g(x,9) 更改變量名稱(chēng)，在上述第（8）步的3個(gè)子句中，分別以x1,x2,x3代替變量x。這種更改變量名稱(chēng)的過(guò)程，有時(shí)稱(chēng)為變量分離標(biāo)準(zhǔn)化。于是，可以得到下列子句集： P(x1)P(y) P(f(x1,y) P(x2) Q(x2,g(x2) P(x3) P(g(x3,7) P(x)P(y) P(f(x,y) P(x) Q(x,g(x)P(x) P(g(x,3.4.2消解反演求解過(guò)程,1、消解反演 給出一個(gè)公式集S和目標(biāo)公式L，通過(guò)反證或反演來(lái)求證目標(biāo)公式L，其證明步驟如下： (1)否定L，得L； (2)把L添加到S中去； (3)把新產(chǎn)生的集合L，S

29、化成子句集； (4)應(yīng)用消解原理，力圖推導(dǎo)出一個(gè)表示矛盾的空子句N(xiāo)IL,例1、判斷下列子句集中哪些是不可滿足的 分析：子句集中各子句間的關(guān)系是合取關(guān)系，因此只要有一個(gè)子句不可滿足，則子句集就是不可滿足的。 (1)NIL(空子句)是不可滿足的。 (2)在子句集中選擇合適的子句對(duì)其進(jìn)行消解，若能推出空子句，就說(shuō)明子句S是不可滿足的,1) S=PQ，Q，P，P 對(duì)子句集S進(jìn)行歸結(jié)推理： (1) PQ (2) Q (3)P (4) P (5) NIL (3)(4)歸結(jié) 故該子句集是不可滿足的,2) S=P(x)Q(f(x),a)， P(h(y)Q(f(h(y),a)P(z) 解：因子句集中無(wú)互補(bǔ)對(duì)，故

30、在子句集S中不存在空子句，故S為可滿足的,例2 證明(x)(P(x)(Q(x)R(x) (x) (P(x)T(x) (x)(T(x)R(x) 證明：第一步：先對(duì)結(jié)論否定并與前提合并得到謂詞公式G。 G=(x)(P(x)(Q(x)R(x) (x) (P(x)T(x) (x)(T(x)R(x) 第二步：將公式G化為子句集。 可將G看作是三項(xiàng)的合取，對(duì)每一項(xiàng)分別求子句集,G1：(x)(P(x)(Q(x)R(x) = (x)(P(x) (Q(x)R(x) =(x)(P(x)Q(x) (P(x)R(x) 所以S1=P(x1)Q(x1), P(x2)R(x2) G2: (x) (P(x)T(x) 所以S2

31、= P(a), T(a) B:(x)(T(x)R(x) =(x)(T(x)R(x) 所以SB=T(x)R(x) 從而求得公式G的子句集： S=S1S2SB= P(x1)Q(x1), P(x2)R(x2), P(a), T(a), T(x3)R(x3,第三步：例用消解原理，對(duì)子句集S進(jìn)行消解,P(x2)R(x2,P(a,R(a,T(x3)R(x3,T(a,1=a/x2,T(a,2=a/x3,NIL,由此得出子句集S是不可滿足的，因此公式G也是不可滿足的。從而命題得證,例3 某公司招聘人員，A、B、C三人應(yīng)試，經(jīng)面試后，公司有如下想法： (1) 三人中至少錄用一人； (2) 如果錄用A而不錄用B，

32、則一定錄用C； (3) 如果錄用B，則一定錄用C。 求證：公司一定錄取C。 證： 定義：P(x)表示錄用x。 則前提為 (1) P(A)P(B)P(C) (2) (P(A)(P(B)=P(C) (3) P(B)=P(C) 則結(jié)論為 P(C,將前提化為子句集： (1) P(A)P(B)P(C) (2) P(A)P(B)P(C) (3) P(B)P(C) 將結(jié)論否定并化為子句集： (4) P(C) 利用消解原理，對(duì)子句集進(jìn)行消解,故證得結(jié)論：公司一定錄取C,2、反演求解過(guò)程 步驟： (1)把已知前提用謂詞公式表示出來(lái)，并化為相應(yīng)的子句集S。 (2)把待求解的問(wèn)題也用謂詞公式表示出來(lái)，然后把它的否定

33、與謂詞ANSWER構(gòu)成析取式。 (3)把第(2)步得到的析取式化為子句集，并入子句集S中，得到子句集S。 (4)對(duì)子句集S應(yīng)用消解原理進(jìn)行消解。 (5)若得答案ANSWER，則答案就在ANSWER中,例1：應(yīng)用消解反演求解如下問(wèn)題： “如果無(wú)論約翰(John)到哪里去，菲多(Fido)也就去那里，那么如果約翰在學(xué)校里，菲多在哪里呢?” 解：定義謂詞：AT（x,y）表示x在y那里。 則前提為： (x)(AT(JOHN,x) AT(FIDO,x) 和 AT(JOHN, SCHOOL) 目標(biāo)公式： (x)AT(FIDO,x) 目標(biāo)公式否定為： (x)(AT(FIDO,x) 其子句形為：AT(FIDO

34、,x,對(duì)本例應(yīng)用消解反演過(guò)程： （1）目標(biāo)公式否定的子句形為： AT(FIDO,x) 將它與謂詞ANSWER構(gòu)成析取式： AT(FIDO,x)ANSWER(FIDO,x) （2）用下圖的反演樹(shù)進(jìn)行消解，并在根部得到子句： ANSWER(FIDO,SCHOOL,例2 某公司招聘人員，A、B、C三人應(yīng)試，經(jīng)面試后，公司有如下想法： (1) 三人中至少錄用一人； (2) 如果錄用A而不錄用B，則一定錄用C； (3) 如果錄用B，則一定錄用C。 求公司錄用誰(shuí)？ 解： 定義：P(x)表示錄用x。 則前提為 (1) P(A)P(B)P(C) (2) (P(A)(P(B)=P(C) (3) P(B)=P(C

35、) 則結(jié)論為 P(x,將前提化為子句集：(1) P(A)P(B)P(C) (2) P(A)P(B)P(C) (3) P(B)P(C) 將結(jié)論否定與謂詞ANSWER構(gòu)成析取式： (4) P(x)ANSWER(x) 利用消解原理，對(duì)子句集進(jìn)行消解,可見(jiàn)公司一定錄取C,例3已知（1）王是李的老師 （2）李是張的同學(xué) （3）如果x與y是同學(xué)，則x的老師也是y的老師。 求：張的老師是誰(shuí),解：令T(x,y):x是y的老師； C(x,y)：x是y的同學(xué),則 已知的三個(gè)事實(shí)可解釋為下列公式集 T(Wang,Li) C(Li,Zhang) (x)(y)(z)C(x,y)T(z,x)=T(z,y) 目標(biāo)公式：(x

36、)T(x,Zhang,將上述事實(shí)化為子句集： T(Wang,Li) C(Li,Zhang) C(x,y)T(z,x)T(z,y) 目標(biāo)公式否定的子句形為： T(x,Zhang) 將它與謂詞ANSWER構(gòu)成析取式： T(w,Zhang)ANSWER(w,Zhang,用下圖的反演樹(shù)進(jìn)行消解，并在根部得到子句,C(x,y)T(z,x)T(z,y,T(Wang,Li,C(Li,y)T(Wang,y,C(Li,Zhang,T(Wang,Zhang,1=Wang/z,Li/x,T(w,Zhang)ANSWER(w,Zhang,2=Zhang/y,ANSWER(Wang,Zhang,3=Wang/w,3.5 產(chǎn)生式系統(tǒng),1、產(chǎn)生式系統(tǒng)的組成 產(chǎn)生式系統(tǒng)由3個(gè)部分組成，即總數(shù)據(jù)庫(kù)(或全局?jǐn)?shù)據(jù)庫(kù))、產(chǎn)