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

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

制作人：王思文

劉玉奇

于斌

人工智能及其應(yīng)用第1章緒論

1、重點(diǎn)掌握人工智能的幾種定義。2、掌握目前人工智能的三個(gè)主要學(xué)派及其認(rèn)知觀。3、一般了解人工智能的主要研究范圍和應(yīng)用領(lǐng)域。第1章緒論1、重點(diǎn)掌握人工智能的幾種定義。定義2人工智能(學(xué)科)人工智能(學(xué)科)是計(jì)算機(jī)科學(xué)中涉及研究、設(shè)計(jì)和應(yīng)用智能機(jī)器的一個(gè)分支。它的近期主要目標(biāo)在于研究用機(jī)器來(lái)模仿和執(zhí)行人腦的某些智力功能，并開發(fā)相關(guān)理論和技術(shù)。定義3人工智能(能力)人工智能(能力)是智能機(jī)器所執(zhí)行的通常與人類智能有關(guān)的智能行為，如判斷、推理、證明、識(shí)別、感知、理解、通信、設(shè)計(jì)、思考、規(guī)劃、學(xué)習(xí)和問(wèn)題求解等思維活動(dòng)。定義2人工智能(學(xué)科)人工智能的三大學(xué)派及其認(rèn)知觀：(1)符號(hào)主義認(rèn)為人工智能起源于數(shù)理邏輯。(2)連接主義認(rèn)為人工智能起源于仿生學(xué)，特別是對(duì)人腦模型的研究。(3)行為主義認(rèn)為人工智能起源于控制論。人工智能的三大學(xué)派及其認(rèn)知觀：第2章知識(shí)表示方法重點(diǎn)掌握用狀態(tài)空間法、問(wèn)題歸約法、謂詞邏輯法、語(yǔ)義網(wǎng)絡(luò)法、框架表示法來(lái)描述問(wèn)題，解決問(wèn)題；第2章知識(shí)表示方法重點(diǎn)掌握用狀態(tài)空間法、問(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)空間法許多問(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）：把問(wèn)題從一種狀態(tài)變換為另一種狀態(tài)的手段；

(3)狀態(tài)空間方法：基于解答空間的問(wèn)題表示和求解方法，它是以狀態(tài)和算符為基礎(chǔ)來(lái)表示和求解問(wèn)題的。2.1狀態(tài)空間法狀態(tài)空間法三要點(diǎ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.1狀態(tài)空間法由上可知，對(duì)一個(gè)問(wèn)題的狀態(tài)描述，必須確定3例2：(分油問(wèn)題)有A、B、C三個(gè)不帶刻度的瓶子，分別能裝8kg,5kg和3kg油。如果A瓶裝滿油，B和C是空瓶，怎樣操作三個(gè)瓶，使A中的油平分兩份？(假設(shè)分油過(guò)程中不耗油)例2：(分油問(wèn)題)有A、B、C三個(gè)不帶刻度的瓶子，分別能裝解：第一步：定義問(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)}解：第一步：定義問(wèn)題狀態(tài)的描述形式：第二步：定義操作符：

操作：把瓶子倒?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,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瓶倒空。第三步：求解過(guò)程：0,33,02,3f1f10

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

由上述狀態(tài)空間圖，可見從初始狀態(tài)(0,1)到例：設(shè)有3個(gè)傳教士和3個(gè)野人來(lái)到河邊，打算乘一只船從右岸渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，那么野人就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全地把所有人都渡過(guò)河去？例：設(shè)有3個(gè)傳教士和3個(gè)野人來(lái)到河邊，打算乘一只船從右岸渡到解：第一步：定義問(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)}解：第一步：定義問(wèn)題狀態(tài)的描述形式：第二步：定義算符。算符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)第二步：定義算符。第三步：求解過(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)第三步：求解過(guò)程。1,1,02,2,13,1,10,2,03

由上述狀態(tài)空間圖，可見從初始狀態(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)}是算符最少的解之一。由上述狀態(tài)空間圖，可見從初始狀態(tài)(3,3,1)2.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ì)。2.2問(wèn)題歸約法問(wèn)題歸約法的概念2.2問(wèn)題歸約法問(wèn)題歸約法的組成部分（1）一個(gè)初始問(wèn)題描述；（2）一套把問(wèn)題變換為子問(wèn)題的操作符；（3）一套本原問(wèn)題描述。

