《人工智能及其應(yīng)用》由會(huì)員分享，可在線閱讀，更多相關(guān)《人工智能及其應(yīng)用（97頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),,,?#?,人工智能及其應(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í)行

2、的通常與人類智能有關(guān)的智能行為，如判斷、推理、證明、識(shí)別、感知、理解、通信、設(shè)計(jì)、思考、規(guī)劃、學(xué)習(xí)和問(wèn)題求解等思維活動(dòng)。,,人工智能的三大學(xué)派及其認(rèn)知觀：,(1),符號(hào)主義 認(rèn)為人工智能起源于數(shù)理邏輯。,(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)題的。這種基于解答空

3、間的問(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,）：把問(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)描述的

4、特性。,,,例,2,：,(,分油問(wèn)題,),有,A,、,B,、,C,三個(gè)不帶刻度的瓶子，分別能裝,8kg, 5kg,和,3kg,油。如果,A,瓶裝滿油，,B,和,C,是空瓶，怎樣操作三個(gè)瓶，使,A,中的油平分兩份？,(,假設(shè)分油過(guò)程中不耗油,),,解：第,一,一步：,定,定義,問(wèn),問(wèn)題狀,態(tài),態(tài)的描,述,述形式,：,：,設(shè),S,k,=(b,c),表示,B,瓶和,C,瓶中的,油,油量的,狀,狀態(tài)。,其中：,b,表示,B,瓶中的,油,油量。,c,表示,C,瓶中的,油,油量。,初始狀,態(tài),態(tài)集：,S={(0,0)},目標(biāo)狀,態(tài),態(tài)集：,G={(4,0)},,第二步,：,： 定,義,義操作,符,符：,操

5、作：,把,把瓶子,倒,倒?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,瓶倒空,。,。,第三步,：,：

6、 求,解,解過(guò)程,：,：,0,3,3,0,2,3,f1,f1,0,0,5,3,1,3,1,0,0,1,5,1,3,3,4,0,4,3,5,2,5,3,0,0,0,2,0,3,2,0,5,0,f1,f3,f4,f7,f8,f6,f5,f3,f1,f4,f7,f5,f3,f2,f8,f3,f8,f3,f2,f5,f8,f3,f8,f7,f7,f6,f1,f4,f7,f4,f5,f1,f7,f1,f1,f1,f7,f5,f5,f7,f5,f6,f7,f5,f1,f3,f3,,f1,：從,A,瓶往,B,瓶倒油,，,，,把,B,瓶倒?jié)M,。,。,,f2,：從,C,瓶往,B,瓶倒油,，,，,把,B,瓶倒?jié)M,

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

8、少的解之,一,一。,例：設(shè)有,3,個(gè)傳教士,和,和,3,個(gè)野人來(lái),到,到河邊，,打,打算乘一,只,只船從右,岸,岸渡到左,岸,岸去。該,船,船的負(fù)載,能,能力為兩,人,人。在任,何,何時(shí)候，,如,如果野人,人,人數(shù)超過(guò),傳,傳教士人,數(shù),數(shù)，那么,野,野人就會(huì),把,把傳教士,吃,吃掉。他,們,們?cè)鯓硬?能,能用這條,船,船安全地,把,把所有人,都,都渡過(guò)河,去,去？,,,解：第一,步,步： 定,義,義問(wèn)題狀,態(tài),態(tài)的描述,形,形式：,設(shè),S,k,=(M,C,B),表示傳教,士,士和野人,在,在河右岸,的,的狀態(tài)。,其中：,M,表示傳教,士,士在右岸,的,的人數(shù)。,C,表示野人,在,在右岸的,人

