人工智能及其應(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ī)器來模仿和執(zhí)行人腦的某些智力功能，并開發(fā)相關(guān)理論和技術(shù)。定義3人工智能(能力)人工智能(能力)是智能機(jī)器所執(zhí)行的通常與人類智能有關(guān)的智能行為，如判斷、推理、證明、識別、感知、理解、通信、設(shè)計(jì)、思考、規(guī)劃、學(xué)習(xí)和問題求解等思維活動。定義2人工智能(學(xué)科)人工智能的三大學(xué)派及其認(rèn)知觀：(1)符號主義認(rèn)為人工智能起源于數(shù)理邏輯。(2)連接主義認(rèn)為人工智能起源于仿生學(xué)，特別是對人腦模型的研究。(3)行為主義認(rèn)為人工智能起源于控制論。人工智能的三大學(xué)派及其認(rèn)知觀：第2章知識表示方法重點(diǎn)掌握用狀態(tài)空間法、問題歸約法、謂詞邏輯法、語義網(wǎng)絡(luò)法、框架表示法來描述問題，解決問題；第2章知識表示方法重點(diǎn)掌握用狀態(tài)空間法、問題歸約法、謂2.1狀態(tài)空間法

許多問題求解方法是采用試探搜索方法的。也就是說，這些方法是通過在某個(gè)可能的解空間內(nèi)尋找一個(gè)解來求解問題的。這種基于解答空間的問題表示和求解方法就是狀態(tài)空間法，它是以狀態(tài)和算符(operator)為基礎(chǔ)來表示和求解問題的。2.1狀態(tài)空間法許多問題求解方法是采用試探搜索方法的。也2.1狀態(tài)空間法狀態(tài)空間法三要點(diǎn)

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

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

(3)狀態(tài)空間方法：基于解答空間的問題表示和求解方法，它是以狀態(tài)和算符為基礎(chǔ)來表示和求解問題的。2.1狀態(tài)空間法狀態(tài)空間法三要點(diǎn)2.1狀態(tài)空間法由上可知，對一個(gè)問題的狀態(tài)描述，必須確定3件事：(1)該狀態(tài)描述方式，特別是初始狀態(tài)描述；(2)操作符集合及其對狀態(tài)描述的作用；(3)目標(biāo)狀態(tài)描述的特性。2.1狀態(tài)空間法由上可知，對一個(gè)問題的狀態(tài)描述，必須確定3例2：(分油問題)有A、B、C三個(gè)不帶刻度的瓶子，分別能裝8kg,5kg和3kg油。如果A瓶裝滿油，B和C是空瓶，怎樣操作三個(gè)瓶，使A中的油平分兩份？(假設(shè)分油過程中不耗油)例2：(分油問題)有A、B、C三個(gè)不帶刻度的瓶子，分別能裝解：第一步：定義問題狀態(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)}解：第一步：定義問題狀態(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瓶倒空。第二步：定義操作符：第三步：求解過程：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瓶倒空。第三步：求解過程：0,33,02,3f1f10

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

由上述狀態(tài)空間圖，可見從初始狀態(tài)(0,1)到例：設(shè)有3個(gè)傳教士和3個(gè)野人來到河邊，打算乘一只船從右岸渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過傳教士人數(shù)，那么野人就會把傳教士吃掉。他們怎樣才能用這條船安全地把所有人都渡過河去？例：設(shè)有3個(gè)傳教士和3個(gè)野人來到河邊，打算乘一只船從右岸渡到解：第一步：定義問題狀態(tài)的描述形式：設(shè)Sk=(M,C,B)表示傳教士和野人在河右岸的狀態(tài)。其中：

M表示傳教士在右岸的人數(shù)。

C表示野人在右岸的人數(shù)。

B用來表示船是不是在右岸。

(B=1表示在右岸，B=0表示在左岸)。初始狀態(tài)集：S={(3,3,1)}目標(biāo)狀態(tài)集：G={(0,0,0)}解：第一步：定義問題狀態(tài)的描述形式：第二步：定義算符。算符R(i,j)表示劃船將i個(gè)傳教士和j個(gè)野人送到左岸的操作。算符L(i,j)表示劃船從左岸將i個(gè)傳教士和j個(gè)野人帶回右岸的操作。由于過河的船每次最多載兩個(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)第二步：定義算符。第三步：求解過程。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)第三步：求解過程。1,1,02,2,13,1,10,2,03

