單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,,,?#?,人工智能及其應用,,,,,制作人：王思文,,劉玉奇,,于斌,,第,1,章　緒論,,1,、重點掌握,人工智能的幾種定義,。,2,、掌握目前,人工智能的三個主要學派,及 其認知觀。,3,、一般了解人工智能的主要研究范圍和 應用領(lǐng)域。,,定義,2,人工智能,(,學科,),人工智能,(,學科,),是計算機科學中涉及研究、設計和應用智能機器的一個分支。它的近期主要目標在于研究用機器來模仿和執(zhí)行人腦的某些智力功能，并開發(fā)相關(guān)理論和技術(shù)。,定義,3,人工智能,(,能力,),人工智能,(,能力,),是智能機器所執(zhí)行的通常與人類智能有關(guān)的智能行為，如判斷、推理、證明、識別、感知、理解、通信、設計、思考、規(guī)劃、學習和問題求解等思維活動。,,人工智能的三大學派及其認知觀：,(1),符號主義 認為人工智能起源于數(shù)理邏輯。,(2),連接主義 認為人工智能起源于仿生學，特別是對人腦模型的研究。,(3),行為主義 認為人工智能起源于控制論。,,第,2,章　知識表示方法,重點掌握用狀態(tài)空間法、問題歸約法、謂詞邏輯法、語義網(wǎng)絡法、框架表示法來描述問題，解決問題；,2.1,狀態(tài)空間法,,許多問題求解方法是采用試探搜索方法的。也就是說，這些方法是通過在某個可能的解空間內(nèi)尋找一個解來求解問題的。這種基于解答空間的問題表示和求解方法就是狀態(tài)空間法，它是以狀態(tài)和算符,(operator),為基礎來表示和求解問題的。,,,2.1,狀態(tài)空間法,狀態(tài)空間法三要點,,(1),狀態(tài),（,state,）,：表示問題解法中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)；,,(2),算符,（,operator,）：把問題從一種狀態(tài)變換為另一種狀態(tài)的手段；,,(3),狀態(tài)空間方法,：基于解答空間的問題表示和求解方法，它是以狀態(tài)和算符為基礎來表示和求解問題的。,2.1,狀態(tài)空間法,由上可知，對一個問題的狀態(tài)描述，必須確定,3,件事：,(1),該狀態(tài)描述方式，特別是初始狀態(tài)描述；,(2),操作符集合及其對狀態(tài)描述的作用；,(3),目標狀態(tài)描述的特性。,,,例,2,：,(,分油問題,),有,A,、,B,、,C,三個不帶刻度的瓶子，分別能裝,8kg, 5kg,和,3kg,油。如果,A,瓶裝滿油，,B,和,C,是空瓶，怎樣操作三個瓶，使,A,中的油平分兩份？,(,假設分油過程中不耗油,),,解：第,一,一步：,定,定義,問,問題狀,態(tài),態(tài)的描,述,述形式,：,：,設,S,k,=(b,c),表示,B,瓶和,C,瓶中的,油,油量的,狀,狀態(tài)。,其中：,b,表示,B,瓶中的,油,油量。,c,表示,C,瓶中的,油,油量。,初始狀,態(tài),態(tài)集：,S={(0,0)},目標狀,態(tài),態(tài)集：,G={(4,0)},,第二步,：,： 定,義,義操作,符,符：,操作：,把,把瓶子,倒,倒?jié)M油,，,，或把,瓶,瓶子的,油,油倒空,。,。,f1,：從,A,瓶往,B,瓶倒油,，,，把,B,瓶倒?jié)M,。,。,f2,：從,C,瓶往,B,瓶倒油,，,，把,B,瓶倒?jié)M,。,。,f3,：從,A,瓶往,C,瓶倒油,，,，把,C,瓶倒?jié)M,。,。,f4,：從,B,瓶往,C,瓶倒油,，,，把,C,瓶倒?jié)M,。,。,f5,：從,B,瓶往,A,瓶倒油,，,，把,B,瓶倒空,。,。,f6,：從,B,瓶往,C,瓶倒油,，,，把,B,瓶倒空,。,。,f7,：從,C,瓶往,A,瓶倒油,，,，把,C,瓶倒空,。,。,f8,：從,C,瓶往,B,瓶倒油,，,，把,C,瓶倒空,。,。,第三步,：,： 求,解,解過程,：,：,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,。,。,,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)空間圖,，,，可見從,初,初始狀態(tài),(0,1),到目標狀,態(tài),態(tài),(4,0),的任何一,條,條通路都,是,是問題的,一,一個解。,其,其中：,{f1,f4,f7,f6,f1,f4,f7},是算符最,少,少的解之,一,一。,例：設有,3,個傳教士,和,和,3,個野人來,到,到河邊，,打,打算乘一,只,只船從右,岸,岸渡到左,岸,岸去。該,船,船的負載,能,能力為兩,人,人。在任,何,何時候，,如,如果野人,人,人數(shù)超過,傳,傳教士人,數(shù),數(shù)，那么,野,野人就會,把,把傳教士,吃,吃掉。他,們,們怎樣才,能,能用這條,船,船安全地,把,把所有人,都,都渡過河,去,去？,,,解：第一,步,步： 定,義,義問題狀,態(tài),態(tài)的描述,形,形式：,設,S,k,=(M,C,B),表示傳教,士,士和野人,在,在河右岸,的,的狀態(tài)。,其中：,M,表示傳教,士,士在右岸,的,的人數(shù)。,C,表示野人,在,在右岸的,人,人數(shù)。,B,用來表示,船,船是不是,在,在右岸。,(B=1,表示在右,岸,岸，,B=0,表示在左,岸,岸,),。,初始狀態(tài),集,集：,S={(3,3,1)},目標狀態(tài),集,集：,G={(0,0,0)},第二步：,定,定義算符,。,。,算符,R(i,j),表示劃船,將,將,i,個傳教士,和,和,j,個野人送,到,到左岸的,操,操作。,算符,L(i,j),表示劃船,從,從左岸將,i,個傳教士,和,和,j,個野人帶,回,回右岸的,操,操作。,由于過河,的,的船每次,最,最多載兩,個,個人，所,以,以,i+j≤2,。這樣定,義,義的算符,集,集,F,中只可能,有,有如下,10,個算符。,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,0,2,2,1,3,1,1,0,2,0,3,0,0,R(2,0),L(2,0),R(1,1),L(1,1),L(0,1),R(0,1),L(2,0),R(2,0),2,2,0,3,3,1,3,2,1,3,2,0,3,1,0,L(0,2),R(0,2),R(0,1),L(0,1),L(1,0),R(1,0),L(0,1),R(0,1),L(1,1),R(1,1),L(0,2),R(0,2),1,1,1,0,0,0,0,1,0,0,1,1,0,2,1,R(0,1),L(1,0),L(0,1),R(0,1),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)空間圖,，,，可見從,初,初始狀態(tài),(3,3,1),到目標狀,態(tài),態(tài),(0,0,0),的任何一,條,條通路都,是,是問題的,一,一個解。,其中：,{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,問題歸約,法,法,問題歸約,法,法的概念,已知問題,的,的描述，,通,通過一系,列,列變換把,此,此問題最,終,終變?yōu)橐?個,個子問題,集,集合；這,些,些子問題,的,的解可以,直,直接得到,，,，從而解,決,決了初始,問,問題。,該方法也,就,就是從目,標,標,(,要解決的,問,問題,),出發(fā)逆向,推,推理，建,立,立子問題,以,以及子問,題,題的子問,題,題，直至,最,最后把初,始,始問題歸,約,約為一個,平,平凡的本,原,原問題集,合,合。這就,是,是問題歸,約,約的實質(zhì),。,。,,2.2,問題歸約,法,法,問題歸約,法,法的組成,部,部分,（,1,）一個初,始,始問題描,述,述；,（,2,）一套把,問,問題變換,為,為子問題,的,的操作符,；,；,（,3,）一套本,原,原問題描,述,述。,2.3,謂詞邏輯,法,法,一階謂詞,邏,邏輯表示,法,法適于表,示,示確定性,的,的知識。,它,它具有自,然,然性、精,確,確性、嚴,密,密性及易,實,實現(xiàn)等特,點,點。,2.3,謂詞邏輯,法,法,用一階謂,詞,詞邏輯法,表,表示知識,的,的步驟如,下,下：,（,1,）定義謂,詞,詞及個體,，,，確定每,個,個謂詞及,個,個體的確,切,切含義。,（,2,）根據(jù)所,要,要表達的,事,事物或概,念,念，為每,個,個謂詞中,的,的變元賦,以,以特定的,值,值。,（,3,）根據(jù)所,要,要表達的,知,知識的語,義,義，用適,當,當?shù)倪B接,符,符號將各,個,個謂詞連,接,接起來，,形,形成謂詞,公,公式。,例,1,：設有下,列,列事實性,知,知識：,張曉輝是,一,一名計算,機,機系的學,生,生，但他,不,不喜歡編,程,程序。李,曉,曉鵬比他,父,父親長得,高,高。,請用謂詞,公,公式表示,這,這些知識,。,。,（,1,）定義謂,詞,詞及個體,。,。,Computer(x):x,是計算機,系,系的學生,。,。,Like(x,y):x,喜歡,y,。,Higher(x,y):x,比,y,長得高。,這里涉及,的,的個體有,：,：張曉輝,(zhangxh),,編程序,(programming),,李曉鵬,(lixp),，以及函,數(shù),數(shù),father(lixp),表示李曉,鵬,鵬的父親,。,。,第二步：,將,將這些個,體,體代入謂,詞,詞中，得,到,到,Computer(zhangxh), ~Like(zhangxh, programming),Higher(lixp,father(lixp)),,第三步：,根,根據(jù)語義,，,，用邏輯,聯(lián),聯(lián)結(jié)詞將,它,它們聯(lián)結(jié),起,起來，就,得,得到了表,示,示上述知,識,識的謂詞,公,公式。,Computer(zhangxh)∧ ~Like(zhangxh, programming),Higher(lixp,father(lixp)),,例,2,：,設有下列,語,語句，請,用,用相應的,謂,謂詞公式,把,把它們表,示,示出來：,（,1,）人人愛,勞,勞動。,（,2,）自然數(shù),都,都是大于,零,零的整數(shù),。,。,（,3,）西安市,的,的夏天既,干,干燥又炎,熱,熱。,（,4,）喜歡讀,《,三國演義,》,的人必讀,《,水滸,》,。,（,5,）有的人,喜,喜歡梅花,，,，有的人,喜,喜歡菊花,，,，有的人,既,既喜歡梅,花,花又喜歡,菊,菊花。,（,6,）他每,天,天下午,都,都去打,籃,籃球。,解：,（,1,）人人,愛,愛勞動,。,。,定義謂,詞,詞如下,：,：,Man(x):x,是人。,Love(x,y):x,愛,y,。,（?,x)(Man(x),→,→Love(x,,勞動）,）,）,,,,（,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,）喜歡,讀,讀,《,三國演,義,義,》,的人必,讀,讀,《,水滸,》,。,定,定,義,義謂詞,：,：,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,,Meihua))∧,(,?y)(MAN(y),∧,LIKE(y,,Juhua))∧,(,?z)(MAN(z),∧,(LIKE(z,,Meihua),∧LIKE(z,Juhua))),,（,6,）他每,天,天下午,都,都去打,籃,籃球。,定義謂,詞,詞及個,體,體：,設,TIME(x):x,是下午,。,。,PLAY(x,y):x,去打,y,，,Liming,表示李,明,明，,Basketball,表示足,球,球，則,:,（,?,x,）,TIME(x),?,PLAY(Liming,Basketball),2.4,語義網(wǎng),絡,絡法,語義網(wǎng),絡,絡是,1968,年,J.R.Quillian,在研究,人,人類聯(lián),想,想記憶,時,時提出,的,的心理,學,學模型,。,。,,2.4,語義網(wǎng),絡,絡法,語義網(wǎng),絡,絡的概,念,念,語義網(wǎng),絡,絡是通,過,過概念,及,及其語,義,義關(guān)系,來,來表示,知,知識的,一,一種結(jié),構(gòu),構(gòu)化網(wǎng),絡,絡圖，,它,它由節(jié),點,點和弧,線,線或鏈,線,線組成,，,，節(jié)點,用,用來表,示,示各種,概,概念、,事,事物、,屬,屬性、,情,情況、,動,動作、,狀,狀態(tài)等,，,，每個,節(jié),節(jié)點可,以,以帶有,若,若干個,屬,屬性，,以,以表征,其,其所代,表,表的對,象,象的特,性,性?；?線,線用于,表,表示節(jié),點,點間的,關(guān),關(guān)系，,其,其上的,標,標注則,表,表示被,連,連接的,兩,兩個節(jié),點,點間的,某,某種語,義,義聯(lián)系,或,或語義,關(guān),關(guān)系。,,2.4,語義網(wǎng),絡,絡法,語義網(wǎng),絡,絡表示,知,知識的,方,方法及,步,步驟,（,a,）確定,問,問題中,的,的所有,對,對象以,及,及各對,象,象的屬,性,性。,（,b,）確定,所,所討論,對,對象間,的,的關(guān)系,。,。,（,c,）語義,網(wǎng),網(wǎng)絡中,，,，如果,節(jié),節(jié)點間,的,的聯(lián)系,是,是,ISA/AKO,，則下,層,層節(jié)點,對,對上層,節(jié),節(jié)點的,屬,屬性具,有,有繼承,性,性。整,理,理同一,層,層節(jié)點,的,的共同,屬,屬性，,并,并抽出,這,這些屬,性,性，加,入,入上層,節(jié),節(jié)點中,，,，以免,造,造成屬,性,性信息,的,的冗余,。,。,,（,d,）將各,對,對象作,為,為語義,網(wǎng),網(wǎng)絡的,一,一個節(jié),點,點，而,各,各對象,間,間的關(guān),系,系作為,網(wǎng),網(wǎng)絡中,各,各節(jié)點,間,間的弧,，,，連接,形,形成語,義,義網(wǎng)絡,。,。節(jié)點,可,可代表,一,一個事,物,物或一,個,個具體,概,概念，,也,也可代,表,表某種,情,情況、,事,事件或,某,某一動,作,作。當,節(jié),節(jié)點表,示,示某種,事,事件或,某,某一動,作,作時，,可,可以從,該,該節(jié)點,引,引出一,組,組向外,的,的弧，,用,用于指,出,出事件,的,的因果,或,或動作,的,的主體,及,及客體,。,。,例,1,、用一,個,個語義,網(wǎng),網(wǎng)絡表,示,示下列,命,命題。,樹和草,都,都是植,物,物；,樹和草,是,是有根,有,有葉的,；,；,水草是,草,草，且,長,長在水,中,中；,果樹是,樹,樹，且,會,會結(jié)果,；,；,蘋果樹,是,是果樹,中,中的一,種,種，它,結(jié),結(jié)蘋果,。,。,分析：,問題涉,及,及的對,象,象有：,植物、,樹,樹、草,、,、水草,、,、果樹,、,、蘋果,樹,樹,各對象,的,的屬性,分,分別為,：,：,樹和草,的,的屬性,：,：有根,、,、有葉,；,；,水草的,屬,屬性：,長,長在水,中,中；,果樹的,屬,屬性：,會,會結(jié)果,；,；,蘋果樹,的,的屬性,：,：結(jié)蘋,果,果。,植物,蘋果樹,水草,果樹,草,樹,AKO,AKO,AKO,AKO,AKO,有根,有葉,有根,有葉,會結(jié)果,結(jié)蘋果,長在水,中,中,例：用,語,語義網(wǎng),絡,絡表示,下,下列知,識,識：,獵狗是,一,一種狗,，,，而狗,是,是一種,動,動物。,狗,狗除了,動,動物的,有,有生命,、,、能吃,食,食物、,有,有繁殖,能,能力、,能,能運動,外,外，還,有,有以下,特,特點：,身,身上有,毛,毛、有,尾,尾巴、,四,四條腿,；,；獵狗,的,的特點,是,是吃肉,、,、奔跑,速,速度快,、,、能狩,獵,獵、個,頭,頭大；,而,而獅子,狗,狗也是,一,一種狗,，,，它的,特,特點是,吃,吃飼料,、,、身體,小,小、奔,跑,跑速度,慢,慢、不,咬,咬人、,供,供觀賞,。,。,,解題分,析,析,（,1,）本知,識,識涉及,的,的對象,有,有,4,個：獵,狗,狗、獅,子,子狗、,狗,狗、動,物,物。獵,狗,狗和獅,子,子狗都,是,是一種,狗,狗，除,了,了它們,本,本身的,屬,屬性外,，,，具有,狗,狗的一,般,般特性,：,：身上,有,有毛、,有,有尾巴,、,、四條,腿,腿。而,狗,狗是一,種,種動物,，,，動物,所,所具有,的,的屬性,它,它也具,有,有。,（,2,）獵狗,與,與狗之,間,間是一,種,種類屬,關(guān),關(guān)系，,狗,狗和動,物,物之間,也,也是一,種,種類屬,關(guān),關(guān)系，,它,它們都,可,可以用,AKO,表示。,（,3,）整理,各,各對象,節(jié),節(jié)點之,間,間的屬,性,性，使,上,上層節(jié),點,點所具,有,有的屬,性,性不在,下,下層節(jié),點,點中標,出,出。,（,4,）將各,對,對象作,為,為一個,節(jié),節(jié)點，,而,而它們,之,之間的,關(guān),關(guān)系作,為,為弧，,得,得到如,下,下圖所,示,示的語,義,義網(wǎng)絡,。,。,動物,獅子狗,獵狗,狗,AKO,AKO,AKO,身上有,毛,毛,有尾巴,有四條,腿,腿,跑得快,能獰獵,有生命,吃飼料,能吃食,物,物,有繁殖,能,能力,能運動,個頭大,吃肉,個頭小,跑得慢,不咬人,供觀賞,2.5,框架表,示,示,1974,年，由,Minsky,在“,A frameworkforrepresenting knowledge”,中提出,。,。,框架是,一,一種描,述,述所論,對,對象屬,性,性的數(shù),據(jù),據(jù)結(jié)構(gòu),。,。所論,對,對象可,以,以是一,個,個事物,、,、一個,事,事件或,者,者一個,概,概念。,一,一個框,架,架由若,干,干個“,槽,槽”組,成,成，每,個,個“槽,”,”又可,劃,劃分為,若,若干個,“,“側(cè)面,”,”。一,個,個槽用,于,于描述,所,所論及,對,對象的,某,某一方,面,面的屬,性,性，一,個,個側(cè)面,用,用于描,述,述相應,屬,屬性的,一,一個方,面,面。槽,和,和側(cè)面,所,所具有,的,的屬性,值,值分別,稱,稱為槽,值,值和側(cè),面,面值。,槽,槽值可,以,以是邏,輯,輯型或,數(shù),數(shù)字型,的,的，具,體,體的值,可,可以是,程,程序、,條,條件、,默,默認值,或,或是一,個,個子框,架,架。,框架表,示,示,用框架,表,表示法,表,表示知,識,識的步,驟,驟如下,：,：,（,1,）分析,待,待表達,知,知識中,的,的對象,及,及其屬,性,性，對,框,框架中,的,的槽進,行,行合理,設,設置。,（,2,）對各,對,對象間,的,的各種,聯(lián),聯(lián)系進,行,行考察,。,。使用,一,一些常,用,用的名,稱,稱或根,據(jù),據(jù)具體,需,需要定,義,義一些,表,表達聯(lián),系,系的槽,名,名，來,描,描述上,、,、下層,框,框架間,的,的聯(lián)系,。,。,（,3,）對各,層,層對象,的,的“槽,”,”及“,側(cè),側(cè)面”,進,進行合,理,理的組,織,織安排,，,，避免,信,信息描,述,述的重,復,復。,例：用,框,框架表,示,示下述,報,報道的,地,地震事,件,件,【,虛擬新,華,華社,3,月,15,日電,】,昨日,，在,云南玉,溪,溪地區(qū),發(fā)生,地震,，造成,財產(chǎn)損,失,失約,10,萬元,，統(tǒng)計,部,部門,如果需,要,要詳細,的,的損失,數(shù),數(shù)字,，可,電詢,62332931,。另據(jù),專,專家,認為震,級,級,不會超,過,過,4,級,，并認,為,為地,處無人,區(qū),區(qū)，不,會,會造成,人,人員傷,亡,亡,。,提示：,分,分析概,括,括用下,劃,劃線標,出,出的要,點,點，經(jīng),過,過概念,化,化形成,槽,槽（,slot,）、側(cè),面,面（,facet,）值。,特,特別要,注,注意，,“,值,”,（,value,）、,“,默認值,”,（,default,）、,“,如果需,要,要值,”,（,if-needed,）、,“,如果附,加,加值,”,（,if-added,）的區(qū),別,別與應,用,用，建,議,議采用,格,格式如,下,下，不,用,用的側(cè),面,面值可,刪,刪。,,,,,Frame,地震,,Slot1,：,Value,：,Default,：,If-needed,：,If-added,：,,,Slot2,：,Value,：,Default,：,If-needed,：,If-added,：,,,Slot3,：,Value,：,Default,：,If-needed,：,If-added,：,,,,解：,第一步,：,：確定,框,框架的,名,名字和,框,框架的,槽,槽。,本報道中，,涉,涉及地震的,發(fā),發(fā)生時間、,地,地點、財產(chǎn),損,損失、傷亡,人,人數(shù)、震級,大,大小等屬性,，,，所以，可,將,將時間、地,點,點、震級、,傷,傷亡人數(shù)、,財,財產(chǎn)損失等,作,作為槽名。,第二步：分,析,析本報道中,各,各對象間的,關(guān),關(guān)系。,由于報道中,只,只涉及地震,一,一件事，所,以,以該步可省,略,略。,框架名：＜地震,1,＞,時間：,3,月,14,日,,,,,,,地點：云南玉溪地區(qū),,,,,,,震級：,專家經(jīng)驗值：≤,4,級,準確值：,NIL,,,,,傷亡人數(shù)：,專家經(jīng)驗值：,0,,,,,,,財產(chǎn)損失：,大約損失：,10,萬元,if-needed,：,ASK,（電詢,62332931,）,,,第,3,章　搜索推,理,理技術(shù),重點掌握一,般,般圖搜索策,略,略和消解原,理,理，掌握各,種,種搜索方法,和,和產(chǎn)生式系,統(tǒng),統(tǒng)原理，了,解,解規(guī)則演繹,系,系統(tǒng)的基本,原,原理，對系,統(tǒng),統(tǒng)組織技術(shù),、,、不確定性,推,推理和非單,調(diào),調(diào)推理等高,級,級推理技術(shù),作,作一般性了,解,解。,,第,3,章　搜索推,理,理技術(shù),從問題表示,到,到問題的解,決,決，有一個,求,求解的過程,。,。而實現(xiàn)求,解,解的過程，,采,采用的基本,方,方法包括搜,索,索和推理。,第,3,章　搜索推,理,理技術(shù),和搜索相對,應,應的知識表,示,示法一般有,兩,兩種：,狀態(tài)空間法,：（,S,，,F,，,G,）,與或圖表示,法,法：基于一,種,種分解與變,換,換的思想，,利,利用樹狀結(jié),構(gòu),構(gòu)對復雜問,題,題進行表示,，,，使復雜問,題,題簡單化。,第,3,章　搜索推,理,理技術(shù),圖搜索策略,是,是一種在圖,中,中尋找路徑,的,的方法。,搜索種類：,盲目搜索：,只,只按預先規(guī),定,定的搜索控,制,制策略進行,搜,搜索。,啟發(fā)式搜索,：,：根據(jù)問題,本,本身的特性,或,或搜索過程,中,中產(chǎn)生的一,些,些信息來不,斷,斷改變和調(diào),整,整搜索的方,向,向。,圖搜索過程,框,框圖,開始,把,S,放入,OPEN,表,OPEN,為空表？,把第一個節(jié)點,(n),從,OPEN,移至,CLOSED,表,n,為目標節(jié)點？,把,n,的后繼節(jié)點放入,OPEN,表的,末端，提供返回節(jié)點,n,的指針,修改指針方向,重排,OPEN,表,失敗,成功,是,是,否,否,3.2,盲目搜索,盲目搜索又,叫,叫做無信息,搜,搜索，一般,只,只適用于求,解,解比較簡單,的,的問題。寬,度,度優(yōu)先搜索,和,和深度優(yōu)先,搜,搜索，屬于,盲,盲目搜索方,法,法。,,3.2.1,寬度優(yōu)先搜,索,索,搜索是以接,近,近起始節(jié)點,的,的程度依次,擴,擴展節(jié)點的,，,，如左圖所,示,示。,從,從圖可見，,這,這種搜索是,逐,逐層進行的,；,；在對下一,層,層的任一節(jié),點,點進行搜索,之,之前，必須,搜,搜索完本層,的,的所有節(jié)點,。,。,,s,L,O,M,F,P,Q,N,F,F,F,例：把寬度,優(yōu),優(yōu)先搜索應,用,用于八數(shù)碼,難,難題時所生,成,成的搜索樹,，,，這個問題,就,就是要把初,始,始棋局變?yōu)?如,如右圖所示,的,的目標棋局,問,問題：,,,,,,,,3.3,啟發(fā)式搜索,盲目搜索的,不,不足：效率,低,低，耗費過,多,多的計算空,間,間與時間。,分析前面介,紹,紹的寬度優(yōu),先,先、深度優(yōu),先,先搜索，或,等,等代價搜索,算,算法,,,其主要的差,別,別是,OPEN,表中待擴展,節(jié),節(jié)點的順序,問,問題。人們,就,就試圖找到,一,一種方法用,于,于排列待擴,展,展節(jié)點的順,序,序，即選擇,最,最有希望的,節(jié),節(jié)點加以擴,展,展，那么，,搜,搜索效率將,會,會大為提高,。,。,啟發(fā)信息：,進,進行搜索技,術(shù),術(shù)一般需要,某,某些有關(guān)具,體,體問題領(lǐng)域,的,的特性的信,息,息，把此種,信,信息叫做啟,發(fā),發(fā)信息。,把利用啟發(fā),信,信息的搜索,方,方法叫做啟,發(fā),發(fā)式搜索方,法,法。,3.3,啟發(fā)式搜索,啟發(fā)式搜索,策,策略,啟發(fā)信息用,于,于決定要擴,展,展的下一個,節(jié),節(jié)點，以免,象,象在寬度優(yōu),先,先或深度優(yōu),先,先搜索中那,樣,樣盲目地擴,展,展。,這種搜索總,是,是選擇,“,最有希望,”,的節(jié)點作為,下,下一個被擴,展,展的節(jié)點。,這,這種搜索叫,做,做有序搜索,(ordered search),。,3.2.1,有序搜索,有序搜索又,稱,稱為最好優(yōu),先,先搜索，它,總,總是選擇最,有,有希望的節(jié),點,點作為下一,個,個要擴展的,節(jié),節(jié)點。,估價函數(shù),f,的確定：一,個,個節(jié)點的希,望,望程度越大,，,，則其,f,值越小。為,此,此，被選為,擴,擴展的節(jié)點,，,，是估價函,數(shù),數(shù)最小的節(jié),點,點。,f,是從起始節(jié),點,點約束地通,過,過節(jié)點,n,而到達目標,節(jié),節(jié)點的最小,代,代價路徑上,的,的一個估算,代,代價,。,3.3.1,有序搜索,寬度優(yōu)先搜,索,索、等代價,搜,搜索和深度,優(yōu),優(yōu)先搜索統(tǒng),統(tǒng),統(tǒng)是有序搜,索,索技術(shù)的特,例,例。,對于寬度優(yōu),先,先搜索，我,們,們選擇,f(i),作為節(jié)點,i,的深度。對,于,于等代價搜,索,索，,f(i),是從起始節(jié),點,點至節(jié)點,i,這段路徑的,代,代價。,3.3.2A,*,算法,A*,算法是一種,有,有序搜索算,法,法，其特點,在,在于對估價,函,函數(shù)的定義,上,上。,估價函數(shù),f,：,f(n)=g(n)+h(n),g(n),：就是到目,前,前為止用搜,索,索算法找到,的,的從,S,到,n,的最小路徑,代,代價。,h(n),：,依賴于有關(guān),問,問題的領(lǐng)域,的,的啟發(fā)信息,。,。,從節(jié)點,n,到某目標節(jié),點,點的一條最,佳,佳路徑的代,價,價,的估計。,,例：八數(shù)碼,難,難題,,,,,解：,采用,估,估價,函,函數(shù),f(n)=d(n)+W(n),其中,：,：,d(n),是搜,索,索樹,中,中節(jié),點,點,n,的深,度,度；,W(n),用來,計,計算,對,對應,于,于節(jié),點,點,n,的數(shù),據(jù),據(jù)庫,中,中錯,放,放的,棋,棋子,個,個數(shù),。,。,因此，起,始,始節(jié)點棋,局,局的,f,值等于,0+3=3,。,,Sg,S,0,3,4,4,5,5,5,6,4,6,4,4,6,3.4,消解,原,原理,重點,掌,掌握,子,子句,集,集的,求,求解,步,步驟,和,和消,解,解反,演,演過,程,程，,掌,掌握,消,消解,推,推理,的,的規(guī),則,則。,3.4.1,子句,集,集的,求,求取,例、,將,將下,列,列謂,詞,詞演,算,算公,式,式化,為,為一,個,個子,句,句集,(,?,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)]}},(4) (,?,x){~P(x),?{,(,?,y)[~P(y),?,P(f(x,y))],?,[Q(x,g(x)),?,~ P(g(x))]}},式中,w=g(x),為一個,Skolem,函數(shù),(5) (,?,x)(,?,y){~P(x),?{,[~P(y),?,P(f(x,y))],?,[Q(x,g(x)),?,~ P(g(x))]}},,(3) (,?,x){~P(x),?{,(,?,y)[~P(y),?,P(f(x,y))],?,(,?,w)[Q(x,w),?,~ P(w)]}},(6) (,?,x)(,?,y){[~P(x),?,~P(y),?,P(f(x,y))],?,[~P(x),?,Q(x,g(x))],?[,~P(x),?,~ P(g(x))]},,(8)~P(x),?,~P(y),?,P(f(x,y)),~P(x),?,Q(x,g(x)),~P(x),?,~ P(g(x)),(9),更改變,量,量名稱,，,，在上,述,述第（,8,）步的,3,個子句,中,中，分,別,別以,x1,x2,x3,代替變,量,量,x,。這種,更,更改變,量,量名稱,的,的過程,，,，有時,稱,稱為變,量,量分離,標,標準化,。,。于是,，,，可以,得,得到下,列,列子句,集,集：,~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,消解反,演,演求解,過,過程,1,、消解,反,反演,給出一,個,個公式,集,集,S,和目標,公,公式,L,，通過,反,反證或,反,反演來,求,求證目,標,標公式,L,，其證,明,明步驟,如,如下：,(1),否定,L,，得～,L,；,(2),把～,L,添加到,S,中去；,(3),把新產(chǎn),生,生的集,合,合｛～,L,，,S,｝化成,子,子句集,；,；,(4),應用消,解,解原理,，,，力圖,推,推導出,一,一個表,示,示矛盾,的,的空子,句,句,NIL,。,例,1,、,判斷下,列,列子句,集,集中哪,些,些是不,可,可滿足,的,的,分析：,子,子句集,中,中各子,句,句間的,關(guān),關(guān)系是,合,合取關(guān),系,系，因,此,此只要,有,有一個,子,子句不,可,可滿足,，,，則子,句,句集就,是,是不可,滿,滿足的,。,。,(1)NIL(,空子句,),是不可,滿,滿足的,。,。,(2),在子句,集,集中選,擇,擇合適,的,的子句,對,對其進,行,行消解,，,，若能,推,推出空,子,子句，,就,就說明,子,子句,S,是不可,滿,滿足的,。,。,(1)S={,～,P∨Q,，～,Q,，,P,，～,P,},對子句,集,集,S,進行歸,結(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),},解：因,子,子句集,中,中無互,補,補對，,故,故在子,句,句集,S,中不存,在,在空子,句,句，故,S,為,可滿,足,足的,。,。,,例,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,化為,子,子句,集,集。,可將,G,看作,是,是三,項,項的,合,合取,，,，對,每,每一,項,項分,別,別求,子,子句,集,集。,,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)},第三,步,步：,例,例用,消,消解,原,原理,，,，對,子,子句,集,集,S,進行消,解,解,～,P(x2)∨R(x2),P(a),R(a),～,T(x3)∨,～,R(x3),～,T(a),?,1,={a/x2},T(a),?,2,={a/x3},NIL,由此得,出,出子句,集,集,S,是不可,滿,滿足的,，,，因此,公,公式,G,也是不,可,可滿足,的,的。從,而,而命題,得,得證。,例,3,某公司,招,招聘人,員,員，,A,、,B,、,C,三人應,試,試，經(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),將前提,化,化為子,句,句集：,(1),P(A)∨P(B),∨,∨P(C),(2),～,P(A)∨P(B),∨,∨P(C),(3),～,P(B)∨,P(C),將結(jié)論,否,否定并,化,化為子,句,句集：,(4),～,P(C),利用消,解,解原理,，,，對子,句,句集進,行,行消解,：,：,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,、反演,求,求解過,程,程,步驟,：,：,(1),把已,知,知前,提,提用,謂,謂詞,公,公式,表,表示,出,出來,，,，并,化,化為,相,相應,的,的子,句,句集,S,。,(,2,),把,待求,解,解的,問,問題,也,也用,謂,謂詞,公,公式,表,表示,出,出來,，,，然,后,后把,它,它的,否,否定,與,與謂,詞,詞,ANSWER,構(gòu)成,析,析取,式,式。,(,3,),把第,(2),步得,到,到的,析,析取,式,式化,為,為子,句,句集,，,，并,入,入子,句,句集,S,中，,得,得到,子,子句,集,集,S,’,。,(4),對子,句,句集,S,’,應用,消解,原理,進,進行,消,消解,。,。,(,5,),若得,答,答案,ANSWER,，則,答,答案,就,就在,ANSWER,中,。,例,1,：,應用,消,消解,反,反演,求,求解,如,如下,問,問題,：,：,“如,果,果無,論,論約,翰,翰,(John),到哪,里,里去,，,，菲,多,多,(Fido),也就,去,去那,里,里，,那,那么,如,如果,約,約翰,在,在學,校,校里,，,，菲,多,多在,哪,哪里,呢,呢,?”,解：,定,定義,謂,謂詞,：,：,AT,（,x,y,）表,示,示,x,在,y,那里,。,。,則前,提,提為,：,：,(,?,x)(AT(JOHN,x),?,AT,(FIDO,x),和,AT(JOHN,SCHOOL),目標,公,公式,：,：,(,?,x,)AT(FIDO,x),目標,公,公式,否,否定,為,為：,(,?,x)(,～,AT(FIDO,x)),其子,句,句形,為,為：,～,～,AT(FIDO,x),對本,例,例應,用,用消,解,解反,演,演過,程,程：,（,1,）目,標,標公,式,式否,定,定的,子,子句,形,形為,：,：,～,AT(FIDO,x),將它,與,與謂,詞,詞,ANSWER,構(gòu)成,析,析取,式,式：,～,AT(FIDO,x),∨,∨ANSWER(FIDO,x),（,2,）用,下,下圖,的,的反,演,演樹,進,進行,消,消解,，,，并,在,在根,部,部得,到,到子,句,句：,A,NSWER,(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},例,2,某公,司,司招,聘,聘人,員,員，,A,、,B,、,C,三人,應,應試,，,，經(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),將前,提,提化,為,為子,句,句集,：,：,(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),利用,消,消解,原,原理,，,，對,子,子句,集,集進,行,行消,解,解：,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,例,3,已知,（,（,1,）王,是,是李,的,的老,師,師,（,2,）李,是,是張,的,的同,學,學,（,3,）如,果,果,x,與,y,是同,學,學，,則,則,x,的老,師,師也,是,是,y,的老,師,師。,求：,張,張的,老,老師,是,是誰,？,？,,解：,令,令,T(x,y):x,是,y,的老,師,師；,C(x,y),：,x,是,y,的同,學,學,,,則,已知,的,的三,個,個事,實,實可,解,解釋,為,為下,列,列公,式,式集,T(Wang,Li),C(Li,Zhang),(?x)(?y)(?z){C(x,y)∧T(z,x)=>T(z,y)},目標,公,公式,：,：,(,?,x)T(x,Zhang),將上,述,述事,實,實化,為,為子,句,句集,：,：,①,T(Wang,Li),②,C(Li,Zhang),③,～,C(x,y),∨,∨,～,T(z,x),∨,∨,T(z,y),目標,公,公式,否,否定,的,的子,句,句形,為,為：,～,T(x,Zhang),將它,與,與謂,詞,詞,ANSWER,構(gòu)成,析,析取,式,式：,④,～,T(w,Zhang),∨,∨ANSWER(w,Zhang),用下,圖,圖的,反,反演,樹,樹進,行,行消,解,解，,并,并在,根,根部,得,得到,子,子句,：,～,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)由,3,個部,分,分組,成,成，,即,即總,數(shù),數(shù)據(jù),庫,庫,(,或全,局,局數(shù),據(jù),據(jù)庫,),、產(chǎn),生,生式,規(guī),規(guī)則,和,和控,制,制策,略,略，,總數(shù)據(jù),庫,庫又稱,為,為綜合,數(shù),數(shù)據(jù)庫,、,、上下,文,文、黑,板,板等，,用,用于存,放,放求解,過,過程中,各,各種當,前,前信息,的,的數(shù)據(jù),結(jié),結(jié)構(gòu)，,如,如問題,是,是的初,始,始狀態(tài),、,、事實,或,或證據(jù),、,、中間,推,推理結(jié),論,論和最,后,后結(jié)果,等,等。,產(chǎn)生式,規(guī),規(guī)則是,一,一個規(guī),則,則庫，,用,用于存,放,放與求,解,解問題,有,有關(guān)的,某,某個領(lǐng),域,域知識,的,的規(guī)則,之,之集合,及,及其交,換,換規(guī)則,。,。,其基本,形,形式為,IF,前提,THEN,結(jié)論,控制策,略,略的作,用,用是說,明,明下一,步,步應該,選,選用什,么,么規(guī)則,。,。,2,、例：,設,設有八,數(shù),數(shù)碼難,題,題：,,,,,,請用產(chǎn),生,生式規(guī),則,則表示,移,移動小,方,方塊的,操,操作。,初始狀,態(tài),態(tài),目標狀,態(tài),態(tài),,解：,1,）建立,棋,棋盤變,換,換的產(chǎn),生,生式規(guī),則,則。,如果把,棋,棋盤的,每,每一布,局,局看作,是,是一個,狀,狀態(tài)矩,陣,陣，本,題,題就變,成,成了從,初,初始狀,態(tài),態(tài)矩陣,到,到目標,狀,狀態(tài)矩,陣,陣的一,種,種變化,。,。,設,S,ij,為狀態(tài),矩,矩陣的,第,第,i,行和第,j,列的數(shù),碼,碼，其,中,中,3≥i, j,≥,≥1,。,i,0,,j,0,表示空,格,格所在,的,的行和,列,列。如,果,果在狀,態(tài),態(tài)矩陣,中,中用,0,來表示,空,空格的,話,話，則,建,建立如,下,下四條,產(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,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ù)庫,將棋盤,的,的布局,表,表示為,狀,狀態(tài)矩,陣,陣的形,式,式存入,綜,綜合數(shù),據(jù),據(jù)庫。,例如，,初,初始布,局,局和目,標,標布局,以,以矩陣,形,形式表,示,示為：,綜合數(shù),據(jù),據(jù)庫中,，,，存放,著,著初始,狀,狀態(tài)矩,陣,陣和目,標,標狀態(tài),矩,矩陣以,及,及變換,過,過程中,的,的中間,矩,矩陣。,3,）推理,求,求解,在進行,推,推理求,解,解時，,可,可能會,有,有多條,產(chǎn),產(chǎn)生式,規(guī),規(guī)則的,條,條件部,分,分和綜,合,合數(shù)據(jù),庫,庫中的,已,已有事,實,實相符,，,，這樣,就,就有可,能,能激活,多,多條規(guī),則,則。,究竟采用哪,一,一條規(guī)則作,為,為啟用規(guī)則,規(guī),規(guī)則，這就,是,是沖突解決,策,策略問題。,在本題中采,用,用一個啟發(fā),式,式函數(shù),f(n)=d(n)+W(n),其中：,d(n),是搜索樹中,節(jié),節(jié)點,n,的深度；,W(n),用來計算對,應,應于節(jié)點,n,的數(shù)據(jù)庫中,錯,錯放的棋子,個,個數(shù)。,在綜合數(shù)據(jù),庫,庫中的初始,矩,矩陣，能滿,足,足規(guī)則,R1,，,R2,，,R3,，,R4,的條件，所,以,以有四條匹,配,配規(guī)則。利,用,用啟發(fā)函數(shù),決,決定哪一條,規(guī),規(guī)則為啟用,規(guī),規(guī)則。因為,規(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)與目標,狀,狀態(tài)差距最,小,小，且都為,4,，而在,R1,與,R2,中再選擇一,條,條規(guī)則作為,啟,啟用規(guī)則，,在,在這里我們,使,使用規(guī)則的,排,排列順序，,首,首先選擇,R1,，所以啟用,規(guī),規(guī)則,R1,，依次類推,。,。,可以得到到,達,達目標狀態(tài),的,的規(guī)則執(zhí)行,序,序列如下：,R1,，,R2,，,R1,，,R4,，,R3,其執(zhí)行過程,如,如下圖所示,。,。,圖中節(jié)點旁,所,所標數(shù)字為,h(x),的值，箭頭,上,上所標為啟,用,用的規(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,演講完畢，,謝,謝謝觀看！,