人工智能期末復(fù)習(xí)題

【本材料—僅供參考】——（6）班by：cyjPAGE17-08-12-12《人工智能期末復(fù)習(xí)題》1．群智能與腦智能：腦智能是一種個體智能，是宏觀心理層次上高級的智能。群智能是一種社會智能（系統(tǒng)智能），屬于微觀生理層次上低級的神經(jīng)元。2．計(jì)算智能與符號智能：符號智能就是符號人工智能，它是模擬腦智能的人工智能，也就是所說的傳統(tǒng)人工智能或經(jīng)典人工智能。計(jì)算智能就是計(jì)算人工智能，它是模擬群智能的人工智能。3．搜索：顧名思義，就是從初始節(jié)點(diǎn)出發(fā)，沿著與之相連的邊試探地前進(jìn)，尋找目標(biāo)節(jié)點(diǎn)的過程(也可以是反向進(jìn)行)。4．知識：就是人們對客觀事物(包括自然的和人造的)及其規(guī)律的認(rèn)識，知識還包括人們利用客觀規(guī)律解決實(shí)際問題的方法和策略等。5．自然計(jì)算：就是模仿或借鑒自然界的某種機(jī)理而設(shè)計(jì)計(jì)算模型，這類計(jì)算模型通常是一類具有自適應(yīng)、自組織、自學(xué)習(xí)、自尋優(yōu)能力的算法。6．機(jī)器學(xué)習(xí)：顧名思義，機(jī)器學(xué)習(xí)就是讓計(jì)算機(jī)模擬人的學(xué)習(xí)行為，或者說讓計(jì)算機(jī)也具有學(xué)習(xí)的能力。7．模式識別：則指的是用計(jì)算機(jī)進(jìn)行物體識別。8．決策樹學(xué)習(xí)：決策樹是一種知識表示形式，構(gòu)造決策樹可以由人來完成，但也可以由機(jī)器從一些實(shí)例中總結(jié)、歸納出來，即機(jī)器學(xué)習(xí)而得。機(jī)器學(xué)習(xí)決策樹也就是所說的決策樹學(xué)習(xí)。9．從系統(tǒng)結(jié)構(gòu)看，智能計(jì)算機(jī)分為智能硬件平臺和智能操作系統(tǒng)兩大部分。10．人工智能的三個最基本、最核心的技術(shù)實(shí)現(xiàn)人工智能的方法雖然很多，但歸納起來，“表示”、“運(yùn)算”、“搜索”則是人工智能的三個最基本、最核心的技術(shù)。11．從所承擔(dān)的工作和任務(wù)性質(zhì)來看，Agent的分類：信息型Agent、合作型Agent、接口型Agent、移動型Agent等。12．用計(jì)算機(jī)來實(shí)現(xiàn)狀態(tài)圖的搜索，有兩種最基本的方式：樹式搜索和線式搜索。13．智能機(jī)器人至少應(yīng)具備哪四種機(jī)能？感知機(jī)能——獲取外部環(huán)境信息以便進(jìn)行自我行動監(jiān)視的機(jī)能；運(yùn)動機(jī)能——施加于外部環(huán)境的相當(dāng)于人的手、腳底動作機(jī)能；思維機(jī)能——求解問題的認(rèn)識、推理、判斷機(jī)能；人—機(jī)通信機(jī)能——理解指示命令、輸出內(nèi)部狀態(tài)，與人進(jìn)行信息交換的機(jī)能。14．知識獲取大體哪三種途徑：(1)人工獲取(2)半自動獲取(3)自動獲取15．知識發(fā)現(xiàn)主要有這些方法：(1)統(tǒng)計(jì)方法(2)機(jī)器學(xué)習(xí)方法(3)粗糙集及模糊集(4)智能計(jì)算方法(5)可視化16．從模擬的智能層次和所用的方法看，人工智能可分為符號智能和計(jì)算智能兩大主要分支領(lǐng)域。17．PRPLOG語言的三種語句分別是：事實(shí)、規(guī)則和問題。18．產(chǎn)生式系統(tǒng)由三部分組成：產(chǎn)生式規(guī)則庫、推理機(jī)和動態(tài)數(shù)據(jù)庫，產(chǎn)生式規(guī)則庫推理機(jī)產(chǎn)生式規(guī)則庫推理機(jī)動態(tài)數(shù)據(jù)庫