由上述狀態(tài)空間圖，可見從初始狀態(tài)(3,3,1)到目標(biāo)狀態(tài)(0,0,0)的任何一條通路都是問題的一個(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問題歸約法問題歸約法的概念已知問題的描述，通過一系列變換把此問題最終變?yōu)橐粋€(gè)子問題集合；這些子問題的解可以直接得到，從而解決了初始問題。該方法也就是從目標(biāo)(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個(gè)平凡的本原問題集合。這就是問題歸約的實(shí)質(zhì)。2.2問題歸約法問題歸約法的概念2.2問題歸約法問題歸約法的組成部分（1）一個(gè)初始問題描述；（2）一套把問題變換為子問題的操作符；（3）一套本原問題描述。

2.2問題歸約法問題歸約法的組成部分2.3謂詞邏輯法一階謂詞邏輯表示法適于表示確定性的知識。它具有自然性、精確性、嚴(yán)密性及易實(shí)現(xiàn)等特點(diǎn)。2.3謂詞邏輯法一階謂詞邏輯表示法適于表示確定性的知識。2.3謂詞邏輯法用一階謂詞邏輯法表示知識的步驟如下：（1）定義謂詞及個(gè)體，確定每個(gè)謂詞及個(gè)體的確切含義。（2）根據(jù)所要表達(dá)的事物或概念，為每個(gè)謂詞中的變元賦以特定的值。（3）根據(jù)所要表達(dá)的知識的語義，用適當(dāng)?shù)倪B接符號將各個(gè)謂詞連接起來，形成謂詞公式。2.3謂詞邏輯法用一階謂詞邏輯法表示知識的步驟如下：例1：設(shè)有下列事實(shí)性知識：張曉輝是一名計(jì)算機(jī)系的學(xué)生，但他不喜歡編程序。李曉鵬比他父親長得高。請用謂詞公式表示這些知識。（1）定義謂詞及個(gè)體。

Computer(x):x是計(jì)算機(jī)系的學(xué)生。

Like(x,y):x喜歡y。

Higher(x,y):x比y長得高。這里涉及的個(gè)體有：張曉輝(zhangxh),編程序(programming),李曉鵬(lixp)，以及函數(shù)father(lixp)表示李曉鵬的父親。例1：設(shè)有下列事實(shí)性知識：第二步：將這些個(gè)體代入謂詞中，得到Computer(zhangxh),~Like(zhangxh,programming),Higher(lixp,father(lixp))第三步：根據(jù)語義，用邏輯聯(lián)結(jié)詞將它們聯(lián)結(jié)起來，就得到了表示上述知識的謂詞公式。Computer(zhangxh)∧~Like(zhangxh,programming)Higher(lixp,father(lixp))第二步：將這些個(gè)體代入謂詞中，得到例2：設(shè)有下列語句，請用相應(yīng)的謂詞公式把它們表示出來：（1）人人愛勞動。（2）自然數(shù)都是大于零的整數(shù)。（3）西安市的夏天既干燥又炎熱。（4）喜歡讀《三國演義》的人必讀《水滸》。

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

Man(x):x是人。

Love(x,y):x愛y。（x)(Man(x)→Love(x,勞動））解：（1）人人愛勞動。（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）喜歡讀《三國演義》的人必讀《水滸》。定義謂詞：

MAN(x)：x是人。

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

(x)(MAN(x)∧LIKE(x,《SANGUOYANYI》)→LIKE(x,《SHUIHU》))（4）喜歡讀《三國演義》的人必讀《水滸》。定義（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語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)是1968年J.R.Quillian在研究人類聯(lián)想記憶時(shí)提出的心理學(xué)模型。2.4語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)是1968年J.R.Quilli2.4語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的概念語義網(wǎng)絡(luò)是通過概念及其語義關(guān)系來表示知識的一種結(jié)構(gòu)化網(wǎng)絡(luò)圖，它由節(jié)點(diǎn)和弧線或鏈線組成，節(jié)點(diǎn)用來表示各種概念、事物、屬性、情況、動作、狀態(tài)等，每個(gè)節(jié)點(diǎn)可以帶有若干個(gè)屬性，以表征其所代表的對象的特性?；【€用于表示節(jié)點(diǎn)間的關(guān)系，其上的標(biāo)注則表示被連接的兩個(gè)節(jié)點(diǎn)間的某種語義聯(lián)系或語義關(guān)系。2.4語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的概念2.4語義網(wǎng)絡(luò)法