9、,人數(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è),個(gè)人，所,以,以,i+j≤2,。這樣定,義,義的算符,集,集,F,中只可能,有,有如下,10,個(gè)算符。,F,：,R(

10、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,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,

11、0,0,1,1,0,2,1,R(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,1,R(0,2),L(0,2),由上述狀,態(tài),態(tài)空間圖,，,，可見(jiàn)從,初,初始狀態(tài),(3,3,1),到目標(biāo)狀,態(tài),態(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,

12、問(wèn)題歸約,法,法,問(wèn)題歸約,法,法的概念,已知問(wèn)題,的,的描述，,通,通過(guò)一系,列,列變換把,此,此問(wèn)題最,終,終變?yōu)橐?個(gè),個(gè)子問(wèn)題,集,集合；這,些,些子問(wèn)題,的,的解可以,直,直接得到,，,，從而解,決,決了初始,問(wèn),問(wèn)題。,該方法也,就,就是從目,標(biāo),標(biāo),(,要解決的,問(wèn),問(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)題描,述,述；,（,

13、2,）一套把,問(wèn),問(wèn)題變換,為,為子問(wèn)題,的,的操作符,；,；,（,3,）一套本,原,原問(wèn)題描,述,述。,2.3,謂詞邏輯,法,法,一階謂詞,邏,邏輯表示,法,法適于表,示,示確定性,的,的知識(shí)。,它,它具有自,然,然性、精,確,確性、嚴(yán),密,密性及易,實(shí),實(shí)現(xiàn)等特,點(diǎn),點(diǎn)。,2.3,謂詞邏輯,法,法,用一階謂,詞,詞邏輯法,表,表示知識(shí),的,的步驟如,下,下：,（,1,）定義謂,詞,詞及個(gè)體,，,，確定每,個(gè),個(gè)謂詞及,個(gè),個(gè)體的確,切,切含義。,（,2,）根據(jù)所,要,要表達(dá)的,事,事物或概,念,念，為每,個(gè),個(gè)謂詞中,的,的變?cè)x,以,以特定的,值,值。,（,3,）根據(jù)所,要,要表達(dá)的,知

14、,知識(shí)的語(yǔ),義,義，用適,當(dāng),當(dāng)?shù)倪B接,符,符號(hào)將各,個(gè),個(gè)謂詞連,接,接起來(lái)，,形,形成謂詞,公,公式。,例,1,：設(shè)有下,列,列事實(shí)性,知,知識(shí)：,張曉輝是,一,一名計(jì)算,機(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),,李

15、曉鵬,(lixp),，以及函,數(shù),數(shù),father(lixp),表示李曉,鵬,鵬的父親,。,。,第二步：,將,將這些個(gè),體,體代入謂,詞,詞中，得,到,到,Computer(zhangxh), ~Like(zhangxh, programming),Higher(lixp,father(lixp)),,第三步：,根,根據(jù)語(yǔ)義,，,，用邏輯,聯(lián),聯(lián)結(jié)詞將,它,它們聯(lián)結(jié),起,起來(lái)，就,得,得到了表,示,示上述知,識(shí),識(shí)的謂詞,公,公式。,Computer(zhangxh)∧ ~Like(zhangxh, programming),Higher(lixp,father(lixp)),,例,2,：,設(shè)

16、有下列,語(yǔ),語(yǔ)句，請(qǐng),用,用相應(yīng)的,謂,謂詞公式,把,把它們表,示,示出來(lái)：,（,1,）人人愛(ài),勞,勞動(dòng)。,（,2,）自然數(shù),都,都是大于,零,零的整數(shù),。,。,（,3,）西安市,的,的夏天既,干,干燥又炎,熱,熱。,（,4,）喜歡讀,《,三國(guó)演義,》,的人必讀,《,水滸,》,。,（,5,）有的人,喜,喜歡梅花,，,，有的人,喜,喜歡菊花,，,，有的人,既,既喜歡梅,花,花又喜歡,菊,菊花。,（,6,）他每,天,天下午,都,都去打,籃,籃球。,解：,（,1,）人人,愛(ài),愛(ài)勞動(dòng),。,。,定義謂,詞,詞如下,：,：,Man(x):x,是人。,Love(x,y):x,愛(ài),y,。,（?,x)(Man(

17、x),→,→Love(x,,勞動(dòng)）,）,）,,,,（,2,）自然,數(shù),數(shù)都是,大,大于等,于,于零的,整,整數(shù)。,定義謂,詞,詞如下,：,：,N(x):x,是自然,數(shù),數(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(Xi,’,’an)→DRY(Xi’an),∧,∧HOT(Xi’an),,（,4,）喜歡,讀,讀,《,三

18、國(guó)演,義,義,》,的人必,讀,讀,《,水滸,》,。,定,定,義,義謂詞,：,：,MAN(x),：,x,是人。,LIKE(x,y),：,x,喜歡讀,y,。,(,?x,)(MAN(x)∧LIKE(x, 《SANGUOYANYI》),→LIKE(x,,《,《SHUIHU》)),,（,5,）有的,人,人喜歡,梅,梅花，,有,有的人,喜,喜歡菊,花,花，有,的,的人既,喜,喜歡梅,花,花又喜,歡,歡菊花,。,。,定義謂,詞,詞：,MAN(x):x,是人。,LIKE(x,y): x,喜歡,y,。,Meihua,表示梅,花,花，,Juhua,表示菊,花,花，,(,?x)(MAN(x),∧,LIKE(x,,M

19、eihua))∧,(,?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,Basketball),2.4,語(yǔ)義網(wǎng),絡(luò),絡(luò)法,語(yǔ)義網(wǎng),絡(luò),絡(luò)是,1968,年,J.R.Quillian,在研究,人,

20、人類聯(lián),想,想記憶,時(shí),時(shí)提出,的,的心理,學(xué),學(xué)模型,。,。,,2.4,語(yǔ)義網(wǎng),絡(luò),絡(luò)法,語(yǔ)義網(wǎng),絡(luò),絡(luò)的概,念,念,語(yǔ)義網(wǎng),絡(luò),絡(luò)是通,過(guò),過(guò)概念,及,及其語(yǔ),義,義關(guān)系,來(lái),來(lái)表示,知,知識(shí)的,一,一種結(jié),構(gòu),構(gòu)化網(wǎng),絡(luò),絡(luò)圖，,它,它由節(jié),點(diǎn),點(diǎn)和弧,線,線或鏈,線,線組成,，,，節(jié)點(diǎn),用,用來(lái)表,示,示各種,概,概念、,事,事物、,屬,屬性、,情,情況、,動(dòng),動(dòng)作、,狀,狀態(tài)等,，,，每個(gè),節(jié),節(jié)點(diǎn)可,以,以帶有,若,若干個(gè),屬,屬性，,以,以表征,其,其所代,表,表的對(duì),象,象的特,性,性。弧,線,線用于,表,表示節(jié),點(diǎn),點(diǎn)間的,關(guān),關(guān)系，,其,其上的,標(biāo),標(biāo)注則,表,表示被,連,

21、連接的,兩,兩個(gè)節(jié),點(diǎn),點(diǎn)間的,某,某種語(yǔ),義,義聯(lián)系,或,或語(yǔ)義,關(guān),關(guān)系。,,2.4,語(yǔ)義網(wǎng),絡(luò),絡(luò)法,語(yǔ)義網(wǎng),絡(luò),絡(luò)表示,知,知識(shí)的,方,方法及,步,步驟,（,a,）確定,問(wèn),問(wèn)題中,的,的所有,對(duì),對(duì)象以,及,及各對(duì),象,象的屬,性,性。,（,b,）確定,所,所討論,對(duì),對(duì)象間,的,的關(guān)系,。,。,（,c,）語(yǔ)義,網(wǎng),網(wǎng)絡(luò)中,，,，如果,節(jié),節(jié)點(diǎn)間,的,的聯(lián)系,是,是,ISA/AKO,，則下,層,層節(jié)點(diǎn),對(duì),對(duì)上層,節(jié),節(jié)點(diǎn)的,屬,屬性具,有,有繼承,性,性。整,理,理同一,層,層節(jié)點(diǎn),的,的共同,屬,屬性，,并,并抽出,這,這些屬,性,性，加,入,入上層,節(jié),節(jié)點(diǎn)中,，,，以免,造,

22、造成屬,性,性信息,的,的冗余,。,。,,（,d,）將各,對(duì),對(duì)象作,為,為語(yǔ)義,網(wǎng),網(wǎng)絡(luò)的,一,一個(gè)節(jié),點(diǎn),點(diǎn)，而,各,各對(duì)象,間,間的關(guān),系,系作為,網(wǎng),網(wǎng)絡(luò)中,各,各節(jié)點(diǎn),間,間的弧,，,，連接,形,形成語(yǔ),義,義網(wǎng)絡(luò),。,。節(jié)點(diǎn),可,可代表,一,一個(gè)事,物,物或一,個(gè),個(gè)具體,概,概念，,也,也可代,表,表某種,情,情況、,事,事件或,某,某一動(dòng),作,作。當(dāng),節(jié),節(jié)點(diǎn)表,示,示某種,事,事件或,某,某一動(dòng),作,作時(shí)，,可,可以從,該,該節(jié)點(diǎn),引,引出一,組,組向外,的,的弧，,用,用于指,出,出事件,的,的因果,或,或動(dòng)作,的,的主體,及,及客體,。,。,例,1,、用一,個(gè),個(gè)語(yǔ)義,網(wǎng)

23、,網(wǎng)絡(luò)表,示,示下列,命,命題。,樹(shù)和草,都,都是植,物,物；,樹(shù)和草,是,是有根,有,有葉的,；,；,水草是,草,草，且,長(zhǎng),長(zhǎng)在水,中,中；,果樹(shù)是,樹(shù),樹(shù)，且,會(huì),會(huì)結(jié)果,；,；,蘋(píng)果樹(shù),是,是果樹(shù),中,中的一,種,種，它,結(jié),結(jié)蘋(píng)果,。,。,分析：,問(wèn)題涉,及,及的對(duì),象,象有：,植物、,樹(shù),樹(shù)、草,、,、水草,、,、果樹(shù),、,、蘋(píng)果,樹(shù),樹(shù),各對(duì)象,的,的屬性,分,分別為,：,：,樹(shù)和草,的,的屬性,：,：有根,、,、有葉,；,；,水草的,屬,屬性：,長(zhǎng),長(zhǎng)在水,中,中；,果樹(shù)的,屬,屬性：,會(huì),會(huì)結(jié)果,；,；,蘋(píng)果樹(shù),的,的屬性,：,：結(jié)蘋(píng),果,果。,植物,蘋(píng)果樹(shù),水草,果樹(shù),草,

24、樹(shù),AKO,AKO,AKO,AKO,AKO,有根,有葉,有根,有葉,會(huì)結(jié)果,結(jié)蘋(píng)果,長(zhǎng)在水,中,中,例：用,語(yǔ),語(yǔ)義網(wǎng),絡(luò),絡(luò)表示,下,下列知,識(shí),識(shí)：,獵狗是,一,一種狗,，,，而狗,是,是一種,動(dòng),動(dòng)物。,狗,狗除了,動(dòng),動(dòng)物的,有,有生命,、,、能吃,食,食物、,有,有繁殖,能,能力、,能,能運(yùn)動(dòng),外,外，還,有,有以下,特,特點(diǎn)：,身,身上有,毛,毛、有,尾,尾巴、,四,四條腿,；,；獵狗,的,的特點(diǎn),是,是吃肉,、,、奔跑,速,速度快,、,、能狩,獵,獵、個(gè),頭,頭大；,而,而獅子,狗,狗也是,一,一種狗,，,，它的,特,特點(diǎn)是,吃,吃飼料,、,、身體,小,小、奔,跑,跑速度,慢,慢

25、、不,咬,咬人、,供,供觀賞,。,。,,解題分,析,析,（,1,）本知,識(shí),識(shí)涉及,的,的對(duì)象,有,有,4,個(gè)：獵,狗,狗、獅,子,子狗、,狗,狗、動(dòng),物,物。獵,狗,狗和獅,子,子狗都,是,是一種,狗,狗，除,了,了它們,本,本身的,屬,屬性外,，,，具有,狗,狗的一,般,般特性,：,：身上,有,有毛、,有,有尾巴,、,、四條,腿,腿。而,狗,狗是一,種,種動(dòng)物,，,，動(dòng)物,所,所具有,的,的屬性,它,它也具,有,有。,（,2,）獵狗,與,與狗之,間,間是一,種,種類屬,關(guān),關(guān)系，,狗,狗和動(dòng),物,物之間,也,也是一,種,種類屬,關(guān),關(guān)系，,它,它們都,可,可以用,AKO,表示。,（,3,）

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

27、senting knowledge”,中提出,。,。,框架是,一,一種描,述,述所論,對(duì),對(duì)象屬,性,性的數(shù),據(jù),據(jù)結(jié)構(gòu),。,。所論,對(duì),對(duì)象可,以,以是一,個(gè),個(gè)事物,、,、一個(gè),事,事件或,者,者一個(gè),概,概念。,一,一個(gè)框,架,架由若,干,干個(gè)“,槽,槽”組,成,成，每,個(gè),個(gè)“槽,”,”又可,劃,劃分為,若,若干個(gè),“,“側(cè)面,”,”。一,個(gè),個(gè)槽用,于,于描述,所,所論及,對(duì),對(duì)象的,某,某一方,面,面的屬,性,性，一,個(gè),個(gè)側(cè)面,用,用于描,述,述相應(yīng),屬,屬性的,一,一個(gè)方,面,面。槽,和,和側(cè)面,所,所具有,的,的屬性,值,值分別,稱,稱為槽,值,值和側(cè),面,面值。,槽,槽值可

28、,以,以是邏,輯,輯型或,數(shù),數(shù)字型,的,的，具,體,體的值,可,可以是,程,程序、,條,條件、,默,默認(rèn)值,或,或是一,個(gè),個(gè)子框,架,架。,框架表,示,示,用框架,表,表示法,表,表示知,識(shí),識(shí)的步,驟,驟如下,：,：,（,1,）分析,待,待表達(dá),知,知識(shí)中,的,的對(duì)象,及,及其屬,性,性，對(duì),框,框架中,的,的槽進(jìn),行,行合理,設(shè),設(shè)置。,（,2,）對(duì)各,對(duì),對(duì)象間,的,的各種,聯(lián),聯(lián)系進(jìn),行,行考察,。,。使用,一,一些常,用,用的名,稱,稱或根,據(jù),據(jù)具體,需,需要定,義,義一些,表,表達(dá)聯(lián),系,系的槽,名,名，來(lái),描,描述上,、,、下層,框,框架間,的,的聯(lián)系,。,。,（,3,）對(duì)

29、各,層,層對(duì)象,的,的“槽,”,”及“,側(cè),側(cè)面”,進(jìn),進(jìn)行合,理,理的組,織,織安排,，,，避免,信,信息描,述,述的重,復(fù),復(fù)。,例：用,框,框架表,示,示下述,報(bào),報(bào)道的,地,地震事,件,件,【,虛擬新,華,華社,3,月,15,日電,】,昨日,，在,云南玉,溪,溪地區(qū),發(fā)生,地震,，造成,財(cái)產(chǎn)損,失,失約,10,萬(wàn)元,，統(tǒng)計(jì),部,部門,如果需,要,要詳細(xì),的,的損失,數(shù),數(shù)字,，可,電詢,62332931,。另?yè)?jù),專,專家,認(rèn)為震,級(jí),級(jí),不會(huì)超,過(guò),過(guò),4,級(jí),，并認(rèn),為,為地,處無(wú)人,區(qū),區(qū)，不,會(huì),會(huì)造成,人,人員傷,亡,亡,。,提示：,分,分析概,括,括用下,劃,劃線標(biāo),出,出的

30、要,點(diǎn),點(diǎn)，經(jīng),過(guò),過(guò)概念,化,化形成,槽,槽（,slot,）、側(cè),面,面（,facet,）值。,特,特別要,注,注意，,“,值,”,（,value,）、,“,默認(rèn)值,”,（,default,）、,“,如果需,要,要值,”,（,if-needed,）、,“,如果附,加,加值,”,（,if-added,）的區(qū),別,別與應(yīng),用,用，建,議,議采用,格,格式如,下,下，不,用,用的側(cè),面,面值可,刪,刪。,,,,,Frame,地震,,Slot1,：,Value,：,Default,：,If-needed,：,If-added,：,,,Slot2,：,Value,：,Default,：,If-need

31、ed,：,If-added,：,,,Slot3,：,Value,：,Default,：,If-needed,：,If-added,：,,,,解：,第一步,：,：確定,框,框架的,名,名字和,框,框架的,槽,槽。,本報(bào)道中，,涉,涉及地震的,發(fā),發(fā)生時(shí)間、,地,地點(diǎn)、財(cái)產(chǎn),損,損失、傷亡,人,人數(shù)、震級(jí),大,大小等屬性,，,，所以，可,將,將時(shí)間、地,點(diǎn),點(diǎn)、震級(jí)、,傷,傷亡人數(shù)、,財(cái),財(cái)產(chǎn)損失等,作,作為槽名。,第二步：分,析,析本報(bào)道中,各,各對(duì)象間的,關(guān),關(guān)系。,由于報(bào)道中,只,只涉及地震,一,一件事，所,以,以該步可省,略,略。,框架名：＜地震,1,＞,時(shí)間：,3,月,14,日,,,,,

32、,,地點(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,）,,,第,3,章　搜索推,理,理技術(shù),重點(diǎn)掌握一,般,般圖搜索策,略,略和消解原,理,理，掌握各,種,種搜索方法,和,和產(chǎn)生式系,統(tǒng),統(tǒng)原理，了,解,解規(guī)則演繹,系,系統(tǒng)的基本,原,原理，對(duì)系,統(tǒng),統(tǒng)組織技術(shù),、,、不確定性,推,推理和非單,調(diào),調(diào)推理等高,級(jí),級(jí)推理技術(shù),作,作一般性了,解,解。,,第,3,章　搜索推,理,理技術(shù),從問(wèn)題表示,到,到問(wèn)題的解,決,決

33、，有一個(gè),求,求解的過(guò)程,。,。而實(shí)現(xiàn)求,解,解的過(guò)程，,采,采用的基本,方,方法包括搜,索,索和推理。,第,3,章　搜索推,理,理技術(shù),和搜索相對(duì),應(yīng),應(yīng)的知識(shí)表,示,示法一般有,兩,兩種：,狀態(tài)空間法,：（,S,，,F,，,G,）,與或圖表示,法,法：基于一,種,種分解與變,換,換的思想，,利,利用樹(shù)狀結(jié),構(gòu),構(gòu)對(duì)復(fù)雜問(wèn),題,題進(jìn)行表示,，,，使復(fù)雜問(wèn),題,題簡(jiǎn)單化。,第,3,章　搜索推,理,理技術(shù),圖搜索策略,是,是一種在圖,中,中尋找路徑,的,的方法。,搜索種類：,盲目搜索：,只,只按預(yù)先規(guī),定,定的搜索控,制,制策略進(jìn)行,搜,搜索。,啟發(fā)式搜索,：,：根據(jù)問(wèn)題,本,本身的特性,或,或

34、搜索過(guò)程,中,中產(chǎn)生的一,些,些信息來(lái)不,斷,斷改變和調(diào),整,整搜索的方,向,向。,圖搜索過(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è)较?重排,OPEN,表,失敗,成功,是,是,否,否,3.2,盲目搜索,盲目搜索又,叫,叫做無(wú)信息,搜,搜索，一般,只,只適用于求,解,解比較簡(jiǎn)單,的,的問(wèn)題。寬,度,度優(yōu)先搜索,和,和深度優(yōu)先,搜,搜索，屬于,盲,盲目搜索方,法,法。,,3.2.1,寬度優(yōu)先搜,索,索,搜索是以接

35、,近,近起始節(jié)點(diǎn),的,的程度依次,擴(kuò),擴(kuò)展節(jié)點(diǎn)的,，,，如左圖所,示,示。,從,從圖可見(jiàn)，,這,這種搜索是,逐,逐層進(jìn)行的,；,；在對(duì)下一,層,層的任一節(jié),點(diǎn),點(diǎn)進(jìn)行搜索,之,之前，必須,搜,搜索完本層,的,的所有節(jié)點(diǎn),。,。,,s,L,O,M,F,P,Q,N,F,F,F,例：把寬度,優(yōu),優(yōu)先搜索應(yīng),用,用于八數(shù)碼,難,難題時(shí)所生,成,成的搜索樹(shù),，,，這個(gè)問(wèn)題,就,就是要把初,始,始棋局變?yōu)?如,如右圖所示,的,的目標(biāo)棋局,問(wèn),問(wèn)題：,,,,,,,,3.3,啟發(fā)式搜索,盲目搜索的,不,不足：效率,低,低，耗費(fèi)過(guò),多,多的計(jì)算空,間,間與時(shí)間。,分析前面介,紹,紹的寬度優(yōu),先,先、深度優(yōu),先,

36、先搜索，或,等,等代價(jià)搜索,算,算法,,,其主要的差,別,別是,OPEN,表中待擴(kuò)展,節(jié),節(jié)點(diǎn)的順序,問(wèn),問(wèn)題。人們,就,就試圖找到,一,一種方法用,于,于排列待擴(kuò),展,展節(jié)點(diǎn)的順,序,序，即選擇,最,最有希望的,節(jié),節(jié)點(diǎn)加以擴(kuò),展,展，那么，,搜,搜索效率將,會(huì),會(huì)大為提高,。,。,啟發(fā)信息：,進(jìn),進(jìn)行搜索技,術(shù),術(shù)一般需要,某,某些有關(guān)具,體,體問(wèn)題領(lǐng)域,的,的特性的信,息,息，把此種,信,信息叫做啟,發(fā),發(fā)信息。,把利用啟發(fā),信,信息的搜索,方,方法叫做啟,發(fā),發(fā)式搜索方,法,法。,3.3,啟發(fā)式搜索,啟發(fā)式搜索,策,策略,啟發(fā)信息用,于,于決定要擴(kuò),展,展的下一個(gè),節(jié),節(jié)點(diǎn)，以免,象,

37、象在寬度優(yōu),先,先或深度優(yōu),先,先搜索中那,樣,樣盲目地?cái)U(kuò),展,展。,這種搜索總,是,是選擇,“,最有希望,”,的節(jié)點(diǎn)作為,下,下一個(gè)被擴(kuò),展,展的節(jié)點(diǎn)。,這,這種搜索叫,做,做有序搜索,(ordered search),。,3.2.1,有序搜索,有序搜索又,稱,稱為最好優(yōu),先,先搜索，它,總,總是選擇最,有,有希望的節(jié),點(diǎn),點(diǎn)作為下一,個(gè),個(gè)要擴(kuò)展的,節(jié),節(jié)點(diǎn)。,估價(jià)函數(shù),f,的確定：一,個(gè),個(gè)節(jié)點(diǎn)的希,望,望程度越大,，,，則其,f,值越小。為,此,此，被選為,擴(kuò),擴(kuò)展的節(jié)點(diǎn),，,，是估價(jià)函,數(shù),數(shù)最小的節(jié),點(diǎn),點(diǎn)。,f,是從起始節(jié),點(diǎn),點(diǎn)約束地通,過(guò),過(guò)節(jié)點(diǎn),n,而到達(dá)目標(biāo),節(jié),節(jié)點(diǎn)的最