2.2問(wèn)題歸約法問(wèn)題歸約法的組成部分2.3謂詞邏輯法一階謂詞邏輯表示法適于表示確定性的知識(shí)。它具有自然性、精確性、嚴(yán)密性及易實(shí)現(xiàn)等特點(diǎn)。2.3謂詞邏輯法一階謂詞邏輯表示法適于表示確定性的知識(shí)。2.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)，形成謂詞公式。2.3謂詞邏輯法用一階謂詞邏輯法表示知識(shí)的步驟如下：例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)表示李曉鵬的父親。例1：設(shè)有下列事實(shí)性知識(shí)：第二步：將這些個(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))第二步：將這些個(gè)體代入謂詞中，得到例2：設(shè)有下列語(yǔ)句，請(qǐng)用相應(yīng)的謂詞公式把它們表示出來(lái)：（1）人人愛勞動(dòng)。（2）自然數(shù)都是大于零的整數(shù)。（3）西安市的夏天既干燥又炎熱。（4）喜歡讀《三國(guó)演義》的人必讀《水滸》。

（5）有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。（6）他每天下午都去打籃球。例2：設(shè)有下列語(yǔ)句，請(qǐng)用相應(yīng)的謂詞公式把它們表示出來(lái)：解：（1）人人愛勞動(dòng)。定義謂詞如下：

Man(x):x是人。

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

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

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

GZ(x):x大于等于零。（x)(N(x)→(GZ(x）∧I(x))）（2）自然數(shù)都是大于等于零的整數(shù)。(3)西安市的夏天既干燥又炎熱。定義謂詞：

SUMMER(x):x處于夏天。

DRY(x):x很干燥。

HOT(x):x很炎熱。SUMMER(Xi’an)→DRY(Xi’an)∧HOT(Xi’an)(3)西安市的夏天既干燥又炎熱。（4）喜歡讀《三國(guó)演義》的人必讀《水滸》。定義謂詞：

MAN(x)：x是人。

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

(x)(MAN(x)∧LIKE(x,《SANGUOYANYI》)→LIKE(x,《SHUIHU》))（4）喜歡讀《三國(guó)演義》的人必讀《水滸》。定義（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)))（5）有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡（6）他每天下午都去打籃球。定義謂詞及個(gè)體：設(shè)TIME(x):x是下午。

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

Liming表示李明，

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

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

例：用框架表示下述報(bào)道的地震事件Frame地震Slot1：Value：Default：If-needed：If-added：Slot2：Value：Default：If-needed：If-added：Slot3：Value：Default：If-needed：If-added：Frame地震Slot1：Slot2：Slot3：解：第一步：確定框架的名字和框架的槽。本報(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)道中只涉及地震一件事，所以該步可省略。

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

財(cái)產(chǎn)損失：大約損失：10萬(wàn)元if-needed：ASK（電詢62332931）框架名：＜地震1＞時(shí)間：3月14日地點(diǎn)：云南玉溪地區(qū)震級(jí)：傷第3章搜索推理技術(shù)

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

從問(wèn)題表示到問(wèn)題的解決，有一個(gè)求解的過(guò)程。而實(shí)現(xiàn)求解的過(guò)程，采用的基本方法包括搜索和推理。第3章搜索推理技術(shù)從問(wèn)題表示到問(wèn)題的解決，有一個(gè)求第3章搜索推理技術(shù)和搜索相對(duì)應(yīng)的知識(shí)表示法一般有兩種：狀態(tài)空間法：（S，F(xiàn)，G）與或圖表示法：基于一種分解與變換的思想，利用樹狀結(jié)構(gòu)對(duì)復(fù)雜問(wèn)題進(jìn)行表示，使復(fù)雜問(wèn)題簡(jiǎn)單化。第3章搜索推理技術(shù)和搜索相對(duì)應(yīng)的知識(shí)表示法一般有兩種：第3章搜索推理技術(shù)圖搜索策略是一種在圖中尋找路徑的方法。搜索種類：盲目搜索：只按預(yù)先規(guī)定的搜索控制策略進(jìn)行搜索。啟發(fā)式搜索：根據(jù)問(wèn)題本身的特性或搜索過(guò)程中產(chǎn)生的一些信息來(lái)不斷改變和調(diào)整搜索的方向。第3章搜索推理技術(shù)圖搜索策略是一種在圖中尋找路徑的方法。圖搜索過(guò)程框圖開始把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表失敗成功是是否否圖搜索過(guò)程框圖開始把S放入OPEN表OPEN為空表？把第一個(gè)3.2盲目搜索

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

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

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