語義網(wǎng)絡(luò)表示知識的方法及步驟（a）確定問題中的所有對象以及各對象的屬性。（b）確定所討論對象間的關(guān)系。（c）語義網(wǎng)絡(luò)中，如果節(jié)點(diǎn)間的聯(lián)系是ISA/AKO，則下層節(jié)點(diǎn)對上層節(jié)點(diǎn)的屬性具有繼承性。整理同一層節(jié)點(diǎn)的共同屬性，并抽出這些屬性，加入上層節(jié)點(diǎn)中，以免造成屬性信息的冗余。2.4語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)表示知識的方法及步驟（d）將各對象作為語義網(wǎng)絡(luò)的一個(gè)節(jié)點(diǎn)，而各對象間的關(guān)系作為網(wǎng)絡(luò)中各節(jié)點(diǎn)間的弧，連接形成語義網(wǎng)絡(luò)。節(jié)點(diǎn)可代表一個(gè)事物或一個(gè)具體概念，也可代表某種情況、事件或某一動作。當(dāng)節(jié)點(diǎn)表示某種事件或某一動作時(shí)，可以從該節(jié)點(diǎn)引出一組向外的弧，用于指出事件的因果或動作的主體及客體。人工智能及其應(yīng)用例1、用一個(gè)語義網(wǎng)絡(luò)表示下列命題。樹和草都是植物；樹和草是有根有葉的；水草是草，且長在水中；果樹是樹，且會結(jié)果；蘋果樹是果樹中的一種，它結(jié)蘋果。例1、用一個(gè)語義網(wǎng)絡(luò)表示下列命題。分析：問題涉及的對象有：植物、樹、草、水草、果樹、蘋果樹各對象的屬性分別為：樹和草的屬性：有根、有葉；水草的屬性：長在水中；果樹的屬性：會結(jié)果；蘋果樹的屬性：結(jié)蘋果。分析：植物蘋果樹水草果樹草樹AKOAKOAKOAKOAKO有根有葉有根有葉會結(jié)果結(jié)蘋果長在水中植物蘋果樹水草果樹草樹AKOAKOAKOAKOAKO有根有葉例：用語義網(wǎng)絡(luò)表示下列知識：獵狗是一種狗，而狗是一種動物。狗除了動物的有生命、能吃食物、有繁殖能力、能運(yùn)動外，還有以下特點(diǎn)：身上有毛、有尾巴、四條腿；獵狗的特點(diǎn)是吃肉、奔跑速度快、能狩獵、個(gè)頭大；而獅子狗也是一種狗，它的特點(diǎn)是吃飼料、身體小、奔跑速度慢、不咬人、供觀賞。例：用語義網(wǎng)絡(luò)表示下列知識：解題分析（1）本知識涉及的對象有4個(gè)：獵狗、獅子狗、狗、動物。獵狗和獅子狗都是一種狗，除了它們本身的屬性外，具有狗的一般特性：身上有毛、有尾巴、四條腿。而狗是一種動物，動物所具有的屬性它也具有。（2）獵狗與狗之間是一種類屬關(guān)系，狗和動物之間也是一種類屬關(guān)系，它們都可以用AKO表示。（3）整理各對象節(jié)點(diǎn)之間的屬性，使上層節(jié)點(diǎn)所具有的屬性不在下層節(jié)點(diǎn)中標(biāo)出。（4）將各對象作為一個(gè)節(jié)點(diǎn)，而它們之間的關(guān)系作為弧，得到如下圖所示的語義網(wǎng)絡(luò)。解題分析動物獅子狗獵狗狗AKOAKOAKO身上有毛有尾巴有四條腿跑得快能獰獵有生命吃飼料能吃食物有繁殖能力能運(yùn)動個(gè)頭大吃肉個(gè)頭小跑得慢不咬人供觀賞動物獅子狗獵狗狗AKOAKOAKO身上有毛有尾巴有四條腿跑得2.5框架表示1974年，由Minsky在“Aframeworkforrepresentingknowledge”中提出?？蚣苁且环N描述所論對象屬性的數(shù)據(jù)結(jié)構(gòu)。所論對象可以是一個(gè)事物、一個(gè)事件或者一個(gè)概念。一個(gè)框架由若干個(gè)“槽”組成，每個(gè)“槽”又可劃分為若干個(gè)“側(cè)面”。一個(gè)槽用于描述所論及對象的某一方面的屬性，一個(gè)側(cè)面用于描述相應(yīng)屬性的一個(gè)方面。槽和側(cè)面所具有的屬性值分別稱為槽值和側(cè)面值。槽值可以是邏輯型或數(shù)字型的，具體的值可以是程序、條件、默認(rèn)值或是一個(gè)子框架。2.5框架表示1974年，由Minsky在“Afra框架表示用框架表示法表示知識的步驟如下：（1）分析待表達(dá)知識中的對象及其屬性，對框架中的槽進(jìn)行合理設(shè)置。（2）對各對象間的各種聯(lián)系進(jìn)行考察。使用一些常用的名稱或根據(jù)具體需要定義一些表達(dá)聯(lián)系的槽名，來描述上、下層框架間的聯(lián)系。（3）對各層對象的“槽”及“側(cè)面”進(jìn)行合理的組織安排，避免信息描述的重復(fù)。框架表示用框架表示法表示知識的步驟如下：例：用框架表示下述報(bào)道的地震事件【虛擬新華社3月15日電】昨日，在云南玉溪地區(qū)發(fā)生地震，造成財(cái)產(chǎn)損失約10萬元，統(tǒng)計(jì)部門如果需要詳細(xì)的損失數(shù)字，可電詢62332931。另據(jù)專家認(rèn)為震級不會超過4級，并認(rèn)為地處無人區(qū)，不會造成人員傷亡。提示：分析概括用下劃線標(biāo)出的要點(diǎn)，經(jīng)過概念化形成槽（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ù)、震級大小等屬性，所以，可將時(shí)間、地點(diǎn)、震級、傷亡人數(shù)、財(cái)產(chǎn)損失等作為槽名。第二步：分析本報(bào)道中各對象間的關(guān)系。由于報(bào)道中只涉及地震一件事，所以該步可省略。

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

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

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

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

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

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