38、小,代,代價(jià)路徑上,的,的一個(gè)估算,代,代價(jià),。,3.3.1,有序搜索,寬度優(yōu)先搜,索,索、等代價(jià),搜,搜索和深度,優(yōu),優(yōu)先搜索統(tǒng),統(tǒng),統(tǒng)是有序搜,索,索技術(shù)的特,例,例。,對(duì)于寬度優(yōu),先,先搜索，我,們,們選擇,f(i),作為節(jié)點(diǎn),i,的深度。對(duì),于,于等代價(jià)搜,索,索，,f(i),是從起始節(jié),點(diǎn),點(diǎn)至節(jié)點(diǎn),i,這段路徑的,代,代價(jià)。,3.3.2A,*,算法,A*,算法是一種,有,有序搜索算,法,法，其特點(diǎn),在,在于對(duì)估價(jià),函,函數(shù)的定義,上,上。,估價(jià)函數(shù),f,：,f(n)=g(n)+h(n),g(n),：就是到目,前,前為止用搜,索,索算法找到,的,的從,S,到,n,的最小路徑,代,代價(jià)

39、。,h(n),：,依賴于有關(guān),問(wèn),問(wèn)題的領(lǐng)域,的,的啟發(fā)信息,。,。,從節(jié)點(diǎn),n,到某目標(biāo)節(jié),點(diǎn),點(diǎn)的一條最,佳,佳路徑的代,價(jià),價(jià),的估計(jì)。,,例：八數(shù)碼,難,難題,,,,,解：,采用,估,估價(jià),函,函數(shù),f(n)=d(n)+W(n),其中,：,：,d(n),是搜,索,索樹(shù),中,中節(jié),點(diǎn),點(diǎn),n,的深,度,度；,W(n),用來(lái),計(jì),計(jì)算,對(duì),對(duì)應(yīng),于,于節(jié),點(diǎn),點(diǎn),n,的數(shù),據(jù),據(jù)庫(kù),中,中錯(cuò),放,放的,棋,棋子,個(gè),個(gè)數(shù),。,。,因此，起,始,始節(jié)點(diǎn)棋,局,局的,f,值等于,0+3=3,。,,Sg,S,0,3,4,4,5,5,5,6,4,6,4,4,6,3.4,消解,原,原理,重點(diǎn),掌,掌