sLOMFPQNFFF3.2.1寬度優(yōu)先搜索搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹，這個(gè)問(wèn)題就是要把初始棋局變?yōu)槿缬覉D所示的目標(biāo)棋局問(wèn)題：

例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹，這個(gè)問(wèn)題人工智能及其應(yīng)用人工智能及其應(yīng)用人工智能及其應(yīng)用3.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ā)式搜索方法。3.3啟發(fā)式搜索盲目搜索的不足：效率低，耗費(fèi)過(guò)多的計(jì)算空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)。這種搜索叫做有序搜索(orderedsearch)。3.3啟發(fā)式搜索啟發(fā)式搜索策略3.2.1有序搜索有序搜索又稱為最好優(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à)。3.2.1有序搜索有序搜索又稱為最好優(yōu)先搜索，它總是選擇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.1有序搜索寬度優(yōu)先搜索、等代價(jià)搜索和深度優(yōu)先搜索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)：依賴于有關(guān)問(wèn)題的領(lǐng)域的啟發(fā)信息。

從節(jié)點(diǎn)n到某目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)的估計(jì)。3.3.2A*算法A*算法是一種有序搜索算法，其特點(diǎn)在于例：八數(shù)碼難題

解：采用估價(jià)函數(shù)

f(n)=d(n)+W(n)其中：d(n)是搜索樹中節(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。例：八數(shù)碼難題解：采用估價(jià)函數(shù)f(n)=d(n)+W(n)SgS0344555646446SgS03445556464463.4消解原理重點(diǎn)掌握子句集的求解步驟和消解反演過(guò)程，掌握消解推理的規(guī)則。3.4消解原理重點(diǎn)掌握子句集的求解步驟和消解反演過(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(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)]}}3.4.1子句集的求取例、將下列謂詞演算公式化為一個(gè)子句(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))]}(4)(x){~P(x){(y)[~P(y)P(8)~P(x)~P(y)P(f(x,y))~P(x)Q(x,g(x))~P(x)~P(g(x))(9)更改變量名稱，在上述第（8）步的3個(gè)子句中，分別以x1,x2,x3代替變量x。這種更改變量名稱的過(guò)程，有時(shí)稱為變量分離標(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))](8)~P(x)~P(y)P(f(x,y))(93.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è)表示矛盾的空子句NIL。

3.4.2消解反演求解過(guò)程1、消解反演例1、判斷下列子句集中哪些是不可滿足的分析：子句集中各子句間的關(guān)系是合取關(guān)系，因此只要有一個(gè)子句不可滿足，則子句集就是不可滿足的。

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

(2)在子句集中選擇合適的子句對(duì)其進(jìn)行消解，若能推出空子句，就說(shuō)明子句S是不可滿足的。例1、判斷下列子句集中哪些是不可滿足的(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é)故該子句集是不可滿足的。(1)S={～P∨Q，～Q，P，～P}(2)S={～P(x)∨Q(f(x),a)，～P(h(y))∨Q(f(h(y)),a)∨～P(z)}

解：因子句集中無(wú)互補(bǔ)對(duì)，故在子句集S中不存在空子句，故S為可滿足的。(2)S={～P(x)∨Q(f(x),a)，例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化為子句集?？蓪看作是三項(xiàng)的合取，對(duì)每一項(xiàng)分別求子句集。例2證明(x)(P(x)(Q(x)∧R(x)))∧

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)}G1：(x)(P(x)(Q(x)∧R(x)))

第三步：例用消解原理，對(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也是不可滿足的。從而命題得證。第三步：例用消解原理，對(duì)子句集S進(jìn)行消解例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)例3某公司招聘人員，A、B、C三人應(yīng)試，經(jīng)面試后，公司

將前提化為子句集：