從圖可見，這種搜索是逐層進(jìn)行的；在對下一層的任一節(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è)問題就是要把初始棋局變?yōu)槿缬覉D所示的目標(biāo)棋局問題：

例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹，這個(gè)問題人工智能及其應(yīng)用人工智能及其應(yīng)用人工智能及其應(yīng)用3.3啟發(fā)式搜索盲目搜索的不足：效率低，耗費(fèi)過多的計(jì)算空間與時(shí)間。分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價(jià)搜索算法,其主要的差別是OPEN表中待擴(kuò)展節(jié)點(diǎn)的順序問題。人們就試圖找到一種方法用于排列待擴(kuò)展節(jié)點(diǎn)的順序，即選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展，那么，搜索效率將會大為提高。啟發(fā)信息：進(jìn)行搜索技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域的特性的信息，把此種信息叫做啟發(fā)信息。把利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索方法。3.3啟發(fā)式搜索盲目搜索的不足：效率低，耗費(fèi)過多的計(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)約束地通過節(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ù)的特例。對于寬度優(yōu)先搜索，我們選擇f(i)作為節(jié)點(diǎn)i的深度。對于等代價(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)在于對估價(jià)函數(shù)的定義上。估價(jià)函數(shù)f：f(n)=g(n)+h(n)g(n)：就是到目前為止用搜索算法找到的從S到n的最小路徑代價(jià)。

h(n)：依賴于有關(guā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)用來計(jì)算對應(yīng)于節(jié)點(diǎn)n的數(shù)據(jù)庫中錯(cuò)放的棋子個(gè)數(shù)。因此，起始節(jié)點(diǎn)棋局的f值等于0+3=3。例：八數(shù)碼難題解：采用估價(jià)函數(shù)f(n)=d(n)+W(n)SgS0344555646446SgS03445556464463.4消解原理重點(diǎn)掌握子句集的求解步驟和消解反演過程，掌握消解推理的規(guī)則。3.4消解原理重點(diǎn)掌握子句集的求解步驟和消解反演過程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。這種更改變量名稱的過程，有時(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消解反演求解過程1、消解反演

給出一個(gè)公式集S和目標(biāo)公式L，通過反證或反演來求證目標(biāo)公式L，其證明步驟如下：

(1)否定L，得～L；

(2)把～L添加到S中去；

(3)把新產(chǎn)生的集合｛～L，S｝化成子句集；

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

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

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

(2)在子句集中選擇合適的子句對其進(jìn)行消解，若能推出空子句，就說明子句S是不可滿足的。例1、判斷下列子句集中哪些是不可滿足的(1)S={～P∨Q，～Q，P，～P}

對子句集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)}

解：因子句集中無互補(bǔ)對，故在子句集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))證明：第一步：先對結(jié)論否定并與前提合并得到謂詞公式G。G=(x)(P(x)(Q(x)∧R(x)))∧(x)(P(x)∧T(x))∧～(x)(T(x)∧R(x))第二步：將公式G化為子句集?？蓪看作是三項(xiàng)的合取，對每一項(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)))

第三步：例用消解原理，對子句集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也是不可滿足的。從而命題得證。第三步：例用消解原理，對子句集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)