40、握,子,子句,集,集的,求,求解,步,步驟,和,和消,解,解反,演,演過(guò),程,程，,掌,掌握,消,消解,推,推理,的,的規(guī),則,則。,3.4.1,子句,集,集的,求,求取,例、,將,將下,列,列謂,詞,詞演,算,算公,式,式化,為,為一,個(gè),個(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

41、(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

42、){~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)),~P(x),?,Q(x,g(x)),~P(x),?,~ P(g(x)),(9),更改變,量,量名稱,，,，在上,述,述第（,8,）步的,3,個(gè)子句,中,中，分,別,別以,x1,x2,x3,代替變,量,量,x,。這種,更,更改變,量

43、,量名稱,的,的過(guò)程,，,，有時(shí),稱,稱為變,量,量分離,標(biāo),標(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ò),過(guò)程,1,、消解,反,反演,給出一,個(gè),個(gè)公式,集,集,S,和目標(biāo),公,公式,L,，通過(guò),反,反證或,反,反演來(lái),求,求證目,標(biāo),標(biāo)公式,L,，其證

44、,明,明步驟,如,如下：,(1),否定,L,，得～,L,；,(2),把～,L,添加到,S,中去；,(3),把新產(chǎn),生,生的集,合,合｛～,L,，,S,｝化成,子,子句集,；,；,(4),應(yīng)用消,解,解原理,，,，力圖,推,推導(dǎo)出,一,一個(gè)表,示,示矛盾,的,的空子,句,句,NIL,。,例,1,、,判斷下,列,列子句,集,集中哪,些,些是不,可,可滿足,的,的,分析：,子,子句集,中,中各子,句,句間的,關(guān),關(guān)系是,合,合取關(guān),系,系，因,此,此只要,有,有一個(gè),子,子句不,可,可滿足,，,，則子,句,句集就,是,是不可,滿,滿足的,。,。,(1)NIL(,空子句,),是不可,滿,滿足的,。,。

