人工智能及其應(yīng)用

人工智能ppt第1章緒論

1、重點(diǎn)掌握人工智能的幾種定義。2、掌握目前人工智能的三個(gè)主要學(xué)派及其認(rèn)知觀。3、一般了解人工智能的主要研究范圍和應(yīng)用領(lǐng)域。人工智能ppt定義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)。人工智能ppt人工智能的三大學(xué)派及其認(rèn)知觀：(1)符號(hào)主義認(rèn)為人工智能起源于數(shù)理邏輯。(2)連接主義認(rèn)為人工智能起源于仿生學(xué)，特別是對(duì)人腦模型的研究。(3)行為主義認(rèn)為人工智能起源于控制論。人工智能ppt第2章知識(shí)表示方法重點(diǎn)掌握用狀態(tài)空間法、問(wèn)題歸約法、謂詞邏輯法、語(yǔ)義網(wǎng)絡(luò)法、框架表示法來(lái)描述問(wèn)題，解決問(wèn)題；人工智能ppt2.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)題的。人工智能ppt2.1狀態(tài)空間法狀態(tài)空間法三要點(diǎn)

(1)狀態(tài)（state）：表示問(wèn)題解法中每一步問(wèn)題狀況的數(shù)據(jù)結(jié)構(gòu)；

(2)算符（operator）：把問(wèn)題從一種狀態(tài)變換為另一種狀態(tài)的手段；

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

b表示B瓶中的油量。

c表示C瓶中的油量。初始狀態(tài)集：S={(0,0)}

目標(biāo)狀態(tài)集：G={(4,0)}人工智能ppt第二步：定義操作符：

操作：把瓶子倒?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瓶倒空。人工智能ppt第三步：求解過(guò)程：0,33,02,3f1f10,05,31,31,00,15,13,34,04,35,25,30,00,20,32,05,0f1f3f4f7f8f6f5f3f1f4f7f5f3f2f8f3f8f3f2f5f8f3f8f7f7f6f1f4f7f4f5f1f7f1f1f1f7f5f5f7f5f6f7f5f1f3f3f1：從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瓶倒空。人工智能ppt

由上述狀態(tài)空間圖，可見(jiàn)從初始狀態(tài)(0,1)到目標(biāo)狀態(tài)(4,0)的任何一條通路都是問(wèn)題的一個(gè)解。其中：{f1,f4,f7,f6,f1,f4,f7}是算符最少的解之一。

人工智能ppt例：設(shè)有3個(gè)傳教士和3個(gè)野人來(lái)到河邊，打算乘一只船從右岸渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，那么野人就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全地把所有人都渡過(guò)河去？人工智能ppt解：第一步：定義問(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)}人工智能ppt第二步：定義算符。算符R(i,j)表示劃船將i個(gè)傳教士和j個(gè)野人送到左岸的操作。算符L(i,j)表示劃船從左岸將i個(gè)傳教士和j個(gè)野人帶回右岸的操作。由于過(guò)河的船每次最多載兩個(gè)人，所以i+j≤2。這樣定義的算符集F中只可能有如下10個(gè)算符。F：R(1,0),R(2,0),R(1,1),R(0,1),R(0,2)L(1,0),L(2,0),L(1,1),L(0,1),L(0,2)人工智能ppt第三步：求解過(guò)程。1,1,02,2,13,1,10,2,03,0,0R(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,03,3,13,2,13,2,03,1,0L(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,10,0,00,1,00,1,10,2,1R(0,1)L(1,0)L(0,1)R(0,1)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,1R(0,2)L(0,2)人工智能ppt

由上述狀態(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)}是算符最少的解之一。人工智能ppt2.2問(wèn)題歸約法問(wèn)題歸約法的概念已知問(wèn)題的描述，通過(guò)一系列變換把此問(wèn)題最終變?yōu)橐粋€(gè)子問(wèn)題集合；這些子問(wèn)題的解可以直接得到，從而解決了初始問(wèn)題。該方法也就是從目標(biāo)(要解決的問(wèn)題)出發(fā)逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集合。這就是問(wèn)題歸約的實(shí)質(zhì)。人工智能ppt2.2問(wèn)題歸約法問(wèn)題歸約法的組成部分（1）一個(gè)初始問(wèn)題描述；（2）一套把問(wèn)題變換為子問(wèn)題的操作符；（3）一套本原問(wèn)題描述。