(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將前提化為子句集：P(A)∨P(B)∨P(C)～P(2、反演求解過(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中。2、反演求解過(guò)程例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)例1：應(yīng)用消解反演求解如下問(wèn)題：對(duì)本例應(yīng)用消解反演過(guò)程：（1）目標(biāo)公式否定的子句形為： ～AT(FIDO,x)

將它與謂詞ANSWER構(gòu)成析取式： ～AT(FIDO,x)∨ANSWER(FIDO,x)（2）用下圖的反演樹進(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}對(duì)本例應(yīng)用消解反演過(guò)程：～AT(FIDO,x)∨ANSWER例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)例2某公司招聘人員，A、B、C三人應(yīng)試，經(jīng)面試后，公司將前提化為子句集：(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}可見公司一定錄取C將前提化為子句集：(1)P(A)∨P(B)∨P(C)P(A例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)例3已知（1）王是李的老師解：令T(x,y):x是y的老師將上述事實(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}用下圖的反演樹進(jìn)行消解，并在根部得到子句： ～C(x,y)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)生式規(guī)則和控制策略，3.5產(chǎn)生式系統(tǒng)1、產(chǎn)生式系統(tǒng)的組成總數(shù)據(jù)庫(kù)又稱為綜合數(shù)據(jù)庫(kù)、上下文、黑板等，用于存放求解過(guò)程中各種當(dāng)前信息的數(shù)據(jù)結(jié)構(gòu)，如問(wèn)題是的初始狀態(tài)、事實(shí)或證據(jù)、中間推理結(jié)論和最后結(jié)果等。產(chǎn)生式規(guī)則是一個(gè)規(guī)則庫(kù)，用于存放與求解問(wèn)題有關(guān)的某個(gè)領(lǐng)域知識(shí)的規(guī)則之集合及其交換規(guī)則。其基本形式為

IF前提THEN結(jié)論控制策略的作用是說(shuō)明下一步應(yīng)該選用什么規(guī)則。總數(shù)據(jù)庫(kù)又稱為綜合數(shù)據(jù)庫(kù)、上下文、黑板等，用于存放求解過(guò)程中2、例：設(shè)有八數(shù)碼難題：

請(qǐng)用產(chǎn)生式規(guī)則表示移動(dòng)小方塊的操作。初始狀態(tài)目標(biāo)狀態(tài)2、例：設(shè)有八數(shù)碼難題：初始狀態(tài)目標(biāo)狀態(tài)解：1）建立棋盤變換的產(chǎn)生式規(guī)則。如果把棋盤的每一布局看作是一個(gè)狀態(tài)矩陣，本題就變成了從初始狀態(tài)矩陣到目標(biāo)狀態(tài)矩陣的一種變化。設(shè)Sij為狀態(tài)矩陣的第i行和第j列的數(shù)碼，其中3≥i,j≥1。i0,j0表示空格所在的行和列。如果在狀態(tài)矩陣中用0來(lái)表示空格的話，則建立如下四條產(chǎn)生式規(guī)則：R1:if(j0-1≥1)thenbeginSi0j0:=Si0(j0-1);Si0(j0-1):=0end空格左移解：1）建立棋盤變換的產(chǎn)生式規(guī)則。R1:if(j0-1R2:if(i0-1≥1)thenbeginSi0j0:=S(i0-1)j0;S(i0-1)j0:=0end空格上移R3:if(j0+1≤3)thenbeginSi0j0:=Si0(j0+1);Si0(j0+1):=0end空格右移R4:if(i0+1≤3)thenbeginSi0j0:=S(i0+1)j0;S(i0+1)j0:=0end空格下移R2:if(i0-1≥1)thenbegin2）建立綜合數(shù)據(jù)庫(kù)將棋盤的布局表示為狀態(tài)矩陣的形式存入綜合數(shù)據(jù)庫(kù)。例如，初始布局和目標(biāo)布局以矩陣形式表示為：綜合數(shù)據(jù)庫(kù)中，存放著初始狀態(tài)矩陣和目標(biāo)狀態(tài)矩陣以及變換過(guò)程中的中間矩陣。2）建立綜合數(shù)據(jù)庫(kù)綜合數(shù)據(jù)庫(kù)中，存放著初始狀態(tài)矩陣和目標(biāo)狀態(tài)3）推理求解在進(jìn)行推理求解時(shí)，可能會(huì)有多條產(chǎn)生式規(guī)則的條件部分和綜合數(shù)據(jù)庫(kù)中的已有事實(shí)相符，這樣就有可能激活多條規(guī)則。究竟采用哪一條規(guī)則作為啟用規(guī)則規(guī)則，這就是沖突解決策略問(wèn)題。在本題中采用一個(gè)啟發(fā)式函數(shù)

f(n)=d(n)+W(n)其中：d(n)是搜索樹中節(jié)點(diǎn)n的深度；

W(n)用來(lái)計(jì)算對(duì)應(yīng)于節(jié)點(diǎn)n的數(shù)據(jù)庫(kù)中錯(cuò)放的棋子個(gè)數(shù)。3）推理求解在綜合數(shù)據(jù)庫(kù)中的初始矩陣，能滿足規(guī)則R1，R2，R3，R4的條件，所以有四條匹配規(guī)則。利用啟發(fā)函數(shù)決定哪一條規(guī)則為啟用規(guī)則。因?yàn)橐?guī)則R1的啟發(fā)式函數(shù)值h(x)=4，規(guī)則R2的啟發(fā)式函數(shù)值h(x)=4,規(guī)則R3的啟發(fā)式函數(shù)值h(x)=5,規(guī)則R4的啟發(fā)式函數(shù)值h(x)=5。在這里R1與R2所得到的新狀態(tài)與目標(biāo)狀態(tài)差距最小，且都為4，而在R1與R2中再選擇一條規(guī)則作為啟用規(guī)則，在這里我們使用規(guī)則的排列順序，首先選擇R1，所以啟用規(guī)則R1，依次類推。在綜合數(shù)據(jù)庫(kù)中的初始矩陣，能滿足規(guī)則R1，R2，R3，R4的可以得到到達(dá)目標(biāo)狀態(tài)的規(guī)則執(zhí)行序列如下：R1，R2，R1，R4，R3其執(zhí)行過(guò)程如下圖所示。圖中節(jié)點(diǎn)旁所標(biāo)數(shù)字為h(x)的值，箭頭上所標(biāo)為啟用的規(guī)則?？梢缘玫降竭_(dá)目標(biāo)狀態(tài)的規(guī)則執(zhí)行序列如下：R1，R2，R1，RSgS0344555646446R1R2R3R4R2R4R1R3R4R3R4SgS0344555646446R1R2R3R4R2R4R1人工智能及其應(yīng)用