45、,(2),在子句,集,集中選,擇,擇合適,的,的子句,對(duì),對(duì)其進(jìn),行,行消解,，,，若能,推,推出空,子,子句，,就,就說(shuō)明,子,子句,S,是不可,滿,滿足的,。,。,(1)S={,～,P∨Q,，～,Q,，,P,，～,P,},對(duì)子句,集,集,S,進(jìn)行歸,結(jié),結(jié)推理,：,：,(1),～,P∨Q,(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ǔ),補(bǔ)對(duì)，,故,故在子,句,句集,S,

46、中不存,在,在空子,句,句，故,S,為,可滿,足,足的,。,。,,例,2,證明,(,?,x)(P(x),?(,Q(x),∧,∧R(x))),∧,∧(,?x,)(P(x)∧T(x)),?(,?,?x)(T(x),∧,∧R(x)),證明,：,：第,一,一步,：,：先,對(duì),對(duì)結(jié),論,論否,定,定并,與,與前,提,提合,并,并得,到,到謂,詞,詞公,式,式,G,。,G=(,?,x)(P(x),?(,Q(x),∧,∧R(x))),∧,∧(,?x,)(P(x)∧T(x)),∧,∧,～,(?x)(T(x)∧R(x)),第二,步,步：,將,將公,式,式,G,化為,子,子句,集,集。,可將,G,看作,是,是三,