利用消解原理，對子句集進(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、反演求解過程步驟：

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

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

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

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

(5)若得答案ANSWER，則答案就在ANSWER中。2、反演求解過程例1：應(yīng)用消解反演求解如下問題：“如果無論約翰(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)用消解反演求解如下問題：對本例應(yīng)用消解反演過程：（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}對本例應(yīng)用消解反演過程：～AT(FIDO,x)∨ANSWER例2某公司招聘人員，A、B、C三人應(yīng)試，經(jīng)面試后，公司有如下想法：

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

(2)如果錄用A而不錄用B，則一定錄用C；

(3)如果錄用B，則一定錄用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(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)

利用消解原理，對子句集進(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的老師。求：張的老師是誰？解：令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ù)庫(或全局?jǐn)?shù)據(jù)庫)、產(chǎn)生式規(guī)則和控制策略，3.5產(chǎn)生式系統(tǒng)1、產(chǎn)生式系統(tǒng)的組成總數(shù)據(jù)庫又稱為綜合數(shù)據(jù)庫、上下文、黑板等，用于存放求解過程中各種當(dāng)前信息的數(shù)據(jù)結(jié)構(gòu)，如問題是的初始狀態(tài)、事實(shí)或證據(jù)、中間推理結(jié)論和最后結(jié)果等。產(chǎn)生式規(guī)則是一個(gè)規(guī)則庫，用于存放與求解問題有關(guān)的某個(gè)領(lǐng)域知識的規(guī)則之集合及其交換規(guī)則。其基本形式為

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

請用產(chǎn)生式規(guī)則表示移動小方塊的操作。初始狀態(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來表示空格的話，則建立如下四條產(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ù)庫將棋盤的布局表示為狀態(tài)矩陣的形式存入綜合數(shù)據(jù)庫。例如，初始布局和目標(biāo)布局以矩陣形式表示為：綜合數(shù)據(jù)庫中，存放著初始狀態(tài)矩陣和目標(biāo)狀態(tài)矩陣以及變換過程中的中間矩陣。2）建立綜合數(shù)據(jù)庫綜合數(shù)據(jù)庫中，存放著初始狀態(tài)矩陣和目標(biāo)狀態(tài)3）推理求解在進(jìn)行推理求解時(shí)，可能會有多條產(chǎn)生式規(guī)則的條件部分和綜合數(shù)據(jù)庫中的已有事實(shí)相符，這樣就有可能激活多條規(guī)則。究竟采用哪一條規(guī)則作為啟用規(guī)則規(guī)則，這就是沖突解決策略問題。在本題中采用一個(gè)啟發(fā)式函數(shù)

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

W(n)用來計(jì)算對應(yīng)于節(jié)點(diǎn)n的數(shù)據(jù)庫中錯(cuò)放的棋子個(gè)數(shù)。3）推理求解在綜合數(shù)據(jù)庫中的初始矩陣，能滿足規(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ù)庫中的初始矩陣，能滿足規(guī)則R1，R2，R3，R4的可以得到到達(dá)目標(biāo)狀態(tài)的規(guī)則執(zhí)行序列如下：R1，R2，R1，R4，R3其執(zhí)行過程如下圖所示。圖中節(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ī)器來模仿和執(zhí)行人腦的某些智力功能，并開發(fā)相關(guān)理論和技術(shù)。定義3人工智能(能力)人工智能(能力)是智能機(jī)器所執(zhí)行的通常與人類智能有關(guān)的智能行為，如判斷、推理、證明、識別、感知、理解、通信、設(shè)計(jì)、思考、規(guī)劃、學(xué)習(xí)和問題求解等思維活動。定義2人工智能(學(xué)科)人工智能的三大學(xué)派及其認(rèn)知觀：(1)符號主義認(rèn)為人工智能起源于數(shù)理邏輯。(2)連接主義認(rèn)為人工智能起源于仿生學(xué)，特別是對人腦模型的研究。(3)行為主義認(rèn)為人工智能起源于控制論。人工智能的三大學(xué)派及其認(rèn)知觀：第2章知識表示方法重點(diǎn)掌握用狀態(tài)空間法、問題歸約法、謂詞邏輯法、語義網(wǎng)絡(luò)法、框架表示法來描述問題，解決問題；第2章知識表示方法重點(diǎn)掌握用狀態(tài)空間法、問題歸約法、謂2.1狀態(tài)空間法

許多問題求解方法是采用試探搜索方法的。也就是說，這些方法是通過在某個(gè)可能的解空間內(nèi)尋找一個(gè)解來求解問題的。這種基于解答空間的問題表示和求解方法就是狀態(tài)空間法，它是以狀態(tài)和算符(operator)為基礎(chǔ)來表示和求解問題的。2.1狀態(tài)空間法許多問題求解方法是采用試探搜索方法的。也2.1狀態(tài)空間法狀態(tài)空間法三要點(diǎn)

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

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

(3)狀態(tài)空間方法：基于解答空間的問題表示和求解方法，它是以狀態(tài)和算符為基礎(chǔ)來表示和求解問題的。2.1狀態(tài)空間法狀態(tài)空間法三要點(diǎn)2.1狀態(tài)空間法由上可知，對一個(gè)問題的狀態(tài)描述，必須確定3件事：(1)該狀態(tài)描述方式，特別是初始狀態(tài)描述；(2)操作符集合及其對狀態(tài)描述的作用；(3)目標(biāo)狀態(tài)描述的特性。2.1狀態(tài)空間法由上可知，對一個(gè)問題的狀態(tài)描述，必須確定3例2：(分油問題)有A、B、C三個(gè)不帶刻度的瓶子，分別能裝8kg,5kg和3kg油。如果A瓶裝滿油，B和C是空瓶，怎樣操作三個(gè)瓶，使A中的油平分兩份？(假設(shè)分油過程中不耗油)例2：(分油問題)有A、B、C三個(gè)不帶刻度的瓶子，分別能裝解：第一步：定義問題狀態(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)}解：第一步：定義問題狀態(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瓶倒空。第二步：定義操作符：第三步：求解過程：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瓶倒空。第三步：求解過程：0,33,02,3f1f10

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

由上述狀態(tài)空間圖，可見從初始狀態(tài)(0,1)到例：設(shè)有3個(gè)傳教士和3個(gè)野人來到河邊，打算乘一只船從右岸渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過傳教士人數(shù)，那么野人就會把傳教士吃掉。他們怎樣才能用這條船安全地把所有人都渡過河去？例：設(shè)有3個(gè)傳教士和3個(gè)野人來到河邊，打算乘一只船從右岸渡到解：第一步：定義問題狀態(tài)的描述形式：設(shè)Sk=(M,C,B)表示傳教士和野人在河右岸的狀態(tài)。其中：

M表示傳教士在右岸的人數(shù)。

C表示野人在右岸的人數(shù)。

B用來表示船是不是在右岸。

(B=1表示在右岸，B=0表示在左岸)。初始狀態(tài)集：S={(3,3,1)}目標(biāo)狀態(tài)集：G={(0,0,0)}解：第一步：定義問題狀態(tài)的描述形式：第二步：定義算符。算符R(i,j)表示劃船將i個(gè)傳教士和j個(gè)野人送到左岸的操作。算符L(i,j)表示劃船從左岸將i個(gè)傳教士和j個(gè)野人帶回右岸的操作。由于過河的船每次最多載兩個(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)第二步：定義算符。第三步：求解過程。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)第三步：求解過程。1,1,02,2,13,1,10,2,03