19．機(jī)器定理證明有四個主要方法：(1)自然演繹法；(2)判定法；(3)定理證明器；(4)計(jì)算機(jī)輔助證明。20．在啟發(fā)式搜索所使用的估價函數(shù)f(x)中，g(x)和h(x)各起什么作用？g(x)為從初始節(jié)點(diǎn)So到節(jié)點(diǎn)x已經(jīng)付出的代價。利用啟發(fā)函數(shù)h(x)制導(dǎo)的啟發(fā)式搜索,實(shí)際是一種深度優(yōu)先的搜索策略。21．什么是Agent，簡述Agent基本特性。Agent指的是一種實(shí)體，而且是一種具有智能的實(shí)體。這種實(shí)體可以是智能軟件、智能設(shè)備、智能機(jī)器人或智能計(jì)算機(jī)系統(tǒng)等等，甚至也可以是人。Agent應(yīng)具有如下基本特性：(1)自主性：亦稱自治性,即能夠在沒有人或別的Agent的干預(yù)下,主動地自發(fā)地控制自身的行為和內(nèi)部狀態(tài),并且還有自己的目標(biāo)或意圖。(2)反應(yīng)性：即能夠感知環(huán)境,并通過行為改變環(huán)境。(3)適應(yīng)性：即能根據(jù)目標(biāo)、環(huán)境等的要求和制約作出行動計(jì)劃,并根據(jù)環(huán)境的變化,修改自己的目標(biāo)和計(jì)劃。(4)社會性：即一個Agent一般不能在環(huán)境中單獨(dú)存在,而要與其他Agent在同一環(huán)境中協(xié)同工作。22．何為不確定性？不確定性有哪些類型？在信息和知識中，含有不肯定、不可靠、不準(zhǔn)確、不確切、不精確、不嚴(yán)格、不嚴(yán)密、不完全甚至不一致的成分，現(xiàn)在人們一般或者習(xí)慣上將這些信息特征統(tǒng)稱為不確定性。不確定性有：(狹義)不確定性、不確切性(模糊性)、不完全性、不一致性和時變性等幾種類型。23．什么是專家系統(tǒng)，專家系統(tǒng)包括哪些基本部分？每一部分的主要功能是什么？顧名思義，專家系統(tǒng)(ES)就是能像人類專家一樣解決困難、復(fù)雜的實(shí)際問題的計(jì)算機(jī)(軟件)系統(tǒng)。專家系統(tǒng)包括以下幾個基本部分：(及各自的主要功能)(1)知識庫：通常以一個個文件的形式存放于外部介質(zhì)上，專家系統(tǒng)運(yùn)行時將被調(diào)入內(nèi)存。知識庫中的知識通常就是按照知識的表示形式、性質(zhì)、層次、內(nèi)容來組織的，構(gòu)成了知識庫的結(jié)構(gòu)。(2)推理機(jī)：實(shí)現(xiàn)(機(jī)器)推理。包括通常的邏輯推理或基于產(chǎn)生式的操作。(3)動態(tài)數(shù)據(jù)庫：它是存放初始證據(jù)事實(shí)、推理結(jié)果和控制信息的場所，它只在系統(tǒng)運(yùn)行期間產(chǎn)生、變化和撤消。(4)人機(jī)界面：用戶與專家系統(tǒng)的交互界面，并輸出結(jié)果以及對系統(tǒng)的行為和最終結(jié)果做出適當(dāng)解釋。(5)解釋模塊：向用戶解釋專家系統(tǒng)的行為和結(jié)果。(6)知識庫管理系統(tǒng)：主要在專家系統(tǒng)的開發(fā)階段使用，但在專家系統(tǒng)的運(yùn)行階段也要經(jīng)常用來對知識庫進(jìn)行增、刪、改、查等各種管理工作。24．請簡述遺傳算法的三種遺傳操作。選擇-復(fù)制(selectionreproduction)操作是模擬生物界優(yōu)勝劣汰的自然選擇法則的一種染色體運(yùn)算,就是從種群中選擇適應(yīng)度較高的染色體進(jìn)行復(fù)制,以生成下一代種群。交叉(crossover)亦稱交換、交配或雜交,就是互換兩個染色體某些位上的基因。變異(mutation)亦稱突變,就是改變?nèi)旧w某個(些)位上的基因。25．實(shí)現(xiàn)機(jī)器的自然語言理解都涉及的工作有：(1)語法分析；(2)語義分析；(3)語用分析。26．設(shè)有如圖所示的一棵與或樹，請指出解樹；并分別按和代價及最大代價求解樹代價；然后，指出最優(yōu)解樹。解：由左邊的解樹可得：按和代價：g(D)＝4=1+2+1g(A)=7=1+2+1+3g(So)=12=7+5按最大代價：g(D)＝2，g(A)=5，g(So)=10由右邊的解樹可得：g(E)＝∞，g(B)＝∞∴So→A→D為最優(yōu)解樹即左邊為最優(yōu)解樹。