人工智能ppt2.3謂詞邏輯法一階謂詞邏輯表示法適于表示確定性的知識(shí)。它具有自然性、精確性、嚴(yán)密性及易實(shí)現(xiàn)等特點(diǎn)。人工智能ppt2.3謂詞邏輯法用一階謂詞邏輯法表示知識(shí)的步驟如下：（1）定義謂詞及個(gè)體，確定每個(gè)謂詞及個(gè)體的確切含義。（2）根據(jù)所要表達(dá)的事物或概念，為每個(gè)謂詞中的變?cè)x以特定的值。（3）根據(jù)所要表達(dá)的知識(shí)的語(yǔ)義，用適當(dāng)?shù)倪B接符號(hào)將各個(gè)謂詞連接起來(lái)，形成謂詞公式。人工智能ppt例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)表示李曉鵬的父親。人工智能ppt第二步：將這些個(gè)體代入謂詞中，得到Computer(zhangxh),~Like(zhangxh,programming),Higher(lixp,father(lixp))第三步：根據(jù)語(yǔ)義，用邏輯聯(lián)結(jié)詞將它們聯(lián)結(jié)起來(lái)，就得到了表示上述知識(shí)的謂詞公式。Computer(zhangxh)∧~Like(zhangxh,programming)Higher(lixp,father(lixp))人工智能ppt例2：設(shè)有下列語(yǔ)句，請(qǐng)用相應(yīng)的謂詞公式把它們表示出來(lái)：（1）人人愛(ài)勞動(dòng)。（2）自然數(shù)都是大于零的整數(shù)。（3）西安市的夏天既干燥又炎熱。（4）喜歡讀《三國(guó)演義》的人必讀《水滸》。

（5）有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。（6）他每天下午都去打籃球。人工智能ppt解：（1）人人愛(ài)勞動(dòng)。定義謂詞如下：

Man(x):x是人。

Love(x,y):x愛(ài)y。（x)(Man(x)→Love(x,勞動(dòng)））人工智能ppt（2）自然數(shù)都是大于等于零的整數(shù)。定義謂詞如下：

N(x):x是自然數(shù)。

I(x):x是整數(shù)。

GZ(x):x大于等于零。（x)(N(x)→(GZ(x）∧I(x))）人工智能ppt(3)西安市的夏天既干燥又炎熱。定義謂詞：

SUMMER(x):x處于夏天。

DRY(x):x很干燥。

HOT(x):x很炎熱。SUMMER(Xi’an)→DRY(Xi’an)∧HOT(Xi’an)人工智能ppt（4）喜歡讀《三國(guó)演義》的人必讀《水滸》。定義謂詞：

MAN(x)：x是人。

LIKE(x,y)：x喜歡讀y。

(x)(MAN(x)∧LIKE(x,《SANGUOYANYI》)→LIKE(x,《SHUIHU》))人工智能ppt（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)))人工智能ppt（6）他每天下午都去打籃球。定義謂詞及個(gè)體：設(shè)TIME(x):x是下午。

PLAY(x,y):x去打y，

Liming表示李明，

Basketball表示足球，則:（x）TIME(x)PLAY(Liming,Basketball)