由上述狀態(tài)空間圖，可見從初始狀態(tài)(3,3,1)到目標(biāo)狀態(tài)(0,0,0)的任何一條通路都是問題的一個(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問題歸約法問題歸約法的概念已知問題的描述，通過一系列變換把此問題最終變?yōu)橐粋€(gè)子問題集合；這些子問題的解可以直接得到，從而解決了初始問題。該方法也就是從目標(biāo)(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個(gè)平凡的本原問題集合。這就是問題歸約的實(shí)質(zhì)。2.2問題歸約法問題歸約法的概念2.2問題歸約法問題歸約法的組成部分（1）一個(gè)初始問題描述；（2）一套把問題變換為子問題的操作符；（3）一套本原問題描述。

2.2問題歸約法問題歸約法的組成部分2.3謂詞邏輯法一階謂詞邏輯表示法適于表示確定性的知識。它具有自然性、精確性、嚴(yán)密性及易實(shí)現(xiàn)等特點(diǎn)。2.3謂詞邏輯法一階謂詞邏輯表示法適于表示確定性的知識。2.3謂詞邏輯法用一階謂詞邏輯法表示知識的步驟如下：（1）定義謂詞及個(gè)體，確定每個(gè)謂詞及個(gè)體的確切含義。（2）根據(jù)所要表達(dá)的事物或概念，為每個(gè)謂詞中的變元賦以特定的值。（3）根據(jù)所要表達(dá)的知識的語義，用適當(dāng)?shù)倪B接符號將各個(gè)謂詞連接起來，形成謂詞公式。2.3謂詞邏輯法用一階謂詞邏輯法表示知識的步驟如下：例1：設(shè)有下列事實(shí)性知識：張曉輝是一名計(jì)算機(jī)系的學(xué)生，但他不喜歡編程序。李曉鵬比他父親長得高。請用謂詞公式表示這些知識。（1）定義謂詞及個(gè)體。