47、項(xiàng),項(xiàng)的,合,合取,，,，對(duì),每,每一,項(xiàng),項(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={,P(a),T(a)},～,B:,～,(?x)(T(x)∧R(x)),=(,?,?x)(,～,T(x),∨,∨,～,R(x)),所以,S,～,B,={

48、,～,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)},第三,步,步：,例,例用,消,消解,原,原理,，,，對(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,也是不

49、,可,可滿足,的,的。從,而,而命題,得,得證。,例,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é)論,為,為

50、,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),行,行消解,：,：,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é),結(jié)論：,公,公司一,定,定錄取,C,2,、反演,求,求解過(guò),程,程,步驟,：,：,(1),把已,知,知前,提,提用,謂,謂詞,公,公式,表,表示,出

51、,出來(lái),，,，并,化,化為,相,相應(yīng),的,的子,句,句集,S,。,(,2,),把,待求,解,解的,問(wèn),問(wèn)題,也,也用,謂,謂詞,公,公式,表,表示,出,出來(lái),，,，然,后,后把,它,它的,否,否定,與,與謂,詞,詞,ANSWER,構(gòu)成,析,析取,式,式。,(,3,),把第,(2),步得,到,到的,析,析取,式,式化,為,為子,句,句集,，,，并,入,入子,句,句集,S,中，,得,得到,子,子句,集,集,S,’,。,(4),對(duì)子,句,句集,S,’,應(yīng)用,消解,原理,進(jìn),進(jìn)行,消,消解,。,。,(,5,),若得,答,答案,ANSWER,，則,答,答案,就,就在,ANSWER,中,。,例,1,：,應(yīng)