人工智能ppt2.4語(yǔ)義網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)是1968年J.R.Quillian在研究人類(lèi)聯(lián)想記憶時(shí)提出的心理學(xué)模型。人工智能ppt2.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)系。人工智能ppt2.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/AKO，則下層節(jié)點(diǎn)對(duì)上層節(jié)點(diǎn)的屬性具有繼承性。整理同一層節(jié)點(diǎn)的共同屬性，并抽出這些屬性，加入上層節(jié)點(diǎn)中，以免造成屬性信息的冗余。人工智能ppt（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)作的主體及客體。人工智能ppt例1、用一個(gè)語(yǔ)義網(wǎng)絡(luò)表示下列命題。樹(shù)和草都是植物；樹(shù)和草是有根有葉的；水草是草，且長(zhǎng)在水中；果樹(shù)是樹(shù)，且會(huì)結(jié)果；蘋(píng)果樹(shù)是果樹(shù)中的一種，它結(jié)蘋(píng)果。人工智能ppt分析：?jiǎn)栴}涉及的對(duì)象有：植物、樹(shù)、草、水草、果樹(shù)、蘋(píng)果樹(shù)各對(duì)象的屬性分別為：樹(shù)和草的屬性：有根、有葉；水草的屬性：長(zhǎng)在水中；果樹(shù)的屬性：會(huì)結(jié)果；蘋(píng)果樹(shù)的屬性：結(jié)蘋(píng)果。人工智能ppt植物蘋(píng)果樹(shù)水草果樹(shù)草樹(shù)AKOAKOAKOAKOAKO有根有葉有根有葉會(huì)結(jié)果結(jié)蘋(píng)果長(zhǎng)在水中人工智能ppt例：用語(yǔ)義網(wǎng)絡(luò)表示下列知識(shí)：獵狗是一種狗，而狗是一種動(dòng)物。狗除了動(dòng)物的有生命、能吃食物、有繁殖能力、能運(yùn)動(dòng)外，還有以下特點(diǎn)：身上有毛、有尾巴、四條腿；獵狗的特點(diǎn)是吃肉、奔跑速度快、能狩獵、個(gè)頭大；而獅子狗也是一種狗，它的特點(diǎn)是吃飼料、身體小、奔跑速度慢、不咬人、供觀賞。人工智能ppt解題分析（1）本知識(shí)涉及的對(duì)象有4個(gè)：獵狗、獅子狗、狗、動(dòng)物。獵狗和獅子狗都是一種狗，除了它們本身的屬性外，具有狗的一般特性：身上有毛、有尾巴、四條腿。而狗是一種動(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ò)。人工智能ppt動(dòng)物獅子狗獵狗狗AKOAKOAKO身上有毛有尾巴有四條腿跑得快能獰獵有生命吃飼料能吃食物有繁殖能力能運(yùn)動(dòng)個(gè)頭大吃肉個(gè)頭小跑得慢不咬人供觀賞人工智能ppt2.5框架表示1974年，由Minsky在“Aframeworkforrepresentingknowledge”中提出?？蚣苁且环N描述所論對(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è)子框架。人工智能ppt框架表示用框架表示法表示知識(shí)的步驟如下：（1）分析待表達(dá)知識(shí)中的對(duì)象及其屬性，對(duì)框架中的槽進(jìn)行合理設(shè)置。（2）對(duì)各對(duì)象間的各種聯(lián)系進(jìn)行考察。使用一些常用的名稱(chēng)或根據(jù)具體需要定義一些表達(dá)聯(lián)系的槽名，來(lái)描述上、下層框架間的聯(lián)系。（3）對(duì)各層對(duì)象的“槽”及“側(cè)面”進(jìn)行合理的組織安排，避免信息描述的重復(fù)。人工智能ppt例：用框架表示下述報(bào)道的地震事件【虛擬新華社3月15日電】昨日，在云南玉溪地區(qū)發(fā)生地震，造成財(cái)產(chǎn)損失約10萬(wàn)元，統(tǒng)計(jì)部門(mén)如果需要詳細(xì)的損失數(shù)字，可電詢(xún)。另?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ū)別與應(yīng)用，建議采用格式如下，不用的側(cè)面值可刪。

人工智能pptFrame地震Slot1：Value：Default：If-needed：If-added：Slot2：Value：Default：If-needed：If-added：Slot3：Value：Default：If-needed：If-added：人工智能ppt解：第一步：確定框架的名字和框架的槽。本報(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)道中只涉及地震一件事，所以該步可省略。