制作人：王思文

劉玉奇

于斌

人工智能及其應(yīng)用第1章緒論

1、重點(diǎn)掌握人工智能的幾種定義。2、掌握目前人工智能的三個(gè)主要學(xué)派及其認(rèn)知觀。3、一般了解人工智能的主要研究范圍和應(yīng)用領(lǐng)域。第1章緒論1、重點(diǎn)掌握人工智能的幾種定義。定義2人工智能(學(xué)科)人工智能(學(xué)科)是計(jì)算機(jī)科學(xué)中涉及研究、設(shè)計(jì)和應(yīng)用智能機(jī)器的一個(gè)分支。它的近期主要目標(biāo)在于研究用機(jī)器來(lái)模仿和執(zhí)行人腦的某些智力功能，并開發(fā)相關(guān)理論和技術(shù)。定義3人工智能(能力)人工智能(能力)是智能機(jī)器所執(zhí)行的通常與人類智能有關(guān)的智能行為，如判斷、推理、證明、識(shí)別、感知、理解、通信、設(shè)計(jì)、思考、規(guī)劃、學(xué)習(xí)和問(wèn)題求解等思維活動(dòng)。定義2人工智能(學(xué)科)人工智能的三大學(xué)派及其認(rèn)知觀：(1)符號(hào)主義認(rèn)為人工智能起源于數(shù)理邏輯。(2)連接主義認(rèn)為人工智能起源于仿生學(xué)，特別是對(duì)人腦模型的研究。(3)行為主義認(rèn)為人工智能起源于控制論。人工智能的三大學(xué)派及其認(rèn)知觀：第2章知識(shí)表示方法重點(diǎn)掌握用狀態(tài)空間法、問(wèn)題歸約法、謂詞邏輯法、語(yǔ)義網(wǎng)絡(luò)法、框架表示法來(lái)描述問(wèn)題，解決問(wèn)題；第2章知識(shí)表示方法重點(diǎn)掌握用狀態(tài)空間法、問(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)空間法許多問(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）：把問(wèn)題從一種狀態(tài)變換為另一種狀態(tài)的手段；

(3)狀態(tài)空間方法：基于解答空間的問(wèn)題表示和求解方法，它是以狀態(tài)和算符為基礎(chǔ)來(lái)表示和求解問(wèn)題的。2.1狀態(tài)空間法狀態(tài)空間法三要點(diǎ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.1狀態(tài)空間法由上可知，對(duì)一個(gè)問(wèn)題的狀態(tài)描述，必須確定3例2：(分油問(wèn)題)有A、B、C三個(gè)不帶刻度的瓶子，分別能裝8kg,5kg和3kg油。如果A瓶裝滿油，B和C是空瓶，怎樣操作三個(gè)瓶，使A中的油平分兩份？(假設(shè)分油過(guò)程中不耗油)例2：(分油問(wèn)題)有A、B、C三個(gè)不帶刻度的瓶子，分別能裝解：第一步：定義問(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)}解：第一步：定義問(wèn)題狀態(tài)的描述形式：第二步：定義操作符：

操作：把瓶子倒?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,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瓶倒空。第三步：求解過(guò)程：0,33,02,3f1f10

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

由上述狀態(tài)空間圖，可見從初始狀態(tài)(0,1)到例：設(shè)有3個(gè)傳教士和3個(gè)野人來(lái)到河邊，打算乘一只船從右岸渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，那么野人就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全地把所有人都渡過(guò)河去？例：設(shè)有3個(gè)傳教士和3個(gè)野人來(lái)到河邊，打算乘一只船從右岸渡到解：第一步：定義問(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)}解：第一步：定義問(wèn)題狀態(tài)的描述形式：第二步：定義算符。算符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)第二步：定義算符。第三步：求解過(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)第三步：求解過(guò)程。1,1,02,2,13,1,10,2,03