52、用,消,消解,反,反演,求,求解,如,如下,問(wèn),問(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

53、)(,～,AT(FIDO,x)),其子,句,句形,為,為：,～,～,AT(FIDO,x),對(duì)本,例,例應(yīng),用,用消,解,解反,演,演過(guò),程,程：,（,1,）目,標(biāo),標(biāo)公,式,式否,定,定的,子,子句,形,形為,：,：,～,AT(FIDO,x),將它,與,與謂,詞,詞,ANSWER,構(gòu)成,析,析取,式,式：,～,AT(FIDO,x),∨,∨ANSWER(FIDO,x),（,2,）用,下,下圖,的,的反,演,演樹(shù),進(jìn),進(jìn)行,消,消解,，,，并,在,在根,部,部得,到,到子,句,句：,A,NSWER,(FIDO,SCHOOL),～,AT(FIDO,x)∨ANSWER(FIDO,x),～,AT(JOH

54、N,y)∨AT(FIDO,y),～,AT(JOHN,x)∨ANSWER(FIDO,x),AT(JOHN,SCHOOL),ANSWER(FIDO,SCHOOL),?1={x/y},?2={SCHOOL/x},例,2,某公,司,司招,聘,聘人,員,員，,A,、,B,、,C,三人,應(yīng),應(yīng)試,，,，經(jīng),面,面試,后,后，,公,公司,有,有如,下,下想,法,法：,(1),三人,中,中至,少,少錄,用,用一,人,人；,(2),如果,錄,錄用,A,而不,錄,錄用,B,，則,一,一定,錄,錄用,C,；,(3),如果,錄,錄用,B,，則,一,一定,錄,錄用,C,。,求公,司,司錄,用,用誰(shuí),？,？,解：,定,定