人工智能ppt框架名：＜地震1＞時(shí)間：3月14日地點(diǎn)：云南玉溪地區(qū)震級(jí)：專(zhuān)家經(jīng)驗(yàn)值：≤4級(jí)準(zhǔn)確值：NIL傷亡人數(shù)：專(zhuān)家經(jīng)驗(yàn)值：0

財(cái)產(chǎn)損失：大約損失：10萬(wàn)元if-needed：ASK（電詢(xún)）人工智能ppt第3章搜索推理技術(shù)

重點(diǎn)掌握一般圖搜索策略和消解原理，掌握各種搜索方法和產(chǎn)生式系統(tǒng)原理，了解規(guī)則演繹系統(tǒng)的基本原理，對(duì)系統(tǒng)組織技術(shù)、不確定性推理和非單調(diào)推理等高級(jí)推理技術(shù)作一般性了解。人工智能ppt第3章搜索推理技術(shù)

從問(wèn)題表示到問(wèn)題的解決，有一個(gè)求解的過(guò)程。而實(shí)現(xiàn)求解的過(guò)程，采用的基本方法包括搜索和推理。人工智能ppt第3章搜索推理技術(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)單化。人工智能ppt第3章搜索推理技術(shù)圖搜索策略是一種在圖中尋找路徑的方法。搜索種類(lèi)：盲目搜索：只按預(yù)先規(guī)定的搜索控制策略進(jìn)行搜索。啟發(fā)式搜索：根據(jù)問(wèn)題本身的特性或搜索過(guò)程中產(chǎn)生的一些信息來(lái)不斷改變和調(diào)整搜索的方向。人工智能ppt圖搜索過(guò)程框圖開(kāi)始把S放入OPEN表OPEN為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN移至CLOSED表n為目標(biāo)節(jié)點(diǎn)？把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針修改指針?lè)较蛑嘏臤PEN表失敗成功是是否否人工智能ppt3.2盲目搜索

盲目搜索又叫做無(wú)信息搜索，一般只適用于求解比較簡(jiǎn)單的問(wèn)題。寬度優(yōu)先搜索和深度優(yōu)先搜索，屬于盲目搜索方法。人工智能ppt3.2.1

寬度優(yōu)先搜索搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，如左圖所示。

從圖可見(jiàn)，這種搜索是逐層進(jìn)行的；在對(duì)下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。

sLOMFPQNFFF人工智能ppt例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹(shù)，這個(gè)問(wèn)題就是要把初始棋局變?yōu)槿缬覉D所示的目標(biāo)棋局問(wèn)題：

人工智能ppt3.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。

人工智能ppt3.2.2深度優(yōu)先搜索有界深度優(yōu)先搜索給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度——深度界限。有界深度優(yōu)先搜索過(guò)程是沿著一條路徑進(jìn)行下去，直到深度界限為止，然后再考慮只有最后一步有差別的相同深度或較淺深度可供選擇的路徑，接著再考慮最后兩步有差別的那些路徑，等等。

人工智能ppt3.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)。人工智能ppt3.3啟發(fā)式搜索盲目搜索的不足：效率低，耗費(fèi)過(guò)多的計(jì)算空間與時(shí)間。分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價(jià)搜索算法,其主要的差別是OPEN表中待擴(kuò)展節(jié)點(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ā)式搜索方法。人工智能ppt3.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)。這種搜索叫做有序搜索(orderedsearch)。人工智能ppt3.2.1有序搜索有序搜索又稱(chēng)為最好優(yōu)先搜索，它總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。估價(jià)函數(shù)f的確定：一個(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à)。人工智能ppt3.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à)。人工智能ppt3.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ā)信息。

從節(jié)點(diǎn)n到某目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)的估計(jì)。人工智能ppt例：八數(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。人工智能pptSgS0344555646446人工智能ppt3.4消解原理重點(diǎn)掌握子句集的求解步驟和消解反演過(guò)程，掌握消解推理的規(guī)則。人工智能ppt3.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(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)]}}人工智能ppt(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))]}人工智能ppt(8)~P(x)~P(y)P(f(x,y))~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))]人工智能ppt3.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｝化成子句集；

