...wd......wd......wd...第1章人工智能概述課后題答案1.1什么是智能?智能包含哪幾種能力解：智能主要是指人類的自然智能。一般認(rèn)為，智能是是一種認(rèn)識客觀事物和運用知識解決問題的綜合能力。智能包含感知能力，記憶與思維能力，學(xué)習(xí)和自適應(yīng)能力，行為能力1.2人類有哪幾種思維方式?各有什么特點解：人類思維方式有形象思維、抽象思維和靈感思維形象思維也稱直感思維，是一種基于形象概念，根據(jù)感性形象認(rèn)識材料，對客觀對象進展處理的一種思維方式。抽象思維也稱邏輯思維，是一種基于抽象概念，根據(jù)邏輯規(guī)則對信息或知識進展處理的理性思維形式。靈感思維也稱頓悟思維，是一種顯意識與潛意識相互作用的思維方式。1.3什么是人工智能?它的研究目標(biāo)是什么解：從能力的角度講，人工智能是指用人工的方法在機器〔計算機〕上實現(xiàn)智能；從學(xué)科的角度看，人工智能是一門研究若何構(gòu)造智能機器或智能系統(tǒng)，使它能模擬、延伸和擴展人類智能的學(xué)科。研究目標(biāo)：對智能行為有效解釋的理論分析；解釋人類智能；構(gòu)造具有智能的人工產(chǎn)品；1.4什么是圖靈實驗圖靈實驗說明了什么解：圖靈實驗可描述如下，該實驗的參加者由一位測試主持人和兩個被測試對象組成。其中，兩個被測試對象中一個是人，另一個是機器。測試規(guī)則為：測試主持人和每個被測試對象分別位于彼此不能看見的房間中，相互之間只能通過計算機終端進展會話。測試開場后，由測試主持人向被測試對象提出各種具有智能性的問題，但不能詢問測試者的物理特征。被測試對象在答復(fù)以下問題時,都應(yīng)盡量使測試者相信自己是“人〞，而另一位是〞機器〞。在這個前提下，要求測試主持人區(qū)分這兩個被測試對象中哪個是人，哪個是機器。如果無論若何更換測試主持人和被測試對象的人，測試主持人總能分辨出人和機器的概率都小于50%，則認(rèn)為該機器具有了智能。1.5人工智能的開展經(jīng)歷了哪幾個階段解：孕育期，形成期，知識應(yīng)用期，從學(xué)派分立走向綜合，智能科學(xué)技術(shù)學(xué)科的興起1.6人工智能研究的基本內(nèi)容有哪些解：與腦科學(xué)與認(rèn)知科學(xué)的穿插研究智能模擬的方法和技術(shù)研究1.7人工智能有哪幾個主要學(xué)派各自的特點是什么解：符號主義：又稱為邏輯主義、心理學(xué)派或計算機學(xué)派，是基于物理符號系統(tǒng)假設(shè)和有限合理性原理的人工智能學(xué)派。符號主義認(rèn)為人工智能起源于數(shù)理邏輯，人類認(rèn)知〔智能〕的基本元素是符號，認(rèn)知過程是符號表示上的一種運算。聯(lián)結(jié)主義：又稱為仿生學(xué)派或生理學(xué)派，是基于神經(jīng)網(wǎng)絡(luò)及網(wǎng)絡(luò)間的聯(lián)結(jié)機制與學(xué)習(xí)算法的人工智能學(xué)派。聯(lián)結(jié)主義認(rèn)為人工智能起源于仿生學(xué)，特別是人腦模型的研究。行為主義：又稱進化主義或控制論學(xué)派，是基于控制論和“感知-動作〞控制系統(tǒng)的人工智能學(xué)派。行為主義認(rèn)為人工智能起源于控制論，提出智能取決于感知和行為，取決于對外界復(fù)雜環(huán)境的適應(yīng)，而不是表示和推理。1.8人工智能有哪些主要研究和應(yīng)用領(lǐng)域其中哪些是新的研究熱點解：機器思維:推理、搜索、規(guī)劃機器學(xué)習(xí)：符號學(xué)習(xí)、聯(lián)結(jié)學(xué)習(xí)、知識發(fā)現(xiàn)和數(shù)據(jù)挖掘機器感知：機器視覺、模式識別、自然語言理解機器行為：智能控制、智能制造計算智能：神經(jīng)計算、進化計算、模糊計算分布智能智能系統(tǒng)：專家系統(tǒng)、智能決策支持系統(tǒng)人工心理與人工情感研究熱點：智能機器人、智能檢索、智能游戲等。1.9人工智能未來開展有哪些值得思考和關(guān)注的重要問題解：多學(xué)科穿插研究分布智能與社會智能研究集成智能研究智能網(wǎng)絡(luò)研究認(rèn)知計算與情感計算研究智能系統(tǒng)與智能服務(wù)確定性知識系統(tǒng)參考答案2.1什么是知識有哪幾種主要的知識分類方法解：知識是人們在改造客觀世界的實踐中積累起來的認(rèn)識和經(jīng)歷；知識是對信息進展智能性加工中形成的對客觀世界規(guī)律性的認(rèn)識。分類：按適用范圍：常識性知識、領(lǐng)域性知識按作用效果：陳述性知識、過程性知識、控制性知識按確定性：確定性知識、不確定性知識2.2什么是知識表示知識表示有哪些要求解：知識表示就是對知識的描述，即用一些約定的符號把知識編碼成一組可以被計算機直接識別，并便于系統(tǒng)使用的數(shù)據(jù)構(gòu)造一介謂詞邏輯表示法非構(gòu)造化方法產(chǎn)生式陳述性知識表示語義網(wǎng)絡(luò)構(gòu)造化方法框架構(gòu)造知識表示方法過程性知識表示要求：表示能力，可利用性，可組織性與可維護性，可理解性和可實現(xiàn)性2.3從心理學(xué)的角度看，推理有哪兩種對比典型的觀點它們的含義是什么解：構(gòu)造觀點：這種觀點從構(gòu)造的角度出發(fā)，認(rèn)為推理由兩個以上判斷所組成，每個判斷所提醒的是概念之間的聯(lián)系和關(guān)系，推理過程是一種對客觀事物做出肯定或否點的思維活動。過程觀點：這種觀點從過程的角度出發(fā)，認(rèn)為推理是在給定信息和已有知識的根基上所進展的一系列加工操作，其代表人物克茨提出了如下人類推理的公式：y=F〔x，k〕式中，x是推理時給出的信息，k是推理時可用的領(lǐng)域知識和特殊事例，F(xiàn)是可用的一系列操作，y是推理過程所得到的結(jié)論。2.4什么是推理它有哪些分類方法解：推理是由具體事例歸納出一般規(guī)律，或者根據(jù)已有的知識推出新的結(jié)論的思維過程分為演繹法和歸納法2.5推理中的控制策略包括哪幾個方面的內(nèi)容主要解決哪些問題解：包括推理策略和搜索策略推理策略主要解決推理方向，求解策略，限制策略，沖突消解策略等搜索策略主要解決推理線路，推理效果，推理效率等問題2.6什么是命題什么是命題的真值解：一個陳述句稱為一個斷言，凡有真假意義的斷言稱為命題。命題的意義通常稱為真值，當(dāng)命題的意義為真時，則稱該命題的真值為真。2.7什么是論域什么是謂詞解：論域是由所討論對象之全體構(gòu)成的非空集合。論域中的元素稱為個體，論域也常稱為個體域。在謂詞邏輯中，命題是用謂詞來表示的。一個謂詞可分為謂詞名和個體兩局部。2.8什么是自由變元什么是約束變元解：當(dāng)一個謂詞公式含有量詞時，區(qū)分個體變元是否受量詞的約束是很重要的。通常，把位于量詞后面的單個謂詞或者用括弧括起來的合式公式稱為該量詞的轄域，轄域內(nèi)與量詞中受約束的變元稱為約束變元，不受約束的變元稱為自由變元。2.9設(shè)有如下語句，請用相應(yīng)的謂詞公式分別把他們表示出來：(1)有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。解：定義謂詞P(x)：x是人L(x,y)：x喜歡y其中，y的個體域是{梅花，菊花}。將知識用謂詞表示為：(x)(P(x)→L(x,梅花)∨L(x,菊花)∨(L(x,梅花)∧L(x,菊花)))(2)有人每天下午都去打籃球。解：定義謂詞P(x)：x是人B(x)：x打籃球A(y)：y是下午將知識用謂詞表示為：(x)(y)(A(y)→B(x)∧P(x))(3)新型計算機速度又快，存儲容量又大。解：定義謂詞NC(x)：x是新型計算機F(x)：x速度快B(x)：x容量大將知識用謂詞表示為：(x)(NC(x)→F(x)∧B(x))(4)不是每個計算機系的學(xué)生都喜歡在計算機上編程序。解：定義謂詞S(x)：x是計算機系學(xué)生L(x,pragramming)：x喜歡編程序U(x,computer)：x使用計算機將知識用謂詞表示為：?(x)(S(x)→L(x,pragramming)∧U(x,computer))(5)但凡喜歡編程序的人都喜歡計算機。解：定義謂詞P(x)：x是人L(x,y)：x喜歡y將知識用謂詞表示為：(x)(P(x)∧L(x,pragramming)→L(x,computer))2.10用謂詞表示法求解機器人摞積木問題。設(shè)機器人有一只機械手，要處理的世界有一張桌子，桌上可堆放假設(shè)干一樣的方積木塊。機械手有4個操作積木的典型動作：從桌上揀起一塊積木；將手中的積木放到桌之上；在積木上再摞上一塊積木；從積木上面揀起一塊積木。積木世界的布局如以以以下圖所示。AABCCACABB圖2.10機器人摞積木問題解：(1)先定義描述狀態(tài)的謂詞CLEAR(x)：積木x上面是空的。ON(x,y)：積木x在積木y的上面。ONTABLE(x)：積木x在桌子上。HOLDING(x)：機械手抓住x。HANDEMPTY：機械手是空的。其中，x和y的個體域都是{A,B,C}。問題的初始狀態(tài)是：ONTABLE(A)ONTABLE(B)ON(C,A)CLEAR(B)CLEAR(C)HANDEMPTY問題的目標(biāo)狀態(tài)是：ONTABLE(C)ON(B,C)ON(A,B)CLEAR(A)HANDEMPTY(2)再定義描述操作的謂詞在本問題中，機械手的操作需要定義以下4個謂詞：Pickup(x)：從桌面上揀起一塊積木x。Putdown(x)：將手中的積木放到桌面上。Stack(x,y)：在積木x上面再摞上一塊積木y。Upstack(x,y)：從積木x上面揀起一塊積木y。其中，每一個操作都可分為條件和動作兩局部，具體描述如下：Pickup(x)條件：ONTABLE(x)，HANDEMPTY，CLEAR(x)動作：刪除表：ONTABLE(x)，HANDEMPTY添加表：HOLDING〔x〕Putdown(x)條件：HOLDING〔x〕動作：刪除表：HOLDING〔x〕添加表：ONTABLE(x)，CLEAR(x)，HANDEMPTYStack(x,y)條件：HOLDING〔x〕，CLEAR(y)動作：刪除表：HOLDING〔x〕，CLEAR(y)添加表：HANDEMPTY，ON(x,y)，CLEAR(x)Upstack(x,y)條件：HANDEMPTY，CLEAR(x)，ON(x,y)動作：刪除表：HANDEMPTY，ON(x,y)添加表：HOLDING(x)，CLEAR(x)(3)問題求解過程利用上述謂詞和操作，其求解過程為：ONTABLE(A)ONTABLE(B)ONTABLE(ONTABLE(A)ONTABLE(B)ONTABLE(C)CLEAR(A)CLEAR(B)CLEAR(C)HANDEMPTYONTABLE(A)ONTABLE(B)ON(C,A)CLEAR(B)CLEAR(C)HANDEMPTYONTABLE(A)ONTABLE(B)HOLDING(C)CLEAR(A)CLEAR(B)Upstack(CUpstack(C,A)Putdown(C)Pickup(Pickup(B)ONTABLE(A)ONTABLE(ONTABLE(A)ONTABLE(C)ON(B,C)CLEAR(A)CLEAR(B)HANDEMPTYONTABLE(A)ONTABLE(C)HOLDING(B)CLEAR(A)CLEAR(B)CLEAR(C)ONTABLE(CONTABLE(C)ON(B,C)ON(A,B)CLEAR(A)HANDEMPTONTABLE(C)ON(B,C)CLEAR(A)CLEAR(B)HOLDING(A)Stack(A,Stack(A,B)Stack(B,C)Pickup(A)2.11用謂詞表示法求解農(nóng)夫、狼、山羊、白菜問題。農(nóng)夫、狼、山羊、白菜全部放在一條河的左岸，現(xiàn)在要把他們?nèi)克偷胶拥挠野度?，農(nóng)夫有一條船，過河時，除農(nóng)夫外船上至多能載狼、山羊、白菜中的一種。狼要吃山羊，山羊要吃白菜，除非農(nóng)夫在那里。似規(guī)劃出一個確保全部安全過河的方案。請寫出所用謂詞的定義，并給出每個謂詞的功能及變量的個體域。解：(1)先定義描述狀態(tài)的謂詞要描述這個問題，需要能夠說明農(nóng)夫、狼、羊、白菜和船在什么位置，為簡化問題表示，取消船在河中行駛的狀態(tài)，只描述左岸和右岸的狀態(tài)。并且，由于左岸和右岸的狀態(tài)互補，因此可僅對左岸或右岸的狀態(tài)做直接描述。此題選擇對左岸進展直接描述的方法，即定義謂詞如下：AL(x)：x在左岸其中，x的個體域是{農(nóng)夫，船，狼，羊，白菜}。對應(yīng)地，?AL(x)表示x在右岸。問題的初始狀態(tài)：AL(農(nóng)夫)AL(船)AL(狼)AL(羊)AL(白菜)問題的目標(biāo)狀態(tài)：?AL(農(nóng)夫)?AL(船)?AL(狼)?AL(羊)?AL(白菜)(2)再定義描述操作的謂詞此題需要以下4個描述操作的謂詞：L-R：農(nóng)夫自己劃船從左岸到右岸L-R(x)：農(nóng)夫帶著x劃船從左岸到右岸R-L：農(nóng)夫自己劃船從右岸到左岸R-L(x)：農(nóng)夫帶著x劃船從右岸到左岸其中，x的個體域是{狼，羊，白菜}。對上述每個操作，都包括條件和動作兩局部。它們對應(yīng)的條件和動作如下：L-R：農(nóng)夫劃船從左岸到右岸條件：AL(船)，AL(農(nóng)夫)，?AL(狼)∨?AL(羊)，?AL(羊)∨?AL(白菜)動作：刪除表：AL(船)，AL(農(nóng)夫)添加表：?AL(船)，?AL(農(nóng)夫)L-R(狼)：農(nóng)夫帶著狼劃船從左岸到右岸條件：AL(船)，AL(農(nóng)夫)，AL(狼)，?AL(羊)動作：刪除表：AL(船)，AL(農(nóng)夫)，AL(狼)添加表：?AL(船)，?AL(農(nóng)夫)，?AL(狼)L-R(羊)：農(nóng)夫帶著羊劃船從左岸到右岸條件：AL(船)，AL(農(nóng)夫)，AL(羊)，AL(狼)，AL(白菜)或：AL(船)，AL(農(nóng)夫)，AL(羊)，?AL(狼)，?AL(白菜)動作：刪除表：AL(船)，AL(農(nóng)夫)，AL(羊)添加表：?AL(船)，?AL(農(nóng)夫)，?AL(羊)L-R(白菜)：農(nóng)夫帶著白菜劃船從左岸到右岸條件：AL(船)，AL(農(nóng)夫)，AL(白菜)，?AL(狼)動作：刪除表：AL(船)，AL(農(nóng)夫)，AL(白菜)添加表：?AL(船)，?AL(農(nóng)夫)，?AL(白菜)R-L：農(nóng)夫劃船從右岸到左岸條件：?AL(船)，?AL(農(nóng)夫)，AL(狼)∨AL(羊)，AL(羊)∨AL(白菜)或：?AL(船)，?AL(農(nóng)夫)，?AL(狼)，?AL(白菜)，AL(羊)動作：刪除表：?AL(船)，?AL(農(nóng)夫)添加表：AL(船)，AL(農(nóng)夫)R-L(羊)：農(nóng)夫帶著羊劃船從右岸到左岸條件：?AL(船)，?AL(農(nóng)夫)，?AL(羊)，?AL(狼)，?AL(羊)，AL(白菜)動作：刪除表：?AL(船)，?AL(農(nóng)夫)，?AL(羊)添加表：AL(船)，AL(農(nóng)夫)，AL(羊)(3)問題求解過程AL(白菜)?AL(農(nóng)夫)?AL(白菜)?AL(農(nóng)夫)?AL(船)?AL(狼)?AL(羊)AL(農(nóng)夫)AL(船)AL(狼)AL(白菜)?AL(羊)AL(狼)AL(白菜)?AL(農(nóng)夫)?AL(船)?AL(羊)R-LR-L(羊)L-R(狼)L-R(羊)AL(船)R-LR-L(羊)L-R(狼)L-R(羊)AL(狼)AL(羊)AL(白菜)AL(農(nóng)夫)AL(船)AL(羊)AL(農(nóng)夫)AL(船)AL(羊)AL(白菜)?AL(狼)AL(農(nóng)夫)AL(船)AL(羊)?AL(白菜)?AL(狼)AL(羊)?AL(農(nóng)夫)?AL(船)?AL(白菜)?AL(狼)L-R(羊)?AL(農(nóng)夫)?L-R(羊)?AL(農(nóng)夫)?AL(船)?AL(羊)?AL(白菜)?AL(狼)R-LL-R(白菜)2.12用謂詞表示法求解修道士和野人問題。在河的北岸有三個修道士、三個野人和一條船，修道士們想用這條船將所有的人都運過河去，但要受到以下條件限制：(1)修道士和野人都會劃船，但船一次只能裝運兩個人。(2)在任何岸邊，野人數(shù)不能超過修道士，否則修道士會被野人吃掉。假定野人愿意服從任何一種過河安排，請規(guī)劃出一種確保修道士安全的過河方案。要求寫出所用謂詞的定義、功能及變量的個體域。解：〔1〕定義謂詞先定義修道士和野人人數(shù)關(guān)系的謂詞：G(x,y,S)：在狀態(tài)S下x大于yGE(x,y,S)：在狀態(tài)S下x大于或等于y其中，x,y分別代表修道士人數(shù)和野人數(shù)，他們的個體域均為{0,1,2,3}。再定義船所在岸的謂詞和修道士不在該岸上的謂詞：Boat(z,S)：狀態(tài)S下船在z岸EZ(x,S)：狀態(tài)S下x等于0，即修道士不在該岸上其中，z的個體域是{L,R}，L表示左岸，R表示右岸。再定義安全性謂詞：Safety(z,x,y,S)≡(G(x,0,S)∧GE(x,y,S))∨(EZ(x,S))其中，z,x,y的含義同上。該謂詞的含義是：狀態(tài)S下，在z岸，保證修道士安全，當(dāng)且僅當(dāng)修道士不在該岸上，或者修道士在該岸上，但人數(shù)超過野人數(shù)。該謂詞同時也描述了相應(yīng)的狀態(tài)。再定義描述過河方案的謂詞：L-R(x,x1,y,y1,S)：x1個修道士和y1個野人渡船從河的左岸到河的右岸條件：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(L,S)動作：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(R,S’)R-L(x,x1,y,y1,S)：x2個修道士和y2個野人渡船從河的左岸到河的右岸條件：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(R,S)動作：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(L,S’)(2)過河方案Safety(L,3,3,S0)∧Safety(R,0,0,S0)∧Boat(L,S0)L-R(3,1,3,1,S0)L-R(3,0,3,2,S0)Safety(L,2,2,S1)∧Safety(R,1,1,S1)∧Boat(R,S1)Safety(L,3,1,S1’)∧Safety(R,0,2,S1’)∧Boat(R,S1’)R-L(2,1,2,0,S1)R-L(3,0,1,1,S1’)Safety(L,3,2,S2)∧Safety(R,0,1,S2)∧Boat(L,S2)L-R(3,0,2,2,S2)Safety(L,3,0,S3)∧Safety(R,0,3,S3)∧Boat(R,S3)R-L(3,0,0,1,S3)Safety(L,3,1,S4)∧Safety(R,0,2,S1)∧Boat(L,S4)L-R(3,2,1,0,S4)Safety(L,1,1,S5)∧Safety(R,2,2,S5)∧Boat(R,S5)R-L(1,1,1,1,S5)Safety(L,2,2,S6)∧Safety(R,1,1,S6)∧Boat(L,S6)L-R(2,2,2,0,S6)Safety(L,0,2,S7)∧Safety(R,3,1,S7)∧Boat(R,S7)R-L(0,0,2,1,S7)Safety(L,0,3,S8)∧Safety(R,3,0,S8)∧Boat(L,S8)L-R(0,0,3,2,S8)Safety(L,0,1,S9)∧Safety(R,3,2,S9)∧Boat(R,S9)R-L(0,1,1,0,S9)Safety(L,1,1,S10)∧Safety(R,2,2,S10)∧Boat(L,S10)L-R(1,1,1,1,S10)Safety(L,0,0,S11)∧Safety(R,3,3,S11)∧Boat(R,S11)2.13什么是產(chǎn)生式它的基本形式是什么代表什么含義解：“產(chǎn)生式〞由美國數(shù)學(xué)家波斯特〔E.POST〕在1934年首先提出，它根據(jù)串代替規(guī)則提出了一種稱為波斯特機的計算模型，模型中的每條規(guī)則稱為產(chǎn)生式。產(chǎn)生式的基本形式P→Q或者IFPTHENQ。P是產(chǎn)生式的前提，也稱為前件，它給出了該產(chǎn)生式可否使用的先決條件，由事實的邏輯組合來構(gòu)成；Q是一組結(jié)論或操作，也稱為產(chǎn)生式的后件，它指出當(dāng)前題P滿足時，應(yīng)該推出的結(jié)論或應(yīng)該執(zhí)行的動作。產(chǎn)生式的含義如果前提P滿足，則可推出結(jié)論Q或執(zhí)行Q所規(guī)定的操作。2.14產(chǎn)生式表示的特征是什么解：優(yōu)點：自然性、模塊性、有效性缺點：效率低性、不方便表示構(gòu)造性知識的有向圖2.15何謂語義網(wǎng)絡(luò)它有哪些基本的語義關(guān)系解：語義網(wǎng)絡(luò)：用實體以及語義關(guān)系來表達知識的有向圖基本的語義關(guān)系：①實例關(guān)系〔ISA〕:(是一個)(一個事物是另一個事物的具體例子)②分類關(guān)系〔AKO〕:(是一種)子類與超類③成員關(guān)系(A-member-of):是一名④屬性關(guān)系:Have有、Can能、Age年齡⑤包含關(guān)系part-of-局部(不具備屬性)⑥位置關(guān)系:Before，after⑦located-onlocated-underlocated-outsidelocated-atlocated-inside⑧相近關(guān)系similar-to相似near-to接近2.16請對以下命題分別寫出它們的語義網(wǎng)絡(luò)：(1)每個學(xué)生都有一臺計算機。AKOAKOAKOAKO人職業(yè)學(xué)生人職業(yè)學(xué)生AKOAKO設(shè)備計算機設(shè)備計算機ownerownerowns占有權(quán)owns占有權(quán)AKOAKO情況占有資格情況占有資格AKOAKO(2)高教師從3月到7月給計算機系學(xué)生講《計算機網(wǎng)絡(luò)》課。解：7月8月7月8月StartEndStartEnd教師ISAObjectSubject高教師計算機系學(xué)生講課事件教師ISAObjectSubject高教師計算機系學(xué)生講課事件ActionCaurseActionCaurse計算機網(wǎng)絡(luò)講課計算機網(wǎng)絡(luò)講課(3)學(xué)習(xí)班的學(xué)員有男、有女、有研究生、有本科生。解：女男研究生本科生女男研究生本科生HaveHaveHaveHaveHaveHave學(xué)員學(xué)員(4)創(chuàng)新公司在科海大街56號，劉洋是該公司的經(jīng)理，他32歲、碩士學(xué)位。3232AgeWork-forAddressAgeWork-forAddressIsa創(chuàng)新公司劉洋經(jīng)理56號Isa創(chuàng)新公司劉洋經(jīng)理56號HaveHave碩士學(xué)位碩士學(xué)位(5)紅隊與藍隊進展足球比賽，最后以3：2的比分完畢。解：比賽比賽AKOAKOParticipants1Outcome3:22Participants1Outcome3:22足球賽紅隊紅隊Participants2Participants2藍隊藍隊2.17請把以下命題用一個語義網(wǎng)絡(luò)表示出來：(1)樹和草都是植物；植物解：植物AKOAKOAKOAKO草樹草樹(2)樹和草都有葉和根；根葉解：根葉HaveHaveHaveHave植物植物是一種是一種是一種是一種草樹草樹(3)水草是草，且生長在水中；解：LiveAKOAKO水草LiveAKOAKO水草水中植物草水中植物草(4)果樹是樹，且會結(jié)果；解：CanAKOAKO果樹CanAKOAKO果樹結(jié)果植物樹結(jié)果植物樹(5)梨樹是果樹中的一種，它會結(jié)梨。解：CanAKOAKO梨樹CanAKOAKO梨樹樹果樹結(jié)梨樹果樹結(jié)梨2.18試述語義網(wǎng)絡(luò)中求解問題的一般過程解：語義網(wǎng)絡(luò)的推理過程主要有兩種，一種是繼承，另一種是匹配。繼承是指把對事物的描述從抽象節(jié)點傳遞到具體節(jié)點。匹配是指在知識庫的語義網(wǎng)絡(luò)中尋找與待求解問題相符的語義網(wǎng)絡(luò)模式。2.19試述語義網(wǎng)絡(luò)表示法的特點解：構(gòu)造性聯(lián)想性自然性缺點：非嚴(yán)格性，復(fù)雜性2.20何謂框架框架的一般形式是什么解：框架表示法是在框架理論的根基上開展起來的一種構(gòu)造化知識表示方法?？蚣芡ǔＳ擅枋鍪挛锔鱾€方面的假設(shè)干槽組成，每一個槽也可以根據(jù)實際情況擁有假設(shè)干個側(cè)面，每一個側(cè)面又可以擁有假設(shè)干個值。2.21何謂實例框架它與框架有什么關(guān)系解：當(dāng)人們把觀察或認(rèn)識到的具體細節(jié)填入框架后，就得到了該框架的一個具體實例，框架的這種具體實例被稱為實例框架。通用構(gòu)造與具體實例，抽象與具體。2.22何謂框架系統(tǒng)何謂框架系統(tǒng)的橫向聯(lián)系何謂框架系統(tǒng)的縱向聯(lián)系解：在框架理論中，框架是知識的基本單位，把一組有關(guān)的框架連接起來便可形成一個框架系統(tǒng)。在框架系統(tǒng)中，系統(tǒng)的行為由該系統(tǒng)內(nèi)框架的變化來實現(xiàn)，系統(tǒng)的推理過程由框架之間的協(xié)調(diào)完成。縱向聯(lián)系：表示那種具有演繹關(guān)系的知識構(gòu)造，下層框架與上層框架之間具有一種繼承關(guān)系，這種具有繼承關(guān)系的框架之間的聯(lián)系稱為縱向聯(lián)系。橫向聯(lián)系：由于一個框架的槽值或側(cè)面值可以是另外一個框架的名字，這就在框架之間建設(shè)了另外一種聯(lián)系，稱為橫向聯(lián)系。2.23假設(shè)有以下一段天氣預(yù)報：“北京地區(qū)今天白天晴，偏北風(fēng)3級，最高氣溫12o，最低氣溫-2o，降水概率15%。〞請用框架表示這一知識。解：Frame<天氣預(yù)報>地域：北京時段：今天白天天氣：晴風(fēng)向：偏北風(fēng)力：3級氣溫：最高：12度最低：-2度降水概率：15%2.24按“師生框架〞、“教師框架〞、“學(xué)生框架〞的形式寫出一個框架系統(tǒng)的描述。解：師生框架Frame<Teachers-Students>Name：Unit〔Last-name，F(xiàn)irst-name〕Sex：Area〔male，female〕Default：maleAge：Unit〔Years〕Telephone：HomeUnit〔Number〕MobileUnit〔Number〕教師框架Frame<Teachers>AKO<Teachers-Students>Major：Unit〔Major-Name〕Lectures：Unit〔Course-Name〕Field：Unit〔Field-Name〕Project：Area〔National，Provincial，Other〕Default：ProvincialPaper：Area〔SCI，EI，Core，General〕Default：Core學(xué)生框架Frame<Students>AKO<Teachers-Students>Major：Unit〔Major-Name〕Classes：Unit〔Classes-Name〕Degree：Area〔doctor，mastor,bachelor〕Default：bachelor2.25在框架系統(tǒng)中，問題求解的一般過程是什么解：特性繼承框架的匹配與填槽2.26框架表示法的特點有哪些解：優(yōu)點：構(gòu)造性，深層性，繼承性，自然性。缺點：缺乏框架的形式理論，缺乏過程性知識表示，清晰性難以保證2.27何謂產(chǎn)生式系統(tǒng)產(chǎn)生式推理的基本構(gòu)造由哪幾局部組成解：利用產(chǎn)生式知識表示方法所進展的推理稱為產(chǎn)生式推理，由此產(chǎn)生的系統(tǒng)為產(chǎn)生式系統(tǒng)基本構(gòu)造：綜合數(shù)據(jù)庫，規(guī)則庫，控制系統(tǒng)2.28什么是產(chǎn)生式的正向推理其基本過程是什么解：從事實出發(fā)，正向使用推理規(guī)則的推理方法。過程：〔1〕把用戶提供的初始證據(jù)放入綜合數(shù)據(jù)庫；〔2〕檢查綜合數(shù)據(jù)庫中是否包含了問題的解，假設(shè)已包含，則求解完畢，并成功推出，否則，執(zhí)行下一步；〔3〕檢查知識庫中是否有可用知識。假設(shè)有，形成當(dāng)前可用知識集，執(zhí)行下一步，否則轉(zhuǎn)〔5〕；〔4〕按照某種沖突消解策略，從當(dāng)前可用知識集中選出一條知識進展推理，并將推出的新事實參加綜合數(shù)據(jù)庫中，然后轉(zhuǎn)〔2〕；〔5〕詢問用戶是否可以進一步補充新的事實，假設(shè)可補充，則將補充的新事實參加綜合數(shù)據(jù)庫中，然后轉(zhuǎn)〔3〕，否則表示無解，失敗退出。2.29什么是逆向推理其基本過程是什么解：以某個假設(shè)目標(biāo)作為出發(fā)點的推理方法過程：將問題的初始證據(jù)和要求證的目標(biāo)〔稱為假設(shè)〕分別放入綜合數(shù)據(jù)庫和假設(shè)集；從假設(shè)集中選出一個假設(shè)，檢查該假設(shè)是否在綜合數(shù)據(jù)庫中，假設(shè)在，則該假設(shè)成立。此時，假設(shè)假設(shè)集為空，則成功退出。否則，扔執(zhí)行〔2〕。假設(shè)該假設(shè)不在數(shù)據(jù)庫中，則執(zhí)行下一步；檢查該假設(shè)是否可由知識庫的某個知識導(dǎo)出，假設(shè)不能由某個知識導(dǎo)出，則詢問用戶尋找新的假設(shè)。假設(shè)不是，則轉(zhuǎn)〔5〕，假設(shè)能由某個知識導(dǎo)出，則執(zhí)行下一步；將知識庫中可以導(dǎo)出該假設(shè)的所有知識構(gòu)成一個可用知識集；檢查可用知識集是否為空，假設(shè)空，失敗退出。否則執(zhí)行下一步；按沖突消解策略從可用知識集中取出一個知識，繼續(xù)執(zhí)行下一步；將該知識的前提中的每個子條件都作為新的假設(shè)放入假設(shè)集，轉(zhuǎn)〔2〕。2.30什么是混合推理它由哪幾種實現(xiàn)方式解：正向推理和逆向推理結(jié)合起來所進展的推理稱為混合推理實現(xiàn)：先正后逆，先逆后正，隨機2.31什么是置換什么是合一解：在不同謂詞公式中，往往會出現(xiàn)多個謂詞的謂詞名一樣但個體不同的情況，此時推理過程是不能直接進展匹配的，需要先進展變元的替換。這種利用項對變元進展替換叫置換。合一利用置換使兩個或多個謂詞的個體一致。2.32判斷以下公式是否為可合一，假設(shè)可合一，則求出其相應(yīng)的置換解：(1)

可合一，其最一般和一為：σ={a/x,

b/y}。

(2)

可合一，其最一般和一為：σ={f(x)/y,

b/z}。

(3)

可合一，其最一般和一為：σ={f(b)/y,

b/x}。

(4)

不可合一。

(5)

可合一，其最一般和一為：σ={

y/x}。2.33什么是自然演繹推理它所依據(jù)的推理規(guī)則是什么從一組為真的事實出發(fā)，直接運用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過程稱為自然演繹推理推理規(guī)則：等價式，永真蘊涵式，置換，合一2.34什么是謂詞公式的可滿足性什么是謂詞公式的不可滿足性教材P55.56頁2.35什么是謂詞公式的前束范式什么是謂詞公式的Skolem范式教材P562.36什么是字句集若何將謂詞公式化為字句集教材P56.572.37把以下謂詞公式化成子句集：(x)(y)(P(x,y)∧Q(x,y))(x)(y)(P(x,y)→Q(x,y))(x)(y)(P(x,y)∨(Q(x,y)→R(x,y)))(x)(y)(z)(P(x,y)→Q(x,y)∨R(x,z))解：(1)由于(x)(y)(P(x,y)∧Q(x,y))已經(jīng)是Skolem標(biāo)準(zhǔn)型，且P(x,y)∧Q(x,y)已經(jīng)是合取范式，所以可直接消去全稱量詞、合取詞，得{P(x,y),Q(x,y)}再進展變元換名得子句集：S={P(x,y),Q(u,v)}(2)對謂詞公式(x)(y)(P(x,y)→Q(x,y))，先消去連接詞“→〞得：(x)(y)(?P(x,y)∨Q(x,y))此公式已為Skolem標(biāo)準(zhǔn)型。再消去全稱量詞得子句集：S={?P(x,y)∨Q(x,y)}(3)對謂詞公式(x)(y)(P(x,y)∨(Q(x,y)→R(x,y)))，先消去連接詞“→〞得：(x)(y)(P(x,y)∨(?Q(x,y)∨R(x,y)))此公式已為前束范式。再消去存在量詞，即用Skolem函數(shù)f(x)替換y得：(x)(P(x,f(x))∨?Q(x,f(x))∨R(x,f(x)))此公式已為Skolem標(biāo)準(zhǔn)型。最后消去全稱量詞得子句集：S={P(x,f(x))∨?Q(x,f(x))∨R(x,f(x))}(4)對謂詞(x)(y)(z)(P(x,y)→Q(x,y)∨R(x,z))，先消去連接詞“→〞得：(x)(y)(z)(?P(x,y)∨Q(x,y)∨R(x,z))再消去存在量詞，即用Skolem函數(shù)f(x)替換y得：(x)(y)(?P(x,y)∨Q(x,y)∨R(x,f(x,y)))此公式已為Skolem標(biāo)準(zhǔn)型。最后消去全稱量詞得子句集：S={?P(x,y)∨Q(x,y)∨R(x,f(x,y))}2.38魯濱遜歸結(jié)原理的基本思想是什么解：魯濱遜歸結(jié)原理也稱為消解原理。其基本思想是把永真性的證明轉(zhuǎn)化為不可滿足性的證明。即要證明P->Q永真，只要能夠證明P∧?Q為不可滿足即可。2.39判斷以下子句集中哪些是不可滿足的：{?P∨Q,?Q,P,?P}{P∨Q,?P∨Q,P∨?Q,?P∨?Q}{P(y)∨Q(y),?P(f(x))∨R(a)}{?P(x)∨Q(x),?P(y)∨R(y),P(a),S(a),?S(z)∨?R(z)}{?P(x)∨Q(f(x),a),?P(h(y))∨Q(f(h(y)),a)∨?P(z)}{P(x)∨Q(x)∨R(x),?P(y)∨R(y),?Q(a),?R(b)}解：(1)不可滿足，其歸結(jié)過程為：??P∨Q?Q?PPNIL(2)不可滿足，其歸結(jié)過程為：PP∨Q?P∨QQP∨?Q?P∨?Q?QNIL(3)不是不可滿足的，原因是不能由它導(dǎo)出空子句。(4)不可滿足，其歸結(jié)過程略(5)不是不可滿足的，原因是不能由它導(dǎo)出空子句。(6)不可滿足，其歸結(jié)過程略2.40對以下各題分別證明G是否為F1,F2,…,Fn的邏輯結(jié)論：F:(x)(y)(P(x,y)G:(y)(x)(P(x,y)F:(x)(P(x)∧(Q(a)∨Q(b)))G:(x)(P(x)∧Q(x))F:(x)(y)(P(f(x))∧(Q(f(y)))G:P(f(a))∧P(y)∧Q(y)F1:(x)(P(x)→(y)(Q(y)→L(x.y)))F2:(x)(P(x)∧(y)(R(y)→L(x.y)))G:(x)(R(x)→Q(x))F1:(x)(P(x)→(Q(x)∧R(x)))F2:(x)(P(x)∧S(x))G:(x)(S(x)∧R(x))解：(1)先將F和?G化成子句集：S={P(a,b),?P(x,b)}再對S進展歸結(jié)：?P?P(x,b)P(a,b)NIL{a/x}NIL所以，G是F的邏輯結(jié)論(2)先將F和?G化成子句集由F得：S1={P(x)，(Q(a)∨Q(b))}由于?G為：?(x)(P(x)∧Q(x))，即(x)(?P(x)∨?Q(x))，可得：S2={?P(x)∨?Q(x)}因此，擴大的子句集為：S={P(x)，(Q(a)∨Q(b))，?P(x)∨?Q(x)}再對S進展歸結(jié)：Q(a)∨Q(a)∨Q(b)Q(a)?P(x)∨?Q(x)?P(a)P(x)NILQ(a)∨Q(b){a/b}?P(x)?P(x)∨?Q(x)Q(a){a/x}?P(?P(a)P(x){a/x}NILNIL所以，G是F的邏輯結(jié)論同理可求得(3)、(4)和(5)，其求解過程略。2.41設(shè)：如果x是y的父親，y是z的父親，則x是z的祖父；每個人都有一個父親。使用歸結(jié)演繹推理證明：對于某人u，一定存在一個人v，v是u的祖父。解：先定義謂詞F(x,y)：x是y的父親GF(x,z)：x是z的祖父P(x)：x是一個人再用謂詞把問題描述出來：F1：(x)(y)(z)(F(x,y)∧F(y,z))→GF(x,z))F2：(y)(P(x)→F(x,y))求證結(jié)論G：(u)(v)(P(u)→GF(v,u))然后再將F1，F(xiàn)2和?G化成子句集：①?F(x,y)∨?F(y,z)∨GF(x,z)②?P(r)∨F(s,r)③P(u)④?GF(v,u))對上述擴大的子句集，其歸結(jié)推理過程如下：??F(x,y)∨?F(y,z)∨GF(x,z)?GF(v,u)?F(x,y)∨?F(y,z)?P(r)∨F(s,r)?F(y,z)∨?P(y)?P(r)∨F(s,r)?P(y)∨?P(z)?P(y)P(u)NIL{x/v,z/u}{x/s,y/r}{y/s,z/r}{y/z}{y/u}由于導(dǎo)出了空子句，故結(jié)論得證。2.42假設(shè)張被盜，公安局派出5個人去調(diào)查。案情分析時，貞察員A說：“趙與人民幣中至少有一個人作案〞，貞察員B說：“人民幣與孫中至少有一個人作案〞，貞察員C說：“孫與李中至少有一個人作案〞，貞察員D說：“趙與孫中至少有一個人與此案無關(guān)〞，貞察員E說：“人民幣與李中至少有一個人與此案無關(guān)〞。如果這5個偵察員的話都是可信的，使用歸結(jié)演繹推理求出誰是盜竊犯。解：(1)先定義謂詞和常量設(shè)C(x)表示x作案，Z表示趙，Q表示人民幣，S表示孫，L表示李(2)將事實用謂詞公式表示出來趙與人民幣中至少有一個人作案：C(Z)∨C(Q)人民幣與孫中至少有一個人作案：C(Q)∨C(S)孫與李中至少有一個人作案：C(S)∨C(L)趙與孫中至少有一個人與此案無關(guān)：?(C(Z)∧C(S))，即?C(Z)∨?C(S)人民幣與李中至少有一個人與此案無關(guān)：?(C(Q)∧C(L))，即?C(Q)∨?C(L)(3)將所要求的問題用謂詞公式表示出來，并與其否認(rèn)取析取。設(shè)作案者為u，則要求的結(jié)論是C(u)。將其與其否)取析取，得：?C(u)∨C(u)對上述擴大的子句集，按歸結(jié)原理進展歸結(jié)，其修改的證明樹如下：C(C(Z)∨C(Q)?C(Z)∨?C(S)C(Q)∨?C(S)C(Q)∨C(S)C(Q)?C(u)∨C(u)C(Q){Q/u}因此，人民幣是盜竊犯。實際上，本案的盜竊犯不止一人。根據(jù)歸結(jié)原理還可以得出：C(S)∨C(L)C(S)∨C(L)?C(Q)∨?C(L)C(S)∨?C(Q)C(Q)∨C(S)C(S)?C(u)∨C(u)C(S)?C(Q)∨?C(L)C(S)∨C(L)C(Q)∨C(Q)∨C(S)C(S)∨?C(Q)??C(u)∨C(u)C(S)C(S){S/u}C(S)C(S)因此，孫也是盜竊犯。2.43設(shè)：能閱讀的人是識字的；海豚不識字；有些海豚是很聰明的。請用歸結(jié)演繹推理證明：有些很聰明的人并不識字。解：第一步，先定義謂詞，設(shè)R(x)表示x是能閱讀的；K(y)表示y是識字的；W(z)表示z是很聰明的；第二步，將事實和目標(biāo)用謂詞公式表示出來能閱讀的人是識字的：(x)(R(x))→K(x))海豚不識字：(y)(?K(y))有些海豚是很聰明的：(z)W(z)有些很聰明的人并不識字：(x)(W(z)∧?K(x))第三步，將上述事實和目標(biāo)的否認(rèn)化成子句集：?R(x))∨K(x)?K(y)W(z)?W(z)∨K(x))第四步，用歸結(jié)演繹推理進展證明W(z)?W(z)?W(z)∨K(x))W(z)K(z)W(z)K(z)NILNIL確定性推理局部參考答案3.1什么是搜索有哪兩大類不同的搜索方法兩者的區(qū)別是什么解：像這種根據(jù)問題的實際情況，不斷尋找可利用知識，從而構(gòu)造一條最小的推理路線，使問題得以解決的過程稱為搜索可根據(jù)搜索過程是否使用啟發(fā)式信息分為盲目搜索和啟發(fā)式搜索，也可根據(jù)問題的表示方式分為狀態(tài)空間搜索和與/或搜索盲目搜索是按預(yù)定的控制策略進展搜索，在搜索過程中獲得的中間信息并不改變控制策略啟發(fā)式搜索是在搜索中參加了與問題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向前進，加速問題的求解過程，并找到最優(yōu)解。狀態(tài)空間搜索是指用狀態(tài)空間法來表示問題所進展的搜索。與/或搜索是指用問題歸約法來表示問題時所進展的搜索。3.2什么是狀態(tài)空間用狀態(tài)空間表示問題時，什么是問題的解什么是最優(yōu)解最優(yōu)解唯一嗎解：狀態(tài)空間〔statespace〕是由一個問題的全部狀態(tài)，以及這些狀態(tài)之間的相互關(guān)系所構(gòu)成的集合，它可用一個三元祖〔S,F,G〕來表示，其中,S為問題的所有初始狀態(tài)的集合；F為操作的集合；G為目標(biāo)狀態(tài)的集合。由初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是該問題的一個解。使某目標(biāo)函數(shù)到達最優(yōu)值〔最大值或最小值〕的任一可行解，都稱為該問題的一個最優(yōu)解。最優(yōu)解不唯一。3.3什么是與樹什么是或樹什么是與/或樹什么是可解節(jié)點什么是解樹解：把一個原問題分解為假設(shè)干個子問題可用一個“與樹〞來表示。把一個原問題變換為假設(shè)干個子問題可用一個“或樹〞來表示。如果一個問題既需要通過分解，有需要通過變換才能得到其本原問題，則其歸約過程可用一個“與/或樹〞來表示在與/或樹中，滿足以下三個條件之一的節(jié)點為可解節(jié)點：任何終止節(jié)點都是可解節(jié)點對“或〞節(jié)點，當(dāng)其子節(jié)點中至少有一個為可解節(jié)點時，則該或節(jié)點就是可解節(jié)點對“與〞節(jié)點，只有當(dāng)其子節(jié)點全部為可解節(jié)點時，該與節(jié)點才是可解節(jié)點。解樹：由可解節(jié)點構(gòu)成，并且有這些可解節(jié)點可以推出初始節(jié)點為可解節(jié)點的子樹為解樹。3.4在狀態(tài)空間一般搜索過程中，open表與closed表的作用與區(qū)別是什么解：open表中存放待考察節(jié)點，close表存放考察過的節(jié)點。3.5有一農(nóng)夫帶一條狼，一只羊和一筐菜從河的左岸乘船到右岸，但受以下條件限制：〔1〕船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河〔2〕如果沒有農(nóng)夫看管，則狼要吃羊，羊要吃菜請設(shè)計一個過河方案，使得農(nóng)夫、狼羊都能不受損失的過河，畫出相應(yīng)的狀態(tài)空間圖有一農(nóng)夫帶一條狼，一只羊和一框青菜與從河的左岸乘船倒右岸，但受到以下條件的限制：(1)船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河；如果沒有農(nóng)夫看管，則狼要吃羊，羊要吃菜。請設(shè)計一個過河方案，使得農(nóng)夫、浪、羊都能不受損失的過河，畫出相應(yīng)的狀態(tài)空間圖。題示：(1)用四元組〔農(nóng)夫，狼，羊，菜〕表示狀態(tài)，其中每個元素都為0或1，用0表示在左岸，用1表示在右岸。(2)把每次過河的一種安排作為一種操作，每次過河都必須有農(nóng)夫，因為只有他可以劃船。解：第一步，定義問題的描述形式用四元組S=〔f，w，s，v〕表示問題狀態(tài)，其中，f，w，s和v分別表示農(nóng)夫，狼，羊和青菜是否在左岸，它們都可以取1或0，取1表示在左岸，取0表示在右岸。第二步，用所定義的問題狀態(tài)表示方式，把所有可能的問題狀態(tài)表示出來，包括問題的初始狀態(tài)和目標(biāo)狀態(tài)。由于狀態(tài)變量有4個，每個狀態(tài)變量都有2種取值，因此有以下16種可能的狀態(tài)：S0=(0,0,0,0)，S1=(0,0,0,1)，S2=(0,0,1,0)，S3=(0,0,1，1)S4=(0,1,0,0)，S5=(0,1,0,1)，S6=(0,1,1,0)，S7=(0,1,1,1)S8=(1,0,0,0)，S9=(1,0,0,1)，S10=(1,0,1,0)，S11=(1,0,1,1)S12=(1,1,0,0)，S13=(1,1,0,1)，S14=(1,1,1,0)，S15=(1,1,1,1)其中，狀態(tài)S3，S6，S7，S8，S9，S12是不合法狀態(tài)，S0和S15分別是初始狀態(tài)和目標(biāo)狀態(tài)。第三步，定義操作，即用于狀態(tài)變換的算符組F由于每次過河船上都必須有農(nóng)夫，且除農(nóng)夫外船上只能載狼，羊和菜中的一種，故算符定義如下：L(i)表示農(nóng)夫從左岸將第i樣?xùn)|西送到右岸〔i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除農(nóng)夫外不載任何東西〕。由于農(nóng)夫必須在船上，故對農(nóng)夫的表示省略。R(i)表示農(nóng)夫從右岸將第i樣?xùn)|西帶到左岸〔i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除農(nóng)夫外不載任何東西〕。同樣，對農(nóng)夫的表示省略。這樣，所定義的算符組F可以有以下8種算符：L(0)，L(1)，L(2)，L(3)R(0)，R(1)，R(2)，R(3)第四步，根據(jù)上述定義的狀態(tài)和操作進展求解。該問題求解過程的狀態(tài)空間圖如下：(0,0,0,0)(0,0,0,0)L(2)L(2)(1,0,1,0)(1,0,1,0)R(0)R(0)(0,0,1,0)(0,0,1,0)L(3)L(1)L(3)L(1)(1,0,1,1)(1,1,1,0)(1,0,1,1)(1,1,1,0)R(2)R(2)R(2)R(2)(0,0,0,1)(0,1,0,0)(0,0,0,1)(0,1,0,0)L(2)L(2)L(3)L(3)(1,1,0,1)(1,1,0,1)R(0)R(0)(0,1,0,1)(0,1,0,1)L(2)L(2)(1,1,1,1)(1,1,1,1)3.6廣度優(yōu)先搜索與深度優(yōu)先搜索有何區(qū)別解：廣度優(yōu)先搜索先進先出，深度先進后出3.7圓盤問題。設(shè)有大小不等的三個圓盤A、B、C套在一根軸上，每個盤上都標(biāo)有數(shù)字1、2、3、4，并且每個圓盤都可以獨立的繞軸做逆時針轉(zhuǎn)動，每次轉(zhuǎn)動90°，其初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如圖3.7所示，請用廣度優(yōu)先搜索和深度優(yōu)先搜索，求出從S0到Sg的路徑。CC12222222CC12222222BAAB42BAAB42234131231331412341312313314144444343初始狀態(tài)S0目標(biāo)狀態(tài)Sg圖3.7圓盤問題解：設(shè)用qA，qB和qC分別表示把A盤，B盤和C盤繞軸逆時針轉(zhuǎn)動90o，這些操作〔算符〕的排列順序是qA，qB，qC。應(yīng)用廣度優(yōu)先搜索，可得到如下搜索樹。在該搜索樹中，重復(fù)出現(xiàn)的狀態(tài)不再劃出，節(jié)點旁邊的標(biāo)識Si，i=0,1,2,…，為按節(jié)點被擴展的順序給出的該節(jié)點的狀態(tài)標(biāo)識。由該圖可以看出，從初始狀態(tài)S0到目標(biāo)狀態(tài)Sg的路徑是S0→2→5→13(Sg)323221113334444233132314122344323141212434233114242413ABCqAqBqC331311224244qA322441311324qBqC413412332334123331313124422412344123412313324112244qC334213112244qA314241231234qB132314242413qC3.7題的廣度優(yōu)先搜索樹S0S1S2S4S5S6S7S8S9S10S11S12即SgS3其深度優(yōu)先搜索略。3.8圖3.8是5個城市的交通圖，城市之間的連線旁邊的數(shù)字是城市之間路程的費用。要求從A城出發(fā)，經(jīng)過其它各城市一次且僅一次，最后回到A城，請找出一條最優(yōu)線路。A10B289C1163128D9E3.8交通費用圖解：這個問題又稱為旅行商問題〔travellingsalesmanproblem,TSP〕或貨郎擔(dān)問題，是一個較有普遍性的實際應(yīng)用問題。根據(jù)數(shù)學(xué)理論，對n個城市的旅行商問題，其封閉路徑的排列總數(shù)為：(n!)/n=(n-1)!其計算量相當(dāng)大。例如，當(dāng)n=20時，要窮舉其所有路徑，即使用一個每秒一億次的計算機來算也需要350年的時間。因此，對這類問題只能用搜索的方法來解決。以以以下圖是對圖4-32按最小代價搜索所得到的搜索樹，樹中的節(jié)點為城市名稱，節(jié)點邊上的數(shù)字為該節(jié)點的代價g。其計算公式為g(ni+1)=g(ni)+c(ni,ni+1)其中，c(ni,ni+1)為節(jié)點ni到ni+1節(jié)點的邊代價。0A0A119210119210102119BDCE102119BDCE9869312838612898693128386128201917CDB181221ECB10105EDB16E2218DC201917CDB181221ECB10105EDB16E2218DC331288933128892312386886896912612988323123868868969126129883C32B222925DC2020EBB16D191622DE31E25CC32B222925DC2020EBB16D191622DE31E25C9838E12912BD272426CB2720C1417BE2524DC2621DE9838E12912BD272426CB2720C1417BE2524DC2621DE68126666812666E3133E9328D31B926B26E831B28DD273E3133E9328D31B926B26E831B28DD27323E35ED27D32C34B30282023E35ED27D32C34B302820E28CBE28CB21021030A30A30A30A圖3.8的最小代價搜索樹圖3.8的最小代價搜索樹可以看出，其最短路經(jīng)是A-C-D-E-B-A或A-B-E-D-C-A其實，它們是同一條路經(jīng)。3.9為什么說深度優(yōu)先搜索和代價樹的深度優(yōu)先搜索可以看成局部擇優(yōu)搜索的兩個特例解：深度優(yōu)先搜索、代價樹的深度優(yōu)先搜索以及局部優(yōu)先搜索都是以子節(jié)點作為考察范圍，但節(jié)點選擇的標(biāo)準(zhǔn)不同。如果取估價函數(shù)f(n)=g(n)，則它將退化為代價樹的深度優(yōu)先搜索。如果取估價函數(shù)f(n)=d(n)，則它將退化為深度優(yōu)先搜索。因此，深度優(yōu)先搜索和代價樹的深度優(yōu)先搜索是局部擇優(yōu)搜索的兩個特例。3.10何謂估價函數(shù)在估價函數(shù)中，g〔n〕和h〔n〕各起什么作用解：見教材P82頁3.11設(shè)有如下構(gòu)造的移動將牌游戲：BBWWE其中，B表示黑色將牌，W表是白色將牌，E表示空格。游戲的規(guī)定走法是：(1)任意一個將牌可移入相鄰的空格，規(guī)定其代價為1；(2)任何一個將牌可相隔1個其它的將牌跳入空格，其代價為跳過將牌的數(shù)目加1。游戲要到達的目標(biāo)是把所有W都移到B的左邊。對這個問題，請定義一個啟發(fā)函數(shù)h(n)，并給出用這個啟發(fā)函數(shù)產(chǎn)生的搜索樹。判別這個啟發(fā)函數(shù)是否滿足下界要求在求出的搜索樹中，對所有節(jié)點是否滿足單調(diào)限制解：設(shè)h(x)=每個W左邊的B的個數(shù)，f(x)=d(x)+3*h(x)，其搜索樹如下：f(x)=0+12=12f(x)=0+12=12BBWWEf(x)=1+12=13f(x)=1+12=13BBEWWf(x)=1+12=13f(x)=1+12=13BBWEWf(x)=2+12=14f(x)=2+12=14f(x)=2+9=11f(x)=2+9=11BBEWWBEWBWf(x)=3+9=12f(x)=3+9=12EBWBWf(x)=4+6=10f(x)=4+6=10WBEBWf(x)=5+3=8f(x)=5+3=8WBWBEf(x)=6+3=9f(x)=6+3=9WBWEBf(x)=7+0=7f(x)=7+0=7WBWEB3.12局部擇優(yōu)搜索與全局擇優(yōu)搜索的一樣之處與區(qū)別是什么解：根據(jù)搜索過程中選擇擴展節(jié)點的范圍，啟發(fā)式搜索算法可分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。其中，全局擇優(yōu)搜索算法每當(dāng)需要擴展節(jié)點時，總是從Open表的所有節(jié)點中選擇一個估價函數(shù)值最小的節(jié)點進展擴展，局部擇優(yōu)搜索算法每當(dāng)需要擴展節(jié)點時，總是從剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的節(jié)點進展擴展。3.13設(shè)有如圖3.29所示的與/或樹，請分別用與/或樹的廣度優(yōu)先搜索和深度優(yōu)先搜索求出解樹。AABCDt2t3t4t1圖3.29習(xí)題3.13的與/或樹tC解：廣度優(yōu)先搜索：AABCDt2t3t4t1tC深度優(yōu)先搜索：AABCDt2t3t4t1tC3.14設(shè)有如圖3.30的與/或/樹，請分別按和代價法及最大代價法求解樹的代價。AABCDt2t3t4t1圖3.30習(xí)題3.14的與/或樹56217223E解：假設(shè)按和代價法，則該解樹的代價為：h(A)=2+3+2+5+2+1+6=21假設(shè)按最大代價法，則該解樹的代價為：h(A)=max{h(B)+5,h(C)+6}=max{(h(E)+2)+5,h(C)+6}=max{(max(2,3)+2)+5,max(2,1)+6}=max((5+5,2+6)=103.15設(shè)有如圖3.31所示的博弈樹，其中最下面的數(shù)字是假設(shè)的估值，請對該博弈樹作如下工作：(1)計算各節(jié)點的倒推值；利用α-β剪枝技術(shù)剪去不必要的分枝。圖3.圖3.31習(xí)題3.15的博弈樹305-336-2354-3068-3369S0ABCDEFGHIJKLNM解：各節(jié)點的倒推值和剪枝情況如以以以下圖所示：習(xí)題3.15的倒推值和剪枝情況習(xí)題3.15的倒推值和剪枝情況305-336-2354-3068-336≤0≥0≤0≤-39≤3≥3≤4≥4≤4≥4≤-3≤6≥6S0ABCDEFGHIJKMNL搜索策略局部參考答案4.1什么是計算智能它包括哪些主要分支解：計算智能是借鑒仿生學(xué)的思想，基于對生物體的構(gòu)造、進化、行為與機理的認(rèn)識，以模型為根基，以分布、并行、仿生計算為特征去模擬生物體和人類的智能；P974.2請說明計算智能〔CI〕、人工智能〔AI〕及生物智能〔BI〕之間的關(guān)系。解：貝茲德克將智能和神經(jīng)網(wǎng)絡(luò)都分為計算的，人工的和生物的三個層次，底層是計算智能〔CI〕，它通過數(shù)值計算來實現(xiàn)的；中層人工智能〔AI〕，它是通過生物神經(jīng)系統(tǒng)來實現(xiàn)的；頂層是生物智能〔BI〕，它是通過生物神經(jīng)系統(tǒng)來實現(xiàn)的。4.3生物神經(jīng)元由哪幾局部組成各局部的功能是什么解：生物神經(jīng)元由細胞體，軸突和樹突三個主要局部組成細胞體是神經(jīng)元主體，用于處理有樹突承受的其他神經(jīng)元傳來的信號；軸突是用來向外傳遞神經(jīng)元產(chǎn)生的輸出電信號；樹突是神經(jīng)元輸出端，用于接收從其他神經(jīng)元的突觸傳來的信號。P994.4什么是人工神經(jīng)元它有哪幾種主要模型解：人工神經(jīng)元是對生物神經(jīng)元的抽象和模擬。它主要有以下幾種模型：〔1〕閾值型〔2〕分段成性型〔3〕S型〔4〕子閾累積型4.5什么是人工神經(jīng)網(wǎng)絡(luò)它有哪些聯(lián)結(jié)方式解：人工神經(jīng)網(wǎng)絡(luò)是對人類神經(jīng)系統(tǒng)的一種模擬。它有幾種聯(lián)結(jié)方式：前饋網(wǎng)絡(luò)和反響網(wǎng)絡(luò)。4.6人工神經(jīng)網(wǎng)絡(luò)的典型模型有哪幾種簡述其中的兩種主要模型。解：人工神經(jīng)網(wǎng)絡(luò)的典型模型：〔1〕感知器模型〔2〕BP網(wǎng)絡(luò)模型〔3〕hopfield網(wǎng)絡(luò)模型P1044.7什么是進化計算它包括哪些主要內(nèi)容解：進化計算以達爾文進化論的“物競天擇，適者存在〞作為算法的進化規(guī)則，并結(jié)合孟德爾的遺傳變異理論，將生物進化過程中的繁殖，變異，競爭和選擇引入到算法中。4.8什么是遺傳算法簡述其基本思想和基本構(gòu)造。解：遺傳算法是在模擬自然界生物遺傳進化過程中形成的一種自適應(yīng)優(yōu)化的概率搜索算法。遺傳算法的基本思想是用模擬生物和人類進化的方法來求解復(fù)雜問題遺傳算法的基本構(gòu)造：染色體編碼，初始種群設(shè)定，適度函數(shù)設(shè)定，遺傳操作設(shè)計等P1124.9什么是種群什么是個體什么是染色體個體和染色體之間的關(guān)系是什么解：種群是指用遺傳算法求解問題時，初始給定的多個解的集合，它是問題解空間的子集個體是指種群中的單個元素，它通常是由一個用于描述其基本遺傳構(gòu)造的數(shù)據(jù)構(gòu)造來表示染色體是對個體進展編碼后所得到的編碼串。4.10什么是遺傳編碼有哪幾種常用的編碼算法解：遺傳編碼是指把實際問題的構(gòu)造變換為遺傳算法的染色體構(gòu)造。常用的遺傳編碼有二進制編碼，格雷編碼，實數(shù)編碼和字符編碼等。4.11什么是適應(yīng)度函數(shù)常用的適應(yīng)度函數(shù)有哪幾種解：適應(yīng)度函數(shù)是一種用來對種群中各個個體的環(huán)境適應(yīng)性進展度量的函數(shù)。其函數(shù)值決定著染色體的優(yōu)劣程度，是遺傳算法實現(xiàn)優(yōu)勝劣汰的主要依據(jù)。常用的適用度函數(shù)有〔1〕原始適應(yīng)度函數(shù)〔2〕標(biāo)準(zhǔn)適應(yīng)度函數(shù)等4.12什么是選擇操作常用的選擇操作有哪幾種解：選擇操作是指根據(jù)選擇概率按某種策略從當(dāng)前種群中挑選出一定數(shù)目的個體，使它們能夠有更多的時機遺傳到下一代中，常用的選擇策略可分為比例選擇，排序選擇和競技選擇三種類型。4.13什么是穿插操作常用的穿插操作有哪幾種解：穿插選擇是指按照某種方式對選擇的父代個體的染色體的局部基因進展交配重組，從而形成新的個體。常用的穿插操作有二進制值穿插和實值穿插兩種。4.14什么是變異操作常用的變異操作有哪幾種解：變異操作是指對選擇中個體的染色體中的某些基因進展變動，以形成新的個體。常用的變異操作有二進制值變異和實值變異兩種。4.15設(shè)種群規(guī)模為4，采用二進制編碼，適應(yīng)度函數(shù)f〔x〕=，初始種群如表4.19所示。編號個體串x適應(yīng)度百分比累計百分比選中次數(shù)1010100100411001201117假設(shè)遺傳操作規(guī)定如下：選擇概率=1,選擇操作用輪盤賭算法，且依次生成的4個隨機數(shù)分別是0.42,0.16,0.89和0.71；穿插概率=1，穿插算法為單點穿插，穿插點為3，穿插順序按個體在種群中的順序；變異概率=0。請完成本輪選擇，穿插和變異操作，并給出所得到的下一代種群。編號個體串x適應(yīng)度百分比累計百分比選中次數(shù)10101010032.3632.36101004165.1837.54011001214444.6084.142011174915.861001解：〔1〕本次選擇后所得到的新的種類為=1100，=1010，=0111，=1100〔2〕編號個體串交對象穿插位子代適應(yīng)值11003110014410103101010001113011036110031101169=0=1100=1010=0110=11014.16什么是模糊性它與隨機性有什么區(qū)別請舉出日常生活中的例子。解：人們把因沒有嚴(yán)格邊界劃分而無法準(zhǔn)確刻畫的現(xiàn)象稱為模糊現(xiàn)象。隨機性是偶然性的一種形式，只有某概率的事件集合中的各個事件所表現(xiàn)出來的不確定性。4.17請說明模糊概念、模糊集及隸屬函數(shù)三者之間的關(guān)系。解：模糊集是一種用來描述模糊現(xiàn)象和模糊概念的數(shù)學(xué)工具。一個模糊集與其隸屬函數(shù)之間是一一對應(yīng)關(guān)系，即一個模糊集只能有一個隸屬函數(shù)來刻畫，一個隸屬函數(shù)也只能刻畫一個模糊集。4.18設(shè)某小組有5個同學(xué)，分別為S1,S2,S3,S4,S5。假設(shè)對每個同學(xué)的“學(xué)習(xí)好〞程度打分：S1:95S2:85S3:80S4:70S5:90這樣就確定了一個模糊集F，它表示該小組同學(xué)對“學(xué)習(xí)好〞這一模糊概念的隸屬程度，請寫出該模糊集。解：對模糊集為F，可表示為：F={0.9/S1,0.8/S2,0.7/S3,0.6/S4,0.85/S5}4.19設(shè)有論域U={u1,u2,u3,u4,u5}并設(shè)F、G是U上的兩個模糊集，且有F=0.9/u1+0.7/u2+0.5/u3+0.3/u4G=0.6/u3+0.8/u4+1/u5請分別計算F∩G，F(xiàn)∪G，﹁F。解：F∩G=(0.9∧0)/u1+(0.7∧0)/u2+(0.5∧0.6)/u3+(0.3∧0.8)/u4+(0∧1)/u5=0/u1+0/u2+0.5/u3+0.3/u4+0/u5=0.5/u3+0.3/u4F∪G=(0.9∨0)/u1+(0.7∨0)/u2+(0.5∨0.6)/u3+(0.3∨0.8)/u4+(0∨1)/u5=0.9/u1+0.7/u2+0.6/u3+0.8/u4+1/u5﹁F=(1-0.9)/u1+(1-0.7)/u2+(1-0.5)/u3+(1-0.3)/u4+(1-0)/u5=0.1/u1+0.3/u2+0.5/u3+0.7/u4+1/u54.20何謂模糊關(guān)系它若何表示解：模糊集上的模糊關(guān)系是對普通集合上確實定關(guān)系的擴大。在普通集合中，關(guān)系是通過笛卡爾乘積定義的4.21設(shè)有如下兩個模糊關(guān)系：請寫出R1與R2的合成R1οR2。解：R(1,1)=(0.3∧0.2)∨(0.7∧0.6)∨(0.2∧0.9)=0.2∨0.6∨0.2=0.6R(1,2)=(0.3∧0.8)∨(0.7∧0.4)∨(0.2∧0.1)=0.3∨0.4∨0.1=0.4R(2,1)=(1∧0.2)∨(0∧0.6)∨(0.4∧0.9)=0.2∨0∨0.4=0.4R(2,2)=(1∧0.8)∨(0∧0.4)∨(0.4∧0.1)=0.8∨0∨0.1=0.8R(3,1)=(0∧0.2)∨(0.5∧0.6)∨(1∧0.9)=0.2∨0.6∨0.9=0.9R(3,2)=(0∧0.8)∨(0.5∧0.4)∨(1∧0.1)=0∨0.4∨0.1=0.4因此有4.22設(shè)F是論域U上的模糊集，R是U×V上的模糊關(guān)系，F(xiàn)和R分別為：求模糊變換FοR。解：={0.1∨0.4∨0.6,0.3∨0.6∨0.3,0.4∨0.6∨0}={0.6,0.6,0.6}4.23什么是等價類什么是等價劃分解：等價類設(shè)B?A對任意對象X∈U，關(guān)于B的等價類［X］＝｛Y∈U｜〔X，Y〕∈IND〔B〕｝等價類的集合稱為等價劃分4.24什么是上近似什么是下近似若何由上近似和下近似定義邊界區(qū)域若何由邊界區(qū)域定義粗糙集解：近似：變X?U，B?AX對B的下近似B〔x〕可定義為X所包含的關(guān)于B的所有等價類的并集B〔x〕=U{[x]|[x]∈x}X對B的上近似B〔x〕可定義為X交集非空的關(guān)于B的所有等價類的并集B〔x〕=U{[x]|[x]∩X≠?}設(shè)x?U，B?A，對象集X關(guān)于屬性集B的邊界區(qū)域定義為BN(x)=B〔x〕-B〔x〕設(shè)x?U，B?A，由對象集X關(guān)于屬性集B的邊界區(qū)域的定義，假設(shè)BN(x)≠?，則稱BN(x)是對象集x關(guān)于屬性集B的粗糙集4.25什么是決策表約簡決策表約簡主要有哪幾個階段解：決策約簡表是指化簡決策表中的條件屬性和屬性值，使決策表在保持原有決策能力的同時具有較少的條件屬性和屬性值決策表約簡有以下幾個階段〔1〕一致性檢查〔2〕屬性約簡〔3〕屬性值約簡4.26什么是清楚矩陣清楚矩陣的作用是什么解：對信息系統(tǒng)IS=〔u,a,v,f〕,令u={u，u，u，u...u，},n=|u|為u、中元素個數(shù)則IS關(guān)于屬性集A的清楚矩陣M〔IS〕是一個n×n階矩陣，且矩陣元素定義為m={a∈A|fa〔ui〕≠fa〔uj〕}〔i，j=1,2,3...n〕構(gòu)造清楚矩陣可得到約簡核4.27設(shè)決策表如表4.20所示，求該決策表的清楚矩陣。其中a，b，c，d為條件屬性，e為決策屬性。AUabcde1021000121202100022211210解：?acdeaadeb?acdeceabcde?adeab?abde?4.28設(shè)化簡后的決策表如以以下圖，請分別求該決策表的核值表和約簡表。AUace120011220022解：屬性集A的清楚矩陣?aceaae?acece?ae?約簡核的構(gòu)造CORE〔A〕={a}與約簡核交集為空的mij有{c，e}選擇e屬性參加到約簡核得到一個約簡{a，e}AUace1x00x12x00x2計算智能局部參考答案5.1什么是不確定性推理為什么要采用不確定推理解：P137頁5.2不確定性推理中需要解決的基本問題有哪些解：〔1〕不確定性的表示〔2〕不確定性的匹配〔3〕組合證據(jù)不確定性的計算〔4〕不確定性的更新〔5〕不確定性結(jié)論的合成5.3不確定性推理可以分為哪幾種類型解：按數(shù)值的方法類型劃分，可分為基于概率論的有關(guān)理論開展起來的方法和基于模糊邏輯理論開展起來的方法。按是否采用數(shù)值的方法劃分可分為數(shù)值方法和非數(shù)值方法兩大類型。5.4何謂可信度由規(guī)則強度CF(H,E)的定義說明它的含義。解：可信度是指人們根據(jù)以往經(jīng)歷對某個事物或現(xiàn)象為真的程度做出的一個判斷。5.5設(shè)有如下一組推理規(guī)則:r1:IFE1THENE2(0.6)r2:IFE2AND