Computer(x):x是計(jì)算機(jī)系的學(xué)生。

Like(x,y):x喜歡y。

Higher(x,y):x比y長得高。這里涉及的個(gè)體有：張曉輝(zhangxh),編程序(programming),李曉鵬(lixp)，以及函數(shù)father(lixp)表示李曉鵬的父親。例1：設(shè)有下列事實(shí)性知識：第二步：將這些個(gè)體代入謂詞中，得到Computer(zhangxh),~Like(zhangxh,programming),Higher(lixp,father(lixp))第三步：根據(jù)語義，用邏輯聯(lián)結(jié)詞將它們聯(lián)結(jié)起來，就得到了表示上述知識的謂詞公式。Computer(zhangxh)∧~Like(zhangxh,programming)Higher(lixp,father(lixp))第二步：將這些個(gè)體代入謂詞中，得到例2：設(shè)有下列語句，請用相應(yīng)的謂詞公式把它們表示出來：（1）人人愛勞動。（2）自然數(shù)都是大于零的整數(shù)。（3）西安市的夏天既干燥又炎熱。（4）喜歡讀《三國演義》的人必讀《水滸》。

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

Man(x):x是人。

Love(x,y):x愛y。（x)(Man(x)→Love(x,勞動））解：（1）人人愛勞動。（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）喜歡讀《三國演義》的人必讀《水滸》。定義謂詞：

MAN(x)：x是人。

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

(x)(MAN(x)∧LIKE(x,《SANGUOYANYI》)→LIKE(x,《SHUIHU》))（4）喜歡讀《三國演義》的人必讀《水滸》。定義（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語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)是1968年J.R.Quillian在研究人類聯(lián)想記憶時(shí)提出的心理學(xué)模型。2.4語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)是1968年J.R.Quilli2.4語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的概念語義網(wǎng)絡(luò)是通過概念及其語義關(guān)系來表示知識的一種結(jié)構(gòu)化網(wǎng)絡(luò)圖，它由節(jié)點(diǎn)和弧線或鏈線組成，節(jié)點(diǎn)用來表示各種概念、事物、屬性、情況、動作、狀態(tài)等，每個(gè)節(jié)點(diǎn)可以帶有若干個(gè)屬性，以表征其所代表的對象的特性?；【€用于表示節(jié)點(diǎn)間的關(guān)系，其上的標(biāo)注則表示被連接的兩個(gè)節(jié)點(diǎn)間的某種語義聯(lián)系或語義關(guān)系。2.4語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)的概念2.4語義網(wǎng)絡(luò)法