27.設(shè)有如下一組規(guī)則：r1：ifE1thenE2(0.6)r2：ifE2andE3thenE4(0.8)r3：ifE4thenH(0.7)r4：ifE5thenH(0.9)且已知CF(E1)=0.5，CF(E3)=0.6，CF(E5)=0.4用確定性理論求CF(H)。解：CF(E2)=0.5×0.6CF(E4)=0.8×min(0.3，0.6)=0.8×0.3=0.24∵CF(H)1=0.24×0.7=0.168≥0CF(H)2=0.9×0.4=0.36≥0∴CF(H)=CF(H)1+CF(H)2－CF(H)1CF(H)2=0.168+0.36－0.168×0.36=0.528－0.06048=0.4675228．設(shè)有如下一組產(chǎn)生式規(guī)則和證據(jù)事實(shí)，試用確定性理論求出CF(E)。規(guī)則:①ifAthenB(0.9)②ifBandCthenD(0.8)③ifAandCthenD(0.7)④ifBorDthenE(0.6)事實(shí)：A，CF(A)=0.8；C，CF(C)=0.9解：由規(guī)則①得：CF(B)=0.9×0.8=0.72由規(guī)則②得：CF(D)1=0.8×min{0.72，0.9}=0.8×0.72=0.576由規(guī)則③得：CF(D)2=0.7×min{0.8，0.9}=0.7×0.8=0.56從而CF(D)=CF(D)1+CF(D)2－CF(D)1×CF(D)2=0.576+0.56－0.576×0.56=0.81344由規(guī)則④得：CF(E)=0.6×max{0.72，0.81344}=0.6×0.81344=0.48806429．設(shè)已知：（1）凡是清潔的東西就有人喜歡；（2）人們都不喜歡蒼蠅。用歸結(jié)原理證明：蒼蠅是不清潔的。clear(y),like(x,y)已知：①clear(y)→like(x,y)②like(x,c)結(jié)論：③clear(c)證明：①clear(y)∨like(x,y)②like(x,c)③clear(c)④clear(c){c/y}⑤□③④30．某公司招聘工作人員，有A,B,C三人應(yīng)聘，經(jīng)面試后，公司表示如下想法：（1）三人中至少錄取一人（2）如果錄取A而不錄取B,則一定錄取C（3）如果錄取B,則一定錄取B試用歸結(jié)原理求證：公司一定錄取CP(x)：錄取x.①P(A)∨P(B)∨P(C)②P(A)∧P(B)→P(C)③P(B)→P(C)結(jié)論：P(C)G.證明：①P(A)∨P(B)∨P(C)②P(A)∨P(B)∨P(C)③P(B)∨P(C)④P(C)(G)⑤P(B)∨P(C)①②⑥P(C)③⑤⑦□④⑥31．求下面謂詞公式的子句集，要求寫出具體步驟。（1）解：