由上述狀態(tài)空間圖，可見從初始狀態(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)}是算符最少的解之一。由上述狀態(tài)空間圖，可見從初始狀態(tài)(3,3,1)2.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ì)。2.2問(wèn)題歸約法問(wèn)題歸約法的概念2.2問(wèn)題歸約法問(wèn)題歸約法的組成部分（1）一個(gè)初始問(wèn)題描述；（2）一套把問(wèn)題變換為子問(wèn)題的操作符；（3）一套本原問(wèn)題描述。

2.2問(wèn)題歸約法問(wèn)題歸約法的組成部分2.3謂詞邏輯法一階謂詞邏輯表示法適于表示確定性的知識(shí)。它具有自然性、精確性、嚴(yán)密性及易實(shí)現(xiàn)等特點(diǎn)。2.3謂詞邏輯法一階謂詞邏輯表示法適于表示確定性的知識(shí)。2.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)，形成謂詞公式。2.3謂詞邏輯法用一階謂詞邏輯法表示知識(shí)的步驟如下：例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)表示李曉鵬的父親。例1：設(shè)有下列事實(shí)性知識(shí)：第二步：將這些個(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))第二步：將這些個(gè)體代入謂詞中，得到例2：設(shè)有下列語(yǔ)句，請(qǐng)用相應(yīng)的謂詞公式把它們表示出來(lái)：（1）人人愛勞動(dòng)。（2）自然數(shù)都是大于零的整數(shù)。（3）西安市的夏天既干燥又炎熱。（4）喜歡讀《三國(guó)演義》的人必讀《水滸》。

（5）有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。（6）他每天下午都去打籃球。例2：設(shè)有下列語(yǔ)句，請(qǐng)用相應(yīng)的謂詞公式把它們表示出來(lái)：解：（1）人人愛勞動(dòng)。定義謂詞如下：

Man(x):x是人。

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

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

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

GZ(x):x大于等于零。（x)(N(x)→(GZ(x）∧I(x))）（2）自然數(shù)都是大于等于零的整數(shù)。(3)西安市的夏天既干燥又炎熱。定義謂詞：

SUMMER(x):x處于夏天。

DRY(x):x很干燥。

HOT(x):x很炎熱。SUMMER(Xi’an)→DRY(Xi’an)∧HOT(Xi’an)(3)西安市的夏天既干燥又炎熱。（4）喜歡讀《三國(guó)演義》的人必讀《水滸》。定義謂詞：

MAN(x)：x是人。

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

(x)(MAN(x)∧LIKE(x,《SANGUOYANYI》)→LIKE(x,《SHUIHU》))（4）喜歡讀《三國(guó)演義》的人必讀《水滸》。定義（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)))（5）有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡（6）他每天下午都去打籃球。定義謂詞及個(gè)體：設(shè)TIME(x):x是下午。

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

Liming表示李明，

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

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

例：用框架表示下述報(bào)道的地震事件Frame地震Slot1：Value：Default：If-needed：If-added：Slot2：Value：Default：If-needed：If-added：Slot3：Value：Default：If-needed：If-added：Frame地震Slot1：Slot2：Slot3：解：第一步：確定框架的名字和框架的槽。本報(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)道中只涉及地震一件事，所以該步可省略。

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