(4)應(yīng)用消解原理，力圖推導(dǎo)出一個(gè)表示矛盾的空子句N(xiāo)IL。

人工智能ppt例1、判斷下列子句集中哪些是不可滿(mǎn)足的分析：子句集中各子句間的關(guān)系是合取關(guān)系，因此只要有一個(gè)子句不可滿(mǎn)足，則子句集就是不可滿(mǎn)足的。

(1)NIL(空子句)是不可滿(mǎn)足的。

(2)在子句集中選擇合適的子句對(duì)其進(jìn)行消解，若能推出空子句，就說(shuō)明子句S是不可滿(mǎn)足的。人工智能ppt(1)S={～P∨Q，～Q，P，～P}

對(duì)子句集S進(jìn)行歸結(jié)推理：

(1)～P∨Q(2)～Q

(3)P(4)～P(5)NIL(3)(4)歸結(jié)故該子句集是不可滿(mǎn)足的。人工智能ppt(2)S={～P(x)∨Q(f(x),a)，～P(h(y))∨Q(f(h(y)),a)∨～P(z)}

解：因子句集中無(wú)互補(bǔ)對(duì)，故在子句集S中不存在空子句，故S為可滿(mǎn)足的。人工智能ppt例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)分別求子句集。人工智能ppt

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={P(a),T(a)}

～B:～(x)(T(x)∧R(x))=(x)(～T(x)∨～R(x))所以S～B={～T(x)∨～R(x)}從而求得公式G的子句集：

S=S1∪S2∪S～B={～P(x1)∨Q(x1),～P(x2)∨R(x2),P(a),T(a),～T(x3)∨～R(x3)}人工智能ppt

第三步：例用消解原理，對(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是不可滿(mǎn)足的，因此公式G也是不可滿(mǎn)足的。從而命題得證。人工智能ppt例3某公司招聘人員，A、B、C三人應(yīng)試，經(jīng)面試后，公司有如下想法：

(1)三人中至少錄用一人；

(2)如果錄用A而不錄用B，則一定錄用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)人工智能ppt

將前提化為子句集：

(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)行消解：P(A)∨P(B)∨P(C)～P(A)∨P(B)∨P(C)P(B)∨P(C)～P(B)∨P(C)P(C)～P(C)NIL故證得結(jié)論：公司一定錄取C人工智能ppt2、反演求解過(guò)程步驟：

(1)把已知前提用謂詞公式表示出來(lái)，并化為相應(yīng)的子句集S。

(2)把待求解的問(wèn)題也用謂詞公式表示出來(lái)，然后把它的否定與謂詞ANSWER構(gòu)成析取式。

(3)把第(2)步得到的析取式化為子句集，并入子句集S中，得到子句集S’。

(4)對(duì)子句集S’應(yīng)用消解原理進(jìn)行消解。

(5)若得答案ANSWER，則答案就在ANSWER中。人工智能ppt例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,x)人工智能ppt對(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)～AT(FIDO,x)∨ANSWER(FIDO,x)～AT(JOHN,y)∨AT(FIDO,y)～AT(JOHN,x)∨ANSWER(FIDO,x)AT(JOHN,SCHOOL)ANSWER(FIDO,SCHOOL)1={x/y}2={SCHOOL/x}人工智能ppt例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)

則結(jié)論為

P(x)人工智能ppt將前提化為子句集：(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)行消解：P(A)∨P(B)∨P(C)～P(A)∨P(B)∨P(C)P(B)∨P(C)～P(B)∨P(C)P(C)～P(x)∨ANSWER(x)ANSWER(C)={C/x}可見(jiàn)公司一定錄取C人工智能ppt例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)T(x,Zhang)人工智能ppt將上述事實(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)

人工智能ppt用下圖的反演樹(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}人工智能ppt3.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)生式規(guī)則和控制策略，人工