語義網(wǎng)絡(luò)表示知識的方法及步驟（a）確定問題中的所有對象以及各對象的屬性。（b）確定所討論對象間的關(guān)系。（c）語義網(wǎng)絡(luò)中，如果節(jié)點(diǎn)間的聯(lián)系是ISA/AKO，則下層節(jié)點(diǎn)對上層節(jié)點(diǎn)的屬性具有繼承性。整理同一層節(jié)點(diǎn)的共同屬性，并抽出這些屬性，加入上層節(jié)點(diǎn)中，以免造成屬性信息的冗余。2.4語義網(wǎng)絡(luò)法語義網(wǎng)絡(luò)表示知識的方法及步驟（d）將各對象作為語義網(wǎng)絡(luò)的一個(gè)節(jié)點(diǎn)，而各對象間的關(guān)系作為網(wǎng)絡(luò)中各節(jié)點(diǎn)間的弧，連接形成語義網(wǎng)絡(luò)。節(jié)點(diǎn)可代表一個(gè)事物或一個(gè)具體概念，也可代表某種情況、事件或某一動作。當(dāng)節(jié)點(diǎn)表示某種事件或某一動作時(shí)，可以從該節(jié)點(diǎn)引出一組向外的弧，用于指出事件的因果或動作的主體及客體。人工智能及其應(yīng)用例1、用一個(gè)語義網(wǎng)絡(luò)表示下列命題。樹和草都是植物；樹和草是有根有葉的；水草是草，且長在水中；果樹是樹，且會結(jié)果；蘋果樹是果樹中的一種，它結(jié)蘋果。例1、用一個(gè)語義網(wǎng)絡(luò)表示下列命題。分析：問題涉及的對象有：植物、樹、草、水草、果樹、蘋果樹各對象的屬性分別為：樹和草的屬性：有根、有葉；水草的屬性：長在水中；果樹的屬性：會結(jié)果；蘋果樹的屬性：結(jié)蘋果。分析：植物蘋果樹水草果樹草樹AKOAKOAKOAKOAKO有根有葉有根有葉會結(jié)果結(jié)蘋果長在水中植物蘋果樹水草果樹草樹AKOAKOAKOAKOAKO有根有葉例：用語義網(wǎng)絡(luò)表示下列知識：獵狗是一種狗，而狗是一種動物。狗除了動物的有生命、能吃食物、有繁殖能力、能運(yùn)動外，還有以下特點(diǎn)：身上有毛、有尾巴、四條腿；獵狗的特點(diǎn)是吃肉、奔跑速度快、能狩獵、個(gè)頭大；而獅子狗也是一種狗，它的特點(diǎn)是吃飼料、身體小、奔跑速度慢、不咬人、供觀賞。例：用語義網(wǎng)絡(luò)表示下列知識：解題分析（1）本知識涉及的對象有4個(gè)：獵狗、獅子狗、狗、動物。獵狗和獅子狗都是一種狗，除了它們本身的屬性外，具有狗的一般特性：身上有毛、有尾巴、四條腿。而狗是一種動物，動物所具有的屬性它也具有。（2）獵狗與狗之間是一種類屬關(guān)系，狗和動物之間也是一種類屬關(guān)系，它們都可以用AKO表示。（3）整理各對象節(jié)點(diǎn)之間的屬性，使上層節(jié)點(diǎn)所具有的屬性不在下層節(jié)點(diǎn)中標(biāo)出。（4）將各對象作為一個(gè)節(jié)點(diǎn)，而它們之間的關(guān)系作為弧，得到如下圖所示的語義網(wǎng)絡(luò)。解題分析動物獅子狗獵狗狗AKOAKOAKO身上有毛有尾巴有四條腿跑得快能獰獵有生命吃飼料能吃食物有繁殖能力能運(yùn)動個(gè)頭大吃肉個(gè)頭小跑得慢不咬人供觀賞動物獅子狗獵狗狗AKOAKOAKO身上有毛有尾巴有四條腿跑得2.5框架表示1974年，由Minsky在“Aframeworkforrepresentingknowledge”中提出。框架是一種描述所論對象屬性的數(shù)據(jù)結(jié)構(gòu)。所論對象可以是一個(gè)事物、一個(gè)事件或者一個(gè)概念。一個(gè)框架由若干個(gè)“槽”組成，每個(gè)“槽”又可劃分為若干個(gè)“側(cè)面”。一個(gè)槽用于描述所論及對象的某一方面的屬性，一個(gè)側(cè)面用于描述相應(yīng)屬性的一個(gè)方面。槽和側(cè)面所具有的屬性值分別稱為槽值和側(cè)面值。槽值可以是邏輯型或數(shù)字型的，具體的值可以是程序、條件、默認(rèn)值或是一個(gè)子框架。2.5框架表示1974年，由Minsky在“Afra框架表示用框架表示法表示知識的步驟如下：（1）分析待表達(dá)知識中的對象及其屬性，對框架中的槽進(jìn)行合理設(shè)置。（2）對各對象間的各種聯(lián)系進(jìn)行考察。使用一些常用的名稱或根據(jù)具體需要定義一些表達(dá)聯(lián)系的槽名，來描述上、下層框架間的聯(lián)系。（3）對各層對象的“槽”及“側(cè)面”進(jìn)行合理的組織安排，避免信息描述的重復(fù)?？蚣鼙硎居每蚣鼙硎痉ū硎局R的步驟如下：例：用框架表示下述報(bào)道的地震事件【虛擬新華社3月15日電】昨日，在云南玉溪地區(qū)發(fā)生地震，造成財(cái)產(chǎn)損失約10萬元，統(tǒng)計(jì)部門如果需要詳細(xì)的損失數(shù)字，可電詢62332931。另據(jù)專家認(rèn)為震級不會超過4級，并認(rèn)為地處無人區(qū)，不會造成人員傷亡。提示：分析概括用下劃線標(biāo)出的要點(diǎn)，經(jīng)過概念化形成槽（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ù)、震級大小等屬性，所以，可將時(shí)間、地點(diǎn)、震級、傷亡人數(shù)、財(cái)產(chǎn)損失等作為槽名。第二步：分析本報(bào)道中各對象間的關(guān)系。由于報(bào)道中只涉及地震一件事，所以該步可省略。

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