55、,義,義：,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),將前,提,提化,為,為子,句,句集,：,：,(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(

56、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,例,3,已知,（,（,1,）王,是,是李,的,的老,師,師,（,2,）李,是,是張,的,的同,學(xué),學(xué),（,3,）如,果,果,x,與,y,是同,學(xué),學(xué)，,則,則,x,的老,師,師也,是,是,y,的老,師,師。,求：,張,張的,老,老師,是,是誰(shuí),？,？,,解：,令,令,T(x,y):x,是,y,的老,師,師；,C(x,y),：,x,是,y,的同,學(xué),學(xué),,,則,已知,的,的三,個(gè),個(gè)事

57、,實(shí),實(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),將上,述,述事,實(shí),實(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

58、(w,Zhang),用下,圖,圖的,反,反演,樹(shù),樹(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),統(tǒng),1,、產(chǎn),生,生式,系,系統(tǒng),的,的組,成,成,產(chǎn)生,式,式系,統(tǒng),統(tǒng)由

59、,3,個(gè)部,分,分組,成,成，,即,即總,數(shù),數(shù)據(jù),庫(kù),庫(kù),(,或全,局,局?jǐn)?shù),據(jù),據(jù)庫(kù),),、產(chǎn),生,生式,規(guī),規(guī)則,和,和控,制,制策,略,略，,總數(shù)據(jù),庫(kù),庫(kù)又稱,為,為綜合,數(shù),數(shù)據(jù)庫(kù),、,、上下,文,文、黑,板,板等，,用,用于存,放,放求解,過(guò),過(guò)程中,各,各種當(dāng),前,前信息,的,的數(shù)據(jù),結(jié),結(jié)構(gòu)，,如,如問(wèn)題,是,是的初,始,始狀態(tài),、,、事實(shí),或,或證據(jù),、,、中間,推,推理結(jié),論,論和最,后,后結(jié)果,等,等。,產(chǎn)生式,規(guī),規(guī)則是,一,一個(gè)規(guī),則,則庫(kù)，,用,用于存,放,放與求,解,解問(wèn)題,有,有關(guān)的,某,某個(gè)領(lǐng),域,域知識(shí),的,的規(guī)則,之,之集合,及,及其交,換,換規(guī)則,。,

60、。,其基本,形,形式為,IF,前提,THEN,結(jié)論,控制策,略,略的作,用,用是說(shuō),明,明下一,步,步應(yīng)該,選,選用什,么,么規(guī)則,。,。,2,、例：,設(shè),設(shè)有八,數(shù),數(shù)碼難,題,題：,,,,,,請(qǐng)用產(chǎn),生,生式規(guī),則,則表示,移,移動(dòng)小,方,方塊的,操,操作。,初始狀,態(tài),態(tài),目標(biāo)狀,態(tài),態(tài),,解：,1,）建立,棋,棋盤變,換,換的產(chǎn),生,生式規(guī),則,則。,如果把,棋,棋盤的,每,每一布,局,局看作,是,是一個(gè),狀,狀態(tài)矩,陣,陣，本,題,題就變,成,成了從,初,初始狀,態(tài),態(tài)矩陣,到,到目標(biāo),狀,狀態(tài)矩,陣,陣的一,種,種變化,。,。,設(shè),S,ij,為狀態(tài),矩,矩陣的,第,第,i,行和第,

61、j,列的數(shù),碼,碼，其,中,中,3≥i, j,≥,≥1,。,i,0,,j,0,表示空,格,格所在,的,的行和,列,列。如,果,果在狀,態(tài),態(tài)矩陣,中,中用,0,來(lái)表示,空,空格的,話,話，則,建,建立如,下,下四條,產(chǎn),產(chǎn)生式,規(guī),規(guī)則：,R1:if (j,0,-1≥1)then begin,S,i0j0,:=S,i0(j0-1),;,S,i0(j0-1),:=0end,空格左,移,移,,R2:if (i,0,-1≥1)then begin,S,i0j0,:=S,(i0-1)j0,;,S,(i0-1)j0,:=0end,空格上,移,移,R3:if (j,0,+1≤3)then begin,S,

62、i0j0,:=S,i0(j0+1),;,S,i0(j0+1),:=0end,空格右,移,移,R4:if (i,0,+1≤3)then begin,S,i0j0,:=S,(i0+1)j0,;,S,(i0+1)j0,:=0end,空格下,移,移,2,）建立,綜,綜合數(shù),據(jù),據(jù)庫(kù),將棋盤,的,的布局,表,表示為,狀,狀態(tài)矩,陣,陣的形,式,式存入,綜,綜合數(shù),據(jù),據(jù)庫(kù)。,例如，,初,初始布,局,局和目,標(biāo),標(biāo)布局,以,以矩陣,形,形式表,示,示為：,綜合數(shù),據(jù),據(jù)庫(kù)中,，,，存放,著,著初始,狀,狀態(tài)矩,陣,陣和目,標(biāo),標(biāo)狀態(tài),矩,矩陣以,及,及變換,過(guò),過(guò)程中,的,的中間,矩,矩陣。,3,）推理,

63、求,求解,在進(jìn)行,推,推理求,解,解時(shí)，,可,可能會(huì),有,有多條,產(chǎn),產(chǎn)生式,規(guī),規(guī)則的,條,條件部,分,分和綜,合,合數(shù)據(jù),庫(kù),庫(kù)中的,已,已有事,實(shí),實(shí)相符,，,，這樣,就,就有可,能,能激活,多,多條規(guī),則,則。,究竟采用哪,一,一條規(guī)則作,為,為啟用規(guī)則,規(guī),規(guī)則，這就,是,是沖突解決,策,策略問(wèn)題。,在本題中采,用,用一個(gè)啟發(fā),式,式函數(shù),f(n)=d(n)+W(n),其中：,d(n),是搜索樹(shù)中,節(jié),節(jié)點(diǎn),n,的深度；,W(n),用來(lái)計(jì)算對(duì),應(yīng),應(yīng)于節(jié)點(diǎn),n,的數(shù)據(jù)庫(kù)中,錯(cuò),錯(cuò)放的棋子,個(gè),個(gè)數(shù)。,在綜合數(shù)據(jù),庫(kù),庫(kù)中的初始,矩,矩陣，能滿,足,足規(guī)則,R1,，,R2,，,R3,，

64、,R4,的條件，所,以,以有四條匹,配,配規(guī)則。利,用,用啟發(fā)函數(shù),決,決定哪一條,規(guī),規(guī)則為啟用,規(guī),規(guī)則。因?yàn)?規(guī),規(guī)則,R1,的啟發(fā)式函,數(shù),數(shù)值,h(x)=4,，規(guī)則,R2,的啟發(fā)式函,數(shù),數(shù)值,h(x)=4,,規(guī)則,R3,的啟發(fā)式函,數(shù),數(shù)值,h(x)=5,,規(guī)則,R4,的啟發(fā)式函,數(shù),數(shù)值,h(x)=5,。在這里,R1,與,R2,所得到的新,狀,狀態(tài)與目標(biāo),狀,狀態(tài)差距最,小,小，且都為,4,，而在,R1,與,R2,中再選擇一,條,條規(guī)則作為,啟,啟用規(guī)則，,在,在這里我們,使,使用規(guī)則的,排,排列順序，,首,首先選擇,R1,，所以啟用,規(guī),規(guī)則,R1,，依次類推,。,。,可以得到到,達(dá),達(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ī)則。,Sg,S,0,3,4,4,5,5,5,6,4,6,4,4,6,R1,R2,R3,R4,R2,R4,R1,R3,R4,R3,R4,演講完畢，,謝,謝謝觀看！,