【文章內容簡介】 (0，1，1，X)狼、羊在右岸； (0，X，1，1)羊、菜在右岸；14. 請闡述狀態(tài)空間的一般搜索過程。OPEN表與CLOSED表的作用是什么？ 答：先把問題的初始狀態(tài)作為當前擴展節(jié)點對其進行擴展，生成一組子節(jié)點，然后檢查問題的目標狀態(tài)是否出現(xiàn)在這些子節(jié)點中。若出現(xiàn)，則搜索成功，找到了問題的解；若沒出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點中選擇一個節(jié)點作為當前擴展節(jié)點。重復上述過程，直到目標狀態(tài)出現(xiàn)在子節(jié)點中或者沒有可供操作的節(jié)點為止。所謂對一個節(jié)點進行“擴展”是指對該節(jié)點用某個可用操作進行作用，生成該節(jié)點的一組子節(jié)點。 OPEN表用于存放剛生成的節(jié)點，對于不同的搜索策略，節(jié)點在OPEN表中的排序是不同的。 CLOSED表用于存放將要擴展或者已擴展的節(jié)點。15. 廣度優(yōu)先搜索與深度優(yōu)先搜索各有什么特點？ 答：廣度優(yōu)先搜索就是始終先在同一級節(jié)點中考查,只有當同一級節(jié)點考查完之后,才考查下一級節(jié)點?；蛘哒f,是以初始節(jié)點為根節(jié)點，向下逐級擴展搜索樹。所以,廣度優(yōu)先策略的搜索樹是自頂向下一層一層逐漸生成的。 深度優(yōu)先搜索就是在搜索樹的每一層始終先只擴展一個子節(jié)點,不斷地向縱深前進,直到不能再前進（到達葉子節(jié)點或受到深度限制） 時，才從當前節(jié)點返回到上一級節(jié)點，沿另一方向又繼續(xù)前進。這種方法的搜索樹是從樹根開始一枝一枝逐漸形成的。深度優(yōu)先搜索亦稱為縱向搜索。由于一個有解的問題樹可能含有無窮分枝，深度優(yōu)先搜索如果誤入無窮分枝(即深度無限)，則不可能找到目標節(jié)點。所以，深度優(yōu)先搜索策略是不完備的。另外，應用此策略得到的解不一定是最佳解(最短路徑)。 廣度優(yōu)先搜索與深度優(yōu)先搜索都屬于盲目搜索。, 邊上的數字是兩城市間的距離。用圖搜索技術編寫程序, 求解以下問題： 解：domains 　 p=string 　 d=integer pp=p* 　 predicates road(p,p,d)　 path(p,p,pp,d) 　member(p,pp)　clauses path(X,Y,L,D):road(X,Y,D),L=[X|[Y]]. 　 path(X,Y,L,D): 　 road(X,Z,D1),%從當前點向前走到下一點Z 　 not(member(Z,L)), 　path(Z,Y,［Z|L］,D2),D=D1+D2.%再找Z到出口Y的路徑 　 member(X,［X|_］). 　 member(X,［_|T］)if member(X,T). 　 road(A,B,D):road(B,A,D). %因為沒向圖 /* 交通圖 */ 　 road(“西安”,”北京”,1165). road(“西安”,”上海”,1511). 　 road(“西安”,“廣州” ,2129). road(“西安”,”昆明”,1942).　 road(“昆明”,”北京”,3179). road(“昆明”,”上?！?2677). 　 road(“昆明”,“廣州”,2216). road(“北京”,”廣州”,2510). 　 road(“上海”,”北京”,1462). road(“廣州”,“上?！?1511). 　 （1）path(“西安”,”北京”,L,D),write(L,D). 　 （2）path(“西安”,”北京”,L,D),　　 　 member(“上海”,L),write(L,D). ?。?）path(“西安”,”北京”,L,D), 　 　　member(“上海”,L),not(member(“昆明”,L)), write(L,D).17. 何謂估價函數？ 在估價函數中,g(x)和h(x)各起什么作用？  答：估價函數用來估計節(jié)點重要性的函數。估價函數f(x)被定義為從初始節(jié)點S0出發(fā)，約束經過節(jié)點x到達目標節(jié)點Sg的所有路徑中最小路徑代價的估計值。它的一般形式為： f(x)=g(x)+h(x)其中，g(x)是從初始節(jié)點S0到節(jié)點x的實際代價；h(x)是從節(jié)點x到目標節(jié)點Sg的最優(yōu)路徑的估計代價。 18. 局部擇優(yōu)搜索與全局擇優(yōu)搜索的相同處與區(qū)別各是什么？ 答：局部擇優(yōu)搜索與全局擇優(yōu)搜索的區(qū)別是，擴展節(jié)點N后僅對N的子節(jié)點按啟發(fā)函數值大小以升序排序，再將它們依次放入OPEN表的首部。故算法從略。19. 傳教士和野人問題。有三個傳教士和三個野人一起來到河邊準備渡河, 河邊有一條空船,且傳教士和野人都會劃船, 但每次最多可供兩人乘渡。河的任何一岸以及船上一旦出現(xiàn)野人人數超過傳教士人數,野人就會把傳教士吃掉。為安全地渡河,傳教士應如何規(guī)劃渡河方案？試給出該問題的狀態(tài)圖表示, 并用PROLOG語言編程求解之。 若傳教士和野人的數目均為五人,渡船至多可乘三人,請定義一個啟發(fā)函數, 并給出相應的搜索樹。 解：首先選取描述問題狀態(tài)的方法。在這個問題中，需要考慮兩岸的修道士人數和野人數，還需要考慮船在左岸還是在右岸。從而可用一個三元組來表示狀態(tài)： S=(m, c, b) 其中，m表示左岸的修道士人數，c表示左岸的野人數，b表示左岸的船數。 右岸的狀態(tài)可由下式確定：右岸修道士數：m39。=3m；右岸野人數：c39。=3c；右岸船數：b39。=1b在這種表示方式下，m和c都可取0、3中之一，b可取0和1中之一。因此，共有442=32種狀態(tài)。 這32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士被野人吃掉的狀態(tài)，有意義的狀態(tài)只有16種： S0=(3, 3, 1) S1=(3, 2, 1) S2=(3, 1, 1) S3=(2, 2, 1) S4=(1, 1, 1) S5=(0, 3, 1) S6=(0, 2, 1) S7=(0, 1, 1) S8=(3, 2, 0) S9=(3, 1, 0) S10=(3, 0, 0) S11=(2, 2, 0) S12=(1, 1,0) S13=(0, 2, 0) S14=(0, 1, 0) S15=(0, 0, 0)有了這些狀態(tài)，還需要考慮可進行的操作。 操作是指用船把修道士或野人從河的左岸運到右岸，或從河的右岸運到左岸。 每個操作都應當滿足如下條件： 一是船至少有一個人（m或c）操作，離開岸邊的m和c的減少數目應該等于到達岸邊的m和c的增加數目；二是每次操作船上人數不得超過2個； 三是操作應保證不產生非法狀態(tài)。 因此，操作應由條件部分和動作部分： 條件：只有當其條件具備時才能使用動作：刻劃了應用此操作所產生的結果。操作的表示： 用符號Pij表示從左岸到右岸的運人操作用符號Qij表示從右岸到左岸的操作 其中： i表示船上的修道士人數 j表示船上的野人數操作集 本問題有10種操作可供選擇： F={P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20} 下面以P01和Q01為例來說明這些操作的條件和動作。 操作符號 條件 動作 P01 b=1, m=0或3, c≥1 b=0, c=c1 Q01 b=0, m=0或3，c≤2 b=1, c=c+1 （1）凡事清潔的東西就有人喜歡（2）人們都不喜歡蒼蠅用歸結原理證明蒼蠅是不清潔的：答案：用八元組(X0,X1,X2,X3,X4,X5,X6,X7)表示第1~8行的棋子，值(x0,x1,x2,x3,x4,x5,x6,x7)表示其在列上的位置。狀態(tài)可表示為八元組的一組值。專家系統(tǒng)：所謂專家系統(tǒng)，就是基于人類專家知識的程序系統(tǒng)。專家系統(tǒng)的特點是擁有大量的專家知識（包括領域知識和經驗知識），能模擬專家的思維方式，面對領域中復雜的實際問題，能作出專家水平級的決策，像專家一樣解決實際問題。專家系統(tǒng)的特征：1)處理問題的性質：善于解決不確定、非結構化、沒有算法解或雖有算法解但在現(xiàn)有機器上無法實施的困難問題。2)處理問題方法：靠知識和推理來解決問題3系統(tǒng)結構：強調知識與推理的分離，系統(tǒng)具有很好的靈活性和可擴充性。4具有解釋功能：在運行中能回答用戶提出的問題，同時還能對輸出（結論）或處理問題的過程作出解釋。5具有“自學習”能力：即不斷對已有知識進行擴充、完善和提煉。6專家系統(tǒng)它始終如一地以專家級水平求解問題。各部分功能：1知識庫：以某種表示形式存儲于計算機中的知識集合。知識庫中的知識一般包括專家知識、領域知識和元知識。2推理機：推理機就是實現(xiàn)機器推理的程序，包括通常的邏輯推理和基于產生式的操作。3動態(tài)數據庫：是存放初始證據事實、推理結果和控制信息的場所。4。人機界面：最終用戶與專家系統(tǒng)的交互界面5解釋模塊：專門負責向用戶解釋專家系統(tǒng)的行為和結果。6知識庫管理系統(tǒng)：是知識庫的支撐軟件。其功能包括知識庫的建立、刪除、重組；知識的獲取、知識的檢查等。專家系統(tǒng)的應用和發(fā)展情況：醫(yī)學診斷/地質勘探/物質結構分析/生物遺傳研究/市場決策/生產管理。20世紀90年代模糊技術、神經網絡和面向對象等新技術迅速崛起，為專家系統(tǒng)注入了新的活力。知識獲?。褐R獲取是建造專家系統(tǒng)的關鍵一步，也是較為困難的一步，被稱為建造專家系統(tǒng)的“瓶頸”。知識獲取大體有三種途徑。1人工獲?。杭从嬎銠C人員與領域專家合作，對有關領域知識和專家知識，進行挖掘、搜集、分析、綜合、整理、歸納，然后以某種表示形式存入知識庫。2半自動獲取，即利用某種專門的知識獲取系統(tǒng)，采取提示、指導或問答的方式，幫助專家提取、歸納有關知識，并自動記入知識庫。3自動獲取又可分為兩種形式：一種是系統(tǒng)本身具有一種機制，使得系統(tǒng)在運行過程中能不斷地總結經驗，并修改和擴充自己的知識庫；另一種是開發(fā)專門的機器學習系統(tǒng)，讓機器自動從實際問題中獲取知識，并填充知識庫。左解樹：為最優(yōu)解 右解樹按和代價法，代價為：g(S0)=12,g(A)=7, g(D)=4. 按最大代價法，代價為：g(S0)=10,g(A)=5, g(D)=2.第2章 知識表示方法部分參考答案 設有如下語句，請用相應的謂詞公式分別把他們表示出來：s(1) 有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花 。解：定義謂詞dP(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是下午將知識用謂詞表示為：a(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) 不是每個計算機系的學生都喜歡在計算機上編程序。解：定義謂詞S(x)：x是計算機系學生L(x, pragramming)：x喜歡編程序U(x,puter)：x使用計算機將知識用謂詞表示為：172。 (x) (S(x)→L(x, pragramming)∧U(x,puter))(5) 凡是喜歡編程序的人都喜歡計算機。解：定義謂詞P(x)：x是人L(x, y)：x喜歡y將知識用謂詞表示為：(x) (P(x)∧L(x,pragramming)→L(x, puter)) 用謂詞表示法求解機器人摞積木問題。設機器人有一只機械手，要處理的世界有一張桌子，桌上可堆放若干相同的方積木塊。機械手有4個操作積木的典型動作：從桌上揀起一塊積木；將手中的積木放到桌之上；在積木上再摞上一塊積木；從積木上面揀起一塊積木。積木世界的布局如下圖所示。ABCCAB圖 機器人摞積木問題解：(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 問題的目標狀態(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 添加表：HANDEMPTY(x)Putdown(x) 條件：H