（2）(P102例5.7)解：或P(x,f(x))∨Q(x,g(x))P(y,f(y))∨R(y,g(y))為原謂詞公式的字句集。 32．證明G是否可肯定是F1，F(xiàn)2的邏輯結(jié)論。要求寫出求解過程。解：①P(x)∨Q(y)∨L(x,y)F1F2②P(b)F2③P(z)∨L(w,z)G④R(a)①⑤{a/y}G⑤Q(a)②⑥{b/x}⑥P(x)∨L(x,a)③⑦{a/z}⑦L(b,a)④⑧⑧R(a)⑨□33．把下列語句用語義網(wǎng)絡(luò)表示(1)即“某個學(xué)生讀過《三國演義》”，其語義網(wǎng)絡(luò)表示為圖如下：謂詞公式的語義網(wǎng)絡(luò)student謂詞公式的語義網(wǎng)絡(luò)studentreadbookxread1三國演義subjectobjectISAISAISA(2)即“每個學(xué)生讀過《三國演義》”，其語義網(wǎng)絡(luò)表示為圖如下：GSGSstudentreadx三國演義subjectobjectISA分塊語義網(wǎng)絡(luò)Rread1bookISAISAISAF1．什么是人工智能？發(fā)展過程中經(jīng)歷了哪些階段？解：人工智能是計(jì)算機(jī)科學(xué)的一個重要分支，也是一門正在發(fā)展中的綜合性前沿學(xué)科，它是由計(jì)算機(jī)科學(xué)、控制論、信息論、神經(jīng)生理學(xué)、哲學(xué)、語言學(xué)等多種學(xué)科相互滲透而發(fā)展起來的，目前正處于發(fā)展階段尚未形成完整體系。發(fā)展過程中經(jīng)歷的階段有：第一階段（40年代中～50年代末）神經(jīng)元網(wǎng)絡(luò)時代第二階段（50年代中～60年代中）通用方法時代第三階段（60年代中～80年代初）知識工程時代第四階段（80年代中～90年代初）新的神經(jīng)元網(wǎng)絡(luò)時代第五階段（90年代初～現(xiàn)在）海量信息處理與網(wǎng)絡(luò)時代2．人工智能研究的基本內(nèi)容是什么？解：基本內(nèi)容是：搜索技術(shù)、知識表示、規(guī)劃方法、機(jī)器學(xué)習(xí)、認(rèn)知科學(xué)、自然語言理解與機(jī)器翻譯、專家系統(tǒng)與知識工程、定理證明、博弈、機(jī)器人、數(shù)據(jù)挖掘與知識發(fā)現(xiàn)、多Agent系統(tǒng)、復(fù)雜系統(tǒng)、足球機(jī)器人、人機(jī)交互技術(shù)等。3．人工智能主要有哪幾大研究學(xué)派？解：（１）符號主義學(xué)派：由心理學(xué)途徑產(chǎn)生，符號主義認(rèn)為人工智能起源于數(shù)理邏輯，人類認(rèn)識（智能）的基本元素是符號，而智能行為則是符號運(yùn)算的結(jié)果。（２）連接主義學(xué)派：由生理學(xué)途徑產(chǎn)生，連接主義又稱為仿生學(xué)派，認(rèn)為人工智能的基本元素是神經(jīng)元，智能產(chǎn)生于大量神經(jīng)元的并行分布式聯(lián)結(jié)之中，而智能行為則是聯(lián)結(jié)計(jì)算的結(jié)果。（３）行為主義學(xué)派：由生物演化途徑產(chǎn)生，行為主義認(rèn)為人工智能起源于控制論，提出智能取決于感知和行為，取決于對外界復(fù)雜環(huán)境的適應(yīng)，而不是表示和推理。４．人工智能有哪些主要的研究領(lǐng)域？解：（１）問題求解（２）邏輯推理與定理證明（３）自然語言理解（４）自動程序設(shè)計(jì)（５）專家系統(tǒng)（６）機(jī)器學(xué)習(xí)（７）神經(jīng)網(wǎng)絡(luò)（８）機(jī)器人學(xué)（９）模式識別（１０）機(jī)器視覺（１１）智能控制（１２）智能檢索（１３）智能調(diào)度與指揮（１４）分布式人工智能與Ａｇｅｎｔ（１５）計(jì)算智能與進(jìn)化計(jì)算（１６）數(shù)據(jù)挖掘與知識發(fā)現(xiàn)（１７）人工生命（１８）系統(tǒng)與語言工具1設(shè)有如下問題：（1）有五個相互可直達(dá)且距離已知的城市A、B、C、D、E，如圖所示；（2）某人從A地出發(fā)，去其它四個城市各參觀一次后回到A;（3）找一條最短的旅行路線請用產(chǎn)生式規(guī)則表示旅行過程。解：=1\*GB3①綜合數(shù)據(jù)庫（x）(x)中x可以是一個字母，也可以是一個字符串。=2\*GB3②初始狀態(tài)（A）=3\*GB3③目標(biāo)狀態(tài)（Ax1x2x3x4A）=4\*GB3④規(guī)則集：r1:IFL(S)=5THENGOTO(A)r2:IFL(S)<5THENGOTO(B)r3:IFL(S)<5THENGOTO(C)r4:IFL(S)<5THENGOTO(D)r5:IFL(S)<5THENGOTO(E)其中L(S)為走過的城市數(shù)，GOTO(x)為走向城市x=5\*GB3⑤路線如下圖所示:(A)(A)(AB)(AC)(AD)(AE)(ACB)(ACD)(ACE)(ACDB)(ACDE)(ACDEB)(ACDEBA)751010769108107起始目標(biāo)最短旅行路線為：A->C->D->E->B->A總距離為5+6+8+10+7=362神州大學(xué)和東方大學(xué)兩?；@球隊(duì)在東方大學(xué)進(jìn)行一場比賽，結(jié)局的比分是85：89，用語義網(wǎng)絡(luò)表示。1張某被盜，公安局派出五個偵察員去調(diào)查。研究案情時，偵察員A說“趙與錢中至少有一人作案”；偵察員B說“錢與孫中至少有一人作案”；偵察員C說“孫與李中至少有一人作案”；偵察員D說“趙與孫中至少有一人與此案無關(guān)”；偵察員E說“錢與李中至少有一人與此案無關(guān)”。如果這五個偵察員的話都是可信的，試用歸結(jié)演繹推理求出誰是盜竊犯。解：第一步：將5位偵察員的話表示成謂詞公式，為此先定義謂詞。 設(shè)謂詞P(x)表示是作案者，所以根據(jù)題意：A:P(zhao)∨P(qian)B:P(qian)∨P(sun)C:P(sun)∨P(li)D:﹁P(zhao)∨﹁P(sun)E:﹁P(qian)∨﹁P(li)以上每個偵察員的話都是一個子句。第二步：將待求解的問題表示成謂詞。設(shè)y是盜竊犯，則問題的謂詞公式為P(y)，將其否定并與ANSWER(y)做析?。害鑀(y)∨ANSWER(y)第三步：求前提條件及﹁P(y)∨ANSWER(y)的子句集，并將各子句列表如下：P(zhao)∨P(qian)P(qian)∨P(sun)P(sun)∨P(li)﹁P(zhao)∨﹁P(sun)﹁P(qian)∨﹁P(li)﹁P(y)∨ANSWER(y)第四步：應(yīng)用歸結(jié)原理進(jìn)行推理。P(qian)∨﹁P(sun)(1)與(4)歸結(jié)P(zhao)∨﹁P(li)(1)與(5)歸結(jié)P(qian)∨﹁P(zhao)(2)與(4)歸結(jié)P(sun)∨﹁P(li)(2)與(5)歸結(jié)﹁P(zhao)∨P(li)(3)與(4)歸結(jié)P(sun)∨﹁P(qian)(3)與(5)歸結(jié)P(qian)(2)與(7)歸結(jié)P(sun)(2)與(12)歸結(jié)ANSWER(qian)(6)與(13)歸結(jié)，σ={qian/y}ANSWER(sun)(6)與(14)歸結(jié),σ={sun/y}所以，本題的盜竊犯是兩個人：錢和孫。2任何兄弟都有同一個父親，John和Peter是兄弟，且John的父親是David，問Peter的父親是誰？解：第一步：將已知條件用謂詞公式表示出來，并化成子句集。那么，要先定義謂詞。定義謂詞：設(shè)Father(x,y)表示x是y的父親。設(shè)Brother(x,y)表示x和y是兄弟。將已知事實(shí)用謂詞公式表示出來：F1:任何兄弟都有同一個父親。(x)(y)(z)(Brother(x,y)∧Father(z,x)→Father(z,y))F2:John和Peter是兄弟。Brother(John,Peter)F3:John的父親是David。Father(David,John)將它們化成子句集，得S1={﹁Brother(x,y)∨﹁Father(z,x)∨Father(z,y),Brother(John,Peter),Father(David,John)}第二步：把問題用謂詞公式表示出來，并將其否定與謂詞ANSWER做析取。設(shè)Peter的父親是u，則有：Father(u,Peter)將其否定與ANSWER做析取，得 G:﹁Father(u,Peter)∨ANSWER(u)第三步：將上述公式G化為子句集S2，并將S1和S2合并到S。S2={﹁Father(u,Peter)∨ANSWER(u)}S=S1∪S2將S中各子句列出如下：（1）﹁Brother(x,y)∨﹁Father(z,x)∨Father(z,y)（2）Brother(John,Peter)（3）Father(David,John)（4）﹁Father(u,Peter)∨ANSWER(u)第四步：應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)。（5）﹁Brother(John,y)∨Father(David,y)（1）與（3）歸結(jié)，σ={David/z,John/x}（6）﹁Brother(John,Peter)∨ANSWER(David) （4）與（5）歸結(jié)，σ={David/u,Peter/y}（7）ANSWER(David)（2）與（6）歸結(jié)第五步：得到了歸結(jié)式ANSWER(David)，答案即在其中，所以u=David,即Peter的父親是David。1圖4-1是五城市間的交通路線圖，A城市是出發(fā)地，E城市是目的地，兩城市間的交通費(fèi)用（代價）如圖中數(shù)字所示。求從A到E的最小費(fèi)用交通路線。圖4-1圖4-1解：先將交通圖轉(zhuǎn)換為代價樹，如圖4-2所示。若用g(x)表示從初始節(jié)點(diǎn)s0到節(jié)點(diǎn)x的代價，用c(x1,x2)表示從父節(jié)點(diǎn)x1到子節(jié)點(diǎn)x2的代價，則有：g(x2)=g(x1)+c(x1,x2)AAC1B1D11D2E1E2B2E4C2E33423454523圖4-2方法一：代價樹的廣度優(yōu)先搜索（擴(kuò)展節(jié)點(diǎn)ｎ，將其子節(jié)點(diǎn)放入open表中，計(jì)算各子節(jié)點(diǎn)的代價，并按各節(jié)點(diǎn)的代價對open表中全部節(jié)點(diǎn)按從小到大的順序進(jìn)行排序（隊(duì)列））步驟如下：圖4-3-1圖4-3-1圖4-3-2圖4-3-2圖圖4-3-3圖4-3-4圖4-3-4圖4-3-5圖4-3-5所以，最優(yōu)路徑為A->C->D->E方法二：代價樹的深度優(yōu)先搜索（不一定是最優(yōu)解）（擴(kuò)展節(jié)點(diǎn)ｎ，將其子節(jié)點(diǎn)按代價從小到大的順序放到open表的首部（棧））步驟如下：AAC1B143圖4-4-1雖然D1的代價大于B1的代價，但按照代價樹的深度優(yōu)先搜索策略，要對D1進(jìn)行擴(kuò)展，放入closed表中（若按代價樹的廣度優(yōu)先搜索，要對B1、D1排序，先擴(kuò)展B1）4雖然D1的代價大于B1的代價，但按照代價樹的深度優(yōu)先搜索策略，要對D1進(jìn)行擴(kuò)展，放入closed表中（若按代價樹的廣度優(yōu)先搜索，要對B1、D1排序，先擴(kuò)展B1）435AC1B1D12圖4-4-24435AC1B1D18圖4-4-3934E2B2E為目標(biāo)節(jié)點(diǎn)，E2->D1->C1->A所以路徑為A->Ｃ->Ｄ->Ｅ注：該題代價樹的深度優(yōu)先搜索與代價樹的廣度優(yōu)先搜索的結(jié)果相同，但這只是巧合。一般情況下，這兩種方法得到的結(jié)果不一定相同。另外，由于代價樹的深度優(yōu)先搜索有可能進(jìn)入無窮分支的路徑，因此它是不完備的。２如下圖４-5所示，分別用代價樹的廣度優(yōu)先搜索策略和代價樹的深度優(yōu)先搜索策略，求A到E的最短費(fèi)用路徑。圖４－５圖４－５ＡＣＢＤＥ６５６７８７解：先將其化成代價樹,如圖4-6：D1D165ＡＢ1C1D2E1C2E2B2E3E466577788圖4-6(1)代價樹的廣度優(yōu)先搜索,步驟如下：AAB1C167圖圖4-7-1B1B1C167D1A511圖圖4-7-25B15B1C16D1A11D2E17781415圖圖4-7-3E為目標(biāo)節(jié)點(diǎn)，路徑為A->C->E，代價為15。（2）代價樹的深度優(yōu)先搜索,步驟如下：B1C1B1C167D1A511C2E2761817B1C167D1A511圖4-8-2圖4-8-2圖4-8-1雖然C1代價低于D1，但按照代價樹的深度優(yōu)先搜索策略，對D1進(jìn)行擴(kuò)展，放入closed表中，因?yàn)锽1擴(kuò)展的節(jié)點(diǎn)為D1，而C1是A節(jié)點(diǎn)擴(kuò)展得到的。E出棧，為目標(biāo)節(jié)點(diǎn)，結(jié)束。故解路徑為A->B->D->E,代價為17，不是最優(yōu)解。注：深度優(yōu)先搜索是不完備的，即使問題有解，也不一定能求得解。得到的解也不一定是最優(yōu)解（因?yàn)槭蔷植績?yōu)先搜索）。3下圖是五城市間的交通費(fèi)用圖，若從西安出發(fā)，要求把每個城市都訪問一遍，最后到達(dá)廣州，請找一條最優(yōu)路線。邊上的數(shù)字是兩城