管理信息化人工智能人工智能課程習(xí)題

管理信息化人工智能人工智能課程習(xí)題《人工智能》課程習(xí)題第一章緒論1-1.什么是人工智能？試從學(xué)科和能力兩方面加以說明。1-2.在人工智能的發(fā)展過程中，有哪些思想和思潮起了重要作用？1-3.為什么能夠用機(jī)器（計(jì)算機(jī)）模仿人的智能？1-4.現(xiàn)在人工智能有哪些學(xué)派？它們的認(rèn)知觀是什么？1-5.你認(rèn)為應(yīng)從哪些層次對(duì)認(rèn)知行為進(jìn)行研究？1-6.人工智能的主要研究和應(yīng)用領(lǐng)域是什么？其中，哪些是新的研究熱點(diǎn)？第二章知識(shí)表示方法2-1狀態(tài)空間法、問題歸約法、謂詞邏輯法和語義網(wǎng)絡(luò)法的要點(diǎn)是什么？它們有何本質(zhì)上的聯(lián)系及異同點(diǎn)?2-2設(shè)有3個(gè)傳教士和3個(gè)野人來到河邊，打算乘一只船從右岸渡到左岸去。該船的負(fù)載能怎樣才能用這條船安全地把所有人都渡過河去?再定義描述過河方案的謂詞：L-R(x,x1,y,y1,S)：x1個(gè)修道士和y1個(gè)野人渡船從河的左岸到河的右岸條件：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(L,S)動(dòng)作：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個(gè)修道士和y2個(gè)野人渡船從河的左岸到河的右岸條件：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(R,S)動(dòng)作：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)2-3利用圖2.3，用狀態(tài)空間法規(guī)劃一個(gè)最短的旅行路程：此旅程從城市A開始，訪問其他城市不多于一次，并返回A。選擇一個(gè)狀態(tài)表示，表示出所求得的狀態(tài)空間的節(jié)點(diǎn)及弧線，標(biāo)出適當(dāng)?shù)拇鷥r(jià)，并指明圖中從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑。2-4試說明怎樣把一棵與或解樹用來表達(dá)圖2.28RL或C可分別用RjωL或1/jωC聯(lián)阻抗的規(guī)則為基礎(chǔ)。圖2.282-5試用四元數(shù)列結(jié)構(gòu)表示四圓盤梵塔問題，并畫出求解該問題的與或圖。2-6把下列句子變換成子句形式：(1)(x)｛P(x)→P(x)｝(2)xy(On(x,y)→Above(x,y))(3)xyz(Above(x,y)∧Above(y,z)→Above(x,z))(4)～｛(x)｛P(x)→｛（yp(y)→p(f(x,y))］∧(y)［Q(x,y)→P(y)2-7用謂詞演算公式表示下列英文句子(詞字母來表示每個(gè)句子。)Aputersystemisintelligentifitcanperformataskwhich,ifperformedbyahuman,requiresintelligence.2-8把下列語句表示成語義網(wǎng)絡(luò)描述：(1)Allmanaremortal.(2)Everycloudhasasilverlining.(3)AllbranchmanagersofDECparticipateinaprofit-sharingplan.2-9作為一個(gè)電影觀眾，請你編寫一個(gè)去電影院看電影的劇本。2-10試構(gòu)造一個(gè)描述你的寢室或辦公室的框架系統(tǒng)。第三章搜索推理技術(shù)3-1什么是圖搜索過程?其中，重排OPEN表意味著什么，重排的原則是什么?3-2試舉例比較各種搜索方法的效率。3-3化為子句形有哪些步驟?請結(jié)合例子說明之。3-4如何通過消解反演求取問題的答案?3-5什么叫合適公式?合適公式有哪些等價(jià)關(guān)系?3-6用寬度優(yōu)先搜索求圖3.33所示迷宮的出路。圖3.33迷宮一例3-7用有界深度優(yōu)先搜索方法求解圖3.34所示八數(shù)碼難題。2812316384754765SoSg圖3-34八數(shù)碼難題3-86個(gè)人的解答。(Nm，Nc)來表示狀態(tài)描述，其中Nm和Nc分別為傳教士和野人的人數(shù)。初始狀態(tài)為(33)，而可能的中間狀態(tài)為(01)(02)(03)，(1，1)，(2，1)，(2，2)，(3，0)，(3，1)和(3，2)等。3-9試比較寬度優(yōu)先搜索、有界深度優(yōu)先搜索及有序搜索的搜索效率，并以實(shí)例數(shù)據(jù)加以說明。3-10一個(gè)機(jī)器人駕駛卡車，攜帶包裹(編號(hào)分別為＃1、＃2和＃3)分別投遞到林(LIN)、吳(WU)和胡(HU)3drive(x,y)和表示卸下包裹的unload(z)；對(duì)于每個(gè)操作符，都有一定的先決條件和結(jié)果。試說明個(gè)滿足AT(#1，LIN)∧AT(#2，WU)∧AT(#3,HU)和目標(biāo)狀態(tài)。3-11規(guī)則演繹系統(tǒng)和產(chǎn)生式系統(tǒng)有哪幾種推理方式?各自的特點(diǎn)為何?3-12為什么需要采用系統(tǒng)組織技術(shù)?有哪幾種系統(tǒng)組織技術(shù)?3-13研究不確定性推理有何意義?有哪幾種不確定性?3-14單調(diào)推理有何局限性?什么叫缺省推理?非單調(diào)推理系統(tǒng)如何證實(shí)一個(gè)節(jié)點(diǎn)的有效性?3-15在什么情況下需要采用不確定推理或非單調(diào)推理?3-16下列語句是一些幾何定理，把這些語句表示為基于規(guī)則的幾何證明系統(tǒng)的產(chǎn)生式規(guī)則：(1)兩個(gè)全等三角形的各對(duì)應(yīng)角相等。(2)兩個(gè)全等三角形的各對(duì)應(yīng)邊相等。(3)各對(duì)應(yīng)邊相等的三角形是全等三角形。(4)等腰三角形的兩底角相等。第四章計(jì)算智能（1）：神經(jīng)計(jì)算模糊計(jì)算4-1計(jì)算智能的含義是什么？它涉及哪些研究分支？4-2試述計(jì)算智能（CIAI）和生物智能（BI）的關(guān)系。4-3人工神經(jīng)網(wǎng)絡(luò)為什么具有誘人的發(fā)展前景和潛在的廣泛應(yīng)用領(lǐng)域？4-4簡述生物神經(jīng)元及人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)和主要學(xué)習(xí)算法。4-5考慮一個(gè)具有階梯型閾值函數(shù)的神經(jīng)網(wǎng)絡(luò)，假設(shè)（1）（1）用一常數(shù)乘所有的權(quán)值和閾值；（2）（2）用一常數(shù)加于所有權(quán)值和閾值。試說明網(wǎng)絡(luò)性能是否會(huì)變化？4-62個(gè)輸入的XOR4-7假定有個(gè)具有線性激勵(lì)函數(shù)的神經(jīng)網(wǎng)絡(luò)，即對(duì)于每個(gè)神經(jīng)元，其輸出等于常數(shù)c乘以各輸入加權(quán)和。（1WW和輸入層I為函數(shù)，而對(duì)隱含層的輸出沒有任何明顯的敘述。試證明：存在一個(gè)不含隱含單位的網(wǎng)絡(luò)能夠計(jì)算上述同樣的函數(shù)。（2）對(duì)于具有任何隱含層數(shù)的網(wǎng)絡(luò)，重復(fù)進(jìn)行上述計(jì)算。從中給出線性激勵(lì)函數(shù)的結(jié)論。4-8試實(shí)現(xiàn)一個(gè)分層前饋神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)，為正向評(píng)價(jià)和反向傳播提供所需信息。應(yīng)用4-9什么是模糊性？它的對(duì)立含義是什么？試各舉出兩個(gè)例子加以說明。4-10什么是模糊集合和隸屬函數(shù)或隸屬度？4-11模糊集合有哪些運(yùn)算，滿足哪些規(guī)律？4-12什么是模糊推理？有哪幾種模糊推理方法？4-13有哪些模糊蘊(yùn)含關(guān)系？4-14什么叫模糊判決？有哪幾種常用的模糊判決方法？4-15對(duì)某種產(chǎn)品的質(zhì)量進(jìn)行抽查評(píng)估。現(xiàn)隨機(jī)選出5個(gè)產(chǎn)品x1，x2，x3，x4，x5進(jìn)行檢驗(yàn)，它們質(zhì)量情況分別為：x1＝80，x2＝72，x3＝65，x4＝98，x5＝53這就確定了一個(gè)模糊集合Q，表示該組產(chǎn)品的“質(zhì)量水平”這個(gè)模糊概念的隸屬程度。試寫出該模糊集。4-16設(shè)有下列兩個(gè)模糊關(guān)系試求出R1與R2的復(fù)合關(guān)系R1○R2。第五章計(jì)算智能(2):進(jìn)化計(jì)算人工生命5-1什么是進(jìn)化計(jì)算？它包括哪些內(nèi)容？它們的出發(fā)點(diǎn)是什么？5-2試述遺傳算法的基本原理，并說明遺傳算法的求解步驟。5-3如何利用遺傳算法求解問題，試舉例說明求解過程。5-4用遺傳算法求的最大值5-5進(jìn)化策略是如何描述的？5-6簡述進(jìn)化編程的機(jī)理和基本過程，并以四狀態(tài)機(jī)為例說明進(jìn)化編程的表示。5-7遺傳算法、進(jìn)化策略和進(jìn)化編程的關(guān)系如何？有何區(qū)別？5-8人工生命是否從1987年開始研究？為什么？5-9什么是人工生命？請按你的理解用自己的語言給人工生命下個(gè)定義。5-10人工生命要模仿自然生命的特征和現(xiàn)象。自然生命有哪些共同特征？5-11為什么要研究人工生命？5-12人工生命包括哪些研究內(nèi)容？其研究方法如何？第六章1-1.什么是人工智能？試從學(xué)科和能力兩方面加以說明。目標(biāo)在于研究用機(jī)器來模范和執(zhí)行人腦的某些智力功能，并開發(fā)相關(guān)理論和技術(shù)。別、感知、理解、通信、設(shè)計(jì)、思考、規(guī)劃、學(xué)習(xí)和問題求解等思維活動(dòng)。1-2.在人工智能的發(fā)展過程中，有哪些思想和思潮起了重要作用？答：1)數(shù)理邏輯和關(guān)于計(jì)算本質(zhì)的新思想2、1956年第一次人工智能研討會(huì)召開3、控制論思想的影響4、計(jì)算機(jī)的發(fā)明發(fā)展5、專家系統(tǒng)和知識(shí)工程6、機(jī)器學(xué)習(xí)、計(jì)算智能、人工神經(jīng)網(wǎng)絡(luò)和行為主義研究1-3.為什么能夠用機(jī)器（計(jì)算機(jī)）模仿人的智能？66么它就能夠表現(xiàn)出智能(人類所具有的智能)。物理符號(hào)系統(tǒng)的假設(shè)伴隨有3個(gè)推論。推論一:既然人具有智能，那么他(她)就一定是個(gè)物理符號(hào)系統(tǒng)。推論二:既然計(jì)算機(jī)是一個(gè)物理符號(hào)系統(tǒng)，它就一定能夠表現(xiàn)出智能。推論三:既然人是一個(gè)物理符號(hào)系統(tǒng)，計(jì)算機(jī)也是一個(gè)物理符號(hào)系統(tǒng)，那么我們就能夠用計(jì)算機(jī)來模擬人的活動(dòng)。1-4.(下棋程序)，邏輯推理與定理證明(四色定理證明)，自然語言理解，自動(dòng)程序設(shè)計(jì)，專家系統(tǒng)，機(jī)器學(xué)習(xí)，神經(jīng)網(wǎng)絡(luò)，機(jī)器人學(xué)(星際探索機(jī)器人)，模式識(shí)別(手寫識(shí)別，汽車牌照識(shí)別，指紋識(shí)別)，機(jī)器視覺(機(jī)器裝配，衛(wèi)星圖像處理)，智能控制，智能檢索，智能調(diào)度與指揮(汽車運(yùn)輸高度，列車編組指揮)，系統(tǒng)與語言工具。新的研究熱點(diǎn)：概率圖模型（隱馬爾可夫模型、貝葉斯網(wǎng)絡(luò)）、統(tǒng)計(jì)學(xué)習(xí)理論(SLT)&支持向量機(jī)(SVM)、數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(超市市場商品數(shù)據(jù)分析)，人工生命1-5.人工智能有哪幾種學(xué)派?答：1）符號(hào)主義(Symbolicism)，又稱為邏輯主義(Logicism)、心理學(xué)派(Psychlogism)或計(jì)算機(jī)學(xué)派(Computerism)[其原理主要為物理符號(hào)系統(tǒng)(即符號(hào)操作系統(tǒng))假設(shè)和有限合理性原理。]2）連接主義(Connectionism)，又稱為仿生學(xué)派(Bionicsism)或生理學(xué)派(Physiologism)[其原理主要為神經(jīng)網(wǎng)絡(luò)及神經(jīng)網(wǎng)絡(luò)間的連接機(jī)制與學(xué)習(xí)算法]3）行為主義(Actionism)，又稱進(jìn)化主義(Evolutionism)或控制論學(xué)派(Cyberneticsism)[其原理為控制論及感知-動(dòng)作型控制系統(tǒng)]1-6、人工智能有哪幾個(gè)研究領(lǐng)域？能檢索；智能調(diào)度與指揮；知識(shí)表示；非經(jīng)典邏輯&非經(jīng)典推理；搜索技術(shù)；機(jī)器學(xué)習(xí)；自然語言理解；知識(shí)工程；定理機(jī)器證明；計(jì)算視覺；遺傳算法&進(jìn)化計(jì)算；分布式AI；數(shù)據(jù)挖掘&知識(shí)發(fā)現(xiàn)；人工生命；機(jī)器人；AI語言2-1知識(shí)表示的方法有哪些？答案：狀態(tài)空間法、問題歸約法、謂詞邏輯法、語義網(wǎng)絡(luò)法、框架表示法。2-2狀態(tài)空間法、問題歸約法、謂詞邏輯法和語義網(wǎng)絡(luò)法的要點(diǎn)是什么？它們有何本質(zhì)上的聯(lián)系及異同點(diǎn)?

答案：狀態(tài)空間法是基于解答空間的問題表示和求解方法,是以狀態(tài)和操作符為基礎(chǔ)的。需要擴(kuò)展過多的節(jié)

點(diǎn)，容易出現(xiàn)“組合爆炸”，因而只適用于表示比較簡單的問題。問題歸約法是從目標(biāo)(要解決的問題)歸約為一個(gè)平凡的本原問題集合。狀態(tài)空間法是問題歸納法的一種特例。這些本原問題的解可以直接得到，從而解決了初始問題，用與或圖來有效地說明問題歸約法的求解途徑。謂語邏輯法是采用謂詞合式公式和一階謂詞演算把要解決的問題變?yōu)橐粋€(gè)有待證明的問題,然后采用消解定理和消解反演來證明一個(gè)新語句是從已知的正確語句導(dǎo)出的,從而證明這個(gè)新語句也是正確的語義網(wǎng)絡(luò)法是用“節(jié)點(diǎn)代替概念，用節(jié)點(diǎn)間的“連接弧代替概念之間的關(guān)系。語義網(wǎng)絡(luò)表示法的優(yōu)點(diǎn)：結(jié)構(gòu)性、聯(lián)想性、自然性。知識(shí)表示法的比較方法初始問題算符目標(biāo)結(jié)果狀態(tài)空間法狀態(tài)算符目標(biāo)狀態(tài)解答路徑（path）規(guī)約法結(jié)點(diǎn)弧結(jié)點(diǎn)解答樹（tree）子句集謂詞邏輯法合式公式（setofclause）根結(jié)點(diǎn)nil置換合一消解反演語義網(wǎng)絡(luò)法結(jié)點(diǎn)鏈目標(biāo)網(wǎng)絡(luò)語義網(wǎng)絡(luò)2-6如何通過消解反演樹求取問題的答案?答1.把由目標(biāo)公式的否定產(chǎn)生的每個(gè)子句添加到目標(biāo)公式否定之否定的子句中去。2.按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個(gè)子句為止。3.用根部的字句作為一個(gè)回答語句。2-7規(guī)則演繹系統(tǒng)和產(chǎn)生式系統(tǒng)有哪幾種推理方式?各自的特點(diǎn)為何?簡述各自的的使用條件答案：1.規(guī)則演繹系統(tǒng)和產(chǎn)生式系統(tǒng)均有三種推理方式：正向推理、逆向推理、雙向推理2.規(guī)則演繹系統(tǒng)的正向推理是從事實(shí)或狀況向目標(biāo)或動(dòng)作進(jìn)行操作（即：從IF到THEN實(shí)或狀況進(jìn)行操作的(THEN到IF)F規(guī)則和逆向系統(tǒng)的B規(guī)則來修正。產(chǎn)生式系統(tǒng)的正向推理(正向鏈接推理)明該謂詞公式或命題是否成立。逆向推理(后向鏈接推理)：從表示目標(biāo)的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則證明事實(shí)謂詞或命題成立，即首先提出一批假設(shè)目標(biāo)，然后逐一驗(yàn)證這些假設(shè)。(其基本原理是從表示目標(biāo)的謂詞或命題出發(fā)，使用一組規(guī)則證明事實(shí)謂詞或命題成立，即提出一批假設(shè)(目標(biāo))，然后逐一驗(yàn)證這些假設(shè)。)配。2-8產(chǎn)生式系統(tǒng)由哪些部分組成？什么是產(chǎn)生式規(guī)則？答1.綜合數(shù)據(jù)庫(或全局?jǐn)?shù)據(jù)庫)、產(chǎn)生式規(guī)則庫和控制系統(tǒng)。產(chǎn)生式規(guī)則是一個(gè)規(guī)則庫，用于存放與求“取某些操作”形式表示的語句，其基本形式為：IF前提THEN結(jié)論.3-1什么是不確定推理？不確定性推理的基本問題是什么？出發(fā)，通過運(yùn)用不確定性知識(shí)，推出具有一定程度的不確定性的和合理的或近乎合理的結(jié)論?；締栴}是：不確定性的表示與度量，不確定性的匹配，不確定性的傳遞算法，不確定性的合成。3-2在什么情況下需要采用不確定推理?不確定推理的主要方法有哪些？答案：1、一般推理方法在許多情況下，往往無法解決面臨的現(xiàn)實(shí)問題，因而需要應(yīng)用不確定性推理等高級(jí)2.不確定性推理大類別上分為模型方法和控制方法。模型方法下有數(shù)值方法和非數(shù)值方法；數(shù)值方法包括概率統(tǒng)計(jì)方法、模糊推理方法、粗糙集方法;概率統(tǒng)計(jì)方法下細(xì)分為絕對(duì)概率方法、貝葉斯方法、證據(jù)理論方法、HMM又包括發(fā)生率計(jì)算?？刂品椒ㄏ掠校合嚓P(guān)性制導(dǎo)回溯、機(jī)緣控制、啟發(fā)式搜索等3-3主觀Bayes方法中LN和LS的意義是什么？答：LN表示必要性因子，它表示~E對(duì)Ｈ的支持程度。LS表示充分性因子，它表示E對(duì)H的支持程度。4-1．計(jì)算智能的含義是什么？答：計(jì)算智能取決于制造者（manufacturers）提供的數(shù)值數(shù)據(jù)，不依賴于知識(shí)；另一方面，人工智能應(yīng)用知識(shí)精品（knowledgetidbits）。人工神經(jīng)網(wǎng)絡(luò)應(yīng)當(dāng)稱為計(jì)算神經(jīng)網(wǎng)絡(luò)。（1）計(jì)算適應(yīng)性；（2）計(jì)算容錯(cuò)性；（3）接近人的速度；（4）誤差率與人相近，則該系統(tǒng)就是計(jì)算智能系統(tǒng)。4-2.簡述生物神經(jīng)元及人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu).連接權(quán)系數(shù)。4-4．什么是模糊集合和隸屬函數(shù)或隸屬度？論域U到[0,1]區(qū)間的任一映射，即，都確定U的一個(gè)模糊子集FF的隸屬函數(shù)或隸屬度。在論域U中，可把模糊子集表示為元素u與其隸屬函數(shù)的序偶集合，記為：4-5．什么是模糊推理？有哪幾種模糊推理方法？1.它以模糊判斷為前提，動(dòng)用模糊語言規(guī)則，推導(dǎo)出一個(gè)近似的模糊判斷結(jié)論。2．推理方法有Zadeh法，Baldwin法、Tsukamoto法、Yager法和Mizumoto法等方法。4-6.說明粗糙集理論的基本概念和特點(diǎn)。1.描述并處理“含糊”信息。2.特點(diǎn)是：1）粗糙集部需要先驗(yàn)知識(shí)。2）粗糙集理論是強(qiáng)大的數(shù)據(jù)分析工具。3）粗糙集和模糊集描述了調(diào)集合本身的含混性。4-7.如何求集合的上近似和下近似？（見課件）4-8.什么是人工生命？在計(jì)算機(jī)學(xué)科中如何定義人工生命？1.人工生命即人造的生命，非自然地生命。人工生命是研究能夠演示出自然生命系統(tǒng)特征行為的人造系統(tǒng)。

2如數(shù)字生命、數(shù)字生態(tài)系統(tǒng)、人工腦、虛擬生物等。4-9.說明人工生命的研究意義、研究內(nèi)容和研究方法。意義為：1.開發(fā)基于人工生命的工程技術(shù)新方法、新系統(tǒng)、新產(chǎn)品。2.為自然生命的研究提供新模型、新工具、新環(huán)境。3.延長人類壽命、減少衰弱、防治疾病。4.擴(kuò)展自然生命，實(shí)現(xiàn)人工進(jìn)化和優(yōu)生優(yōu)育。5促進(jìn)生命科學(xué)、信息科學(xué)、系統(tǒng)科學(xué)的交叉于發(fā)展。研究內(nèi)容為：1）構(gòu)造生物體的內(nèi)部系統(tǒng)。2）生物體及其群體的外部系統(tǒng)?？茖W(xué)框架由下列主要內(nèi)容構(gòu)成：1.生命現(xiàn)象仿生系統(tǒng)。2345化機(jī)器人。6）進(jìn)化和學(xué)習(xí)等方面的結(jié)合。7）人工生命的應(yīng)用。研究方法主要分兩類：1）信息模型法。2）工作原理法。研究技術(shù)途徑分兩種：1）工程技術(shù)途徑。2）生物科學(xué)途徑。

5-1什么是機(jī)器學(xué)習(xí)?為什么要研究機(jī)器學(xué)習(xí)?1）機(jī)器學(xué)習(xí)是研究如何使用機(jī)器來模擬人類學(xué)習(xí)活動(dòng)的一門學(xué)科。即：機(jī)器學(xué)習(xí)是一門研究機(jī)器獲取新知識(shí)和新技能，并識(shí)別現(xiàn)有知識(shí)的學(xué)問。2）機(jī)器學(xué)習(xí)是人工智能的主要核心研究領(lǐng)域之一,也是現(xiàn)代智能系統(tǒng)的關(guān)鍵環(huán)節(jié)和瓶頸。

很難想象:一個(gè)沒有學(xué)習(xí)功能的系統(tǒng)能被稱具有智能的系統(tǒng)。

來自生物、金融與網(wǎng)絡(luò)等各領(lǐng)域的數(shù)據(jù)，迫切需要分析或建立模型。

5-2試述機(jī)器學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)，并說明各部分的作用。（見書本）

執(zhí)行知識(shí)庫學(xué)習(xí)環(huán)境效能，執(zhí)行部分根據(jù)知識(shí)庫完成任務(wù)，同時(shí)把獲得的信息反饋給學(xué)習(xí)部分。5-3試說明歸納學(xué)習(xí)的模式和學(xué)習(xí)方法。歸納學(xué)習(xí)的一般模式為：給1(事實(shí))F,2)假定的初始?xì)w納斷言（可能為空）；3）背景知識(shí)，用于定義有關(guān)觀察陳述、候選納斷言以及任何相關(guān)問題領(lǐng)域知識(shí)、假設(shè)和約束，其中包括能夠刻畫所求歸納斷言的性質(zhì)的優(yōu)先準(zhǔn)則。求：歸納斷言（假設(shè)）H,能重言蘊(yùn)涵或弱蘊(yùn)涵觀察陳述，并滿足背景知識(shí)。假設(shè)H永真蘊(yùn)涵事實(shí)F,說明F是H的邏輯推理，則有：HI>F(讀作H特殊化為F)或者FI<H（讀作F一般化或消解為H）這里，從H推導(dǎo)到F時(shí)演繹推理，因此是保真的；而從事實(shí)F推導(dǎo)出假設(shè)H是歸納推理，因此不是保真的，而是保假的。專家系統(tǒng)6-1什么叫做專家系統(tǒng)?它具有哪些特點(diǎn)與優(yōu)點(diǎn)?6-2專家系統(tǒng)由哪些部分構(gòu)成?各部分的作用為何?6-3建造專家系統(tǒng)的關(guān)鍵步驟是什么?6-4專家系統(tǒng)程序與一般的問題求解軟件程序有何不同?開發(fā)專家系統(tǒng)與開發(fā)其它軟件的任務(wù)有何不同?6-5基于規(guī)則的專家系統(tǒng)是如何工作的？其結(jié)構(gòu)為何？6-6基于框架的專家系統(tǒng)與面向目標(biāo)編程有何關(guān)系？其結(jié)構(gòu)有何特點(diǎn)？其設(shè)計(jì)任務(wù)是什么？6-7為什么要提出基于模型的專家系統(tǒng)？試述神經(jīng)網(wǎng)絡(luò)專家系統(tǒng)的一般結(jié)構(gòu)。6-8新型專家系統(tǒng)有何特征？什么是分布式專家系統(tǒng)和協(xié)同式專家系統(tǒng)？6-9在設(shè)計(jì)專家系統(tǒng)時(shí)，應(yīng)考慮哪些技術(shù)？6-10什么是建造專家系統(tǒng)的工具?你知道哪些專家系統(tǒng)工具，各有什么特點(diǎn)?6-11專家系統(tǒng)面臨什么問題?你認(rèn)為應(yīng)如何發(fā)展專家系統(tǒng)?6-12用基于規(guī)則的推理系統(tǒng)證明下述推理的正確性：已知狗都會(huì)吠叫和咬人任何動(dòng)物吠叫時(shí)總是吵人的獵犬是狗結(jié)論獵犬是吵人的第七章機(jī)器學(xué)習(xí)7-1什么是學(xué)習(xí)和機(jī)器學(xué)習(xí)?為什么要研究機(jī)器學(xué)習(xí)?7-2試述機(jī)器學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)，并說明各部分的作用。7-3試解釋機(jī)械學(xué)習(xí)的模式。機(jī)械學(xué)習(xí)有哪些重要問題需要加以研究?7-4試說明歸納學(xué)習(xí)的模式和學(xué)習(xí)方法。7-5什么是類比學(xué)習(xí)？其推理和學(xué)習(xí)過程為何？7-6試述解釋學(xué)習(xí)的基本原理、學(xué)習(xí)形式和功能。7-7試比較說明符號(hào)系統(tǒng)和連接機(jī)制在機(jī)器學(xué)習(xí)中的主要思想。7-8用C語言編寫一套計(jì)算機(jī)程序，用于執(zhí)行BP學(xué)習(xí)算法。7-9試應(yīng)用神經(jīng)網(wǎng)絡(luò)模型優(yōu)化求解銷售員旅行問題。7-10考慮一個(gè)具有階梯型閾值函數(shù)的神經(jīng)網(wǎng)絡(luò)，假設(shè)(1)用一常數(shù)乘所有的權(quán)值和閾值；(2)用一常數(shù)加于所有權(quán)值和閾值。試說明網(wǎng)絡(luò)性能是否會(huì)變化?7-11增大權(quán)值是否能夠使BP學(xué)習(xí)變慢?7-12什么是知識(shí)發(fā)現(xiàn)？知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘有何關(guān)系？7-13試說明知識(shí)發(fā)現(xiàn)的處理過程。7-14有哪幾種比較常用的知識(shí)發(fā)現(xiàn)方法？試略加介紹。7-15知識(shí)發(fā)現(xiàn)的應(yīng)用領(lǐng)域有哪些？試展望知識(shí)發(fā)現(xiàn)的發(fā)展和應(yīng)用前景。第八章機(jī)器人規(guī)劃8-1有哪幾種重要的機(jī)器人高層規(guī)劃系統(tǒng)?它們各有什么特點(diǎn)?你認(rèn)為哪種規(guī)劃方法有較大的發(fā)展前景?8-2讓right(x),left(x),up(x)和down(x)分別表示八數(shù)碼難題中單元x左邊、右邊、上面和下面的單元(如果這樣的單元存在的話)。試寫出STIPS規(guī)劃來模擬向上移動(dòng)B(空格)、向下移動(dòng)B、向左移動(dòng)B和向右移動(dòng)B等動(dòng)作。8-3考慮設(shè)計(jì)一個(gè)清掃廚房規(guī)劃問題。(1)寫出一套可能要用的STRIPS·清掃火爐或電冰箱會(huì)弄臟地板?！ひ鍜吆嫦洌仨殤?yīng)用烘箱清洗器，然后搬走此清洗器?！ぴ谇鍜叩匕逯?，必須先行打掃?！ぴ诖驋叩匕逯?，必須先把垃圾筒拿出去。·清掃電冰箱造成垃圾污物，并把工作臺(tái)弄臟。·清洗工作臺(tái)或地板使洗滌盤弄臟。(2)(但很可能難以得到的)目標(biāo)描述。(3)說明如何把STRIPS規(guī)劃技術(shù)用來求解這個(gè)問題。(提示：你可能想修正添加條件的定義，以便當(dāng)某個(gè)條件添加至數(shù)據(jù)庫時(shí)，如果出現(xiàn)它的否定的話，就能自動(dòng)刪去此否定)。8-4曲頸瓶F1和F2的容積分別為C1和C2。公式CONT(X，Y)表示瓶子X含有Y容量單位的液體。試寫出STRIPS規(guī)劃來模擬下列動(dòng)作：(1)把F1內(nèi)的全部液體倒進(jìn)F2內(nèi)。(2)用F1的部分液體把F2裝滿。8-5機(jī)器人Rover正在房外，想進(jìn)入房內(nèi)，但不能開門讓自已進(jìn)去，而只能喊叫，讓叫聲促M(fèi)axMax通常可以把門打開來使RoverMax和Rover各有一個(gè)STRIPS規(guī)劃生成系統(tǒng)和規(guī)劃執(zhí)行系統(tǒng)。試說明Max和Rover的STRIPS驟。8-6用本章討論過的任何規(guī)劃生成系統(tǒng)，解決圖8.22所示機(jī)械手堆積木問題。8-7考慮圖8.23所示的尋找路徑問題。(1)對(duì)所示物體和障礙物(陰影部分)建立一個(gè)結(jié)構(gòu)空間。其中，物體的初始位置有兩種情況，一種如圖所示，另一種情況是把物體旋轉(zhuǎn)90°。(2)應(yīng)用結(jié)構(gòu)空間，描述一個(gè)尋求上述無碰撞路徑的過程(程序)把問題限于無旋轉(zhuǎn)的二維問題。(a)初始布局(b)目標(biāo)布局圖8.22機(jī)械手堆積木規(guī)劃問題8-8指出你的過程結(jié)構(gòu)空間求得的圖8.23中所得結(jié)論推廣至包括旋轉(zhuǎn)情況。圖8.23一個(gè)尋找路徑問題8-9圖8.24Robot把3個(gè)箱子BOX1BOX2和BOX3移到如圖E23(b)所示目標(biāo)位置，試用專家系統(tǒng)方法建立本規(guī)劃，并給出規(guī)劃序列。(a)初始世界模型M0(b)目標(biāo)世界模型G0圖8.24移動(dòng)箱子于一處的機(jī)器人規(guī)劃8-10圖8.25表示機(jī)器人工作的世界模型。要求機(jī)器人把箱子從房間R2初始位置移至房間R1目標(biāo)位置。試建立本機(jī)器人規(guī)劃專家系統(tǒng)，并給出規(guī)劃結(jié)果。圖8.25從一房間移至另一房間的機(jī)器人規(guī)劃第九章Agent(艾真體)9-1分布式人工智能系統(tǒng)有何特點(diǎn)？試與多艾真體系統(tǒng)的特性加以比較。9-2什么是艾真體？你對(duì)agent的譯法有何見解？9-3艾真體在結(jié)構(gòu)上有何特點(diǎn)？在結(jié)構(gòu)上又是如何分類的？每種結(jié)構(gòu)的特點(diǎn)為何？9-4艾真體為什么需要互相通信？9-5試述艾真體通信的步驟、類型和方式。9-6艾真體有哪幾種主要通信語言？它們各有什么特點(diǎn)？9-7多艾真體系統(tǒng)有哪幾種基本模型？其體系結(jié)構(gòu)又有哪幾種？9-8試說明多艾真體的協(xié)作方法、協(xié)商技術(shù)和協(xié)調(diào)方式。9-9為什么多艾真體需要學(xué)習(xí)與規(guī)劃？9-10你認(rèn)為多艾真體系統(tǒng)的研究方向應(yīng)是哪些？其應(yīng)用前景又如何？9-11好？9-12如何接近理想的艾真體？9-13改善其性能，以求處理更為復(fù)雜的地貌。9-14才進(jìn)行推理。這兩種推理方法在知識(shí)層、邏輯層和執(zhí)行層將有何區(qū)別？9-15和輸出（行動(dòng)閥門）的邏輯門的集合。(1)試解釋為什么需要觸發(fā)器。(2)估計(jì)需要多少邏輯門和觸發(fā)器。第十章機(jī)器視覺10-1可用廣義錐體語言把楔形物體描述為一個(gè)具有一定尺寸的三角形沿著一根直軸移動(dòng)而成的。請給出另一種描述。10-2(1)除了表面法線(p,q,-1)外，還有另外兩個(gè)感興趣的矢量：一個(gè)矢量指向光源，它對(duì)應(yīng)于某些特別的p和q值，記為ps和(s為假設(shè)日光)，表示指向日光的矢量(ps，qs，-1)；另一指向觀察者，即矢量(0，0，-1)。p和q位角有關(guān)的公式。試證明下列公式成立：(2)對(duì)和推導(dǎo)類似公式。10-3p和q的亮度為：當(dāng)為一常數(shù)時(shí)，亮度E為一恒值。由于是平面PQ上某個(gè)圓的方程式，所以我們可得如下結(jié)PQ10-4觀察者的背后。(1)球面的光線亮度如何變化?(2)為什么滿月看上去是扁平的?10-5aab線的光線強(qiáng)度大體上像圖（b）那樣，而當(dāng)立方體的拐角為圓滑過渡時(shí)，其光線強(qiáng)度如圖(c)所示。題10－5圖朗伯立方體及其光強(qiáng)分布圖(1)在PQ空間，指出此立方體各可見側(cè)面的表面法線的準(zhǔn)確位置。(2)在PQ空間，對(duì)著光源方向，指出可取的位置。(3)假設(shè)交界是陡變的，試畫出沿cd線的光強(qiáng)度分布圖。(4)假設(shè)交界是圓滑的，試畫出沿cd線的光強(qiáng)度分布圖。10-6下列陣列表示航空照片圖象上點(diǎn)陣的PQ投影以及所觀察亮度Er的鏈?zhǔn)酱a：-1-10.23+1-10.23+1-10.17-1-10.23+1-10.17000.3000.3000.3000.3度線。試把每點(diǎn)圖象分類為石頭、樹和墓石、假設(shè)它們的反射系數(shù)分別為0.7，0.5和0.3。

10-73面，這3個(gè)光源對(duì)此表面的反射圖如圖所示。用這些光分別照射時(shí)所觀察到的亮度分別為：

題10-7圖3個(gè)反射圖(1)在PQ空間畫出當(dāng)?shù)扔?3和40.51和2時(shí)的線。(2)求10-8把圖中所示各物體量化為32×32的畫面(方格紙自備)題10－8圖需要數(shù)字化的物體(1)建立兩個(gè)畫面，每個(gè)畫面包含上述3個(gè)物體。要求兩畫面上的物體具有不同的尺寸、位置和方向。(2)計(jì)算兩畫面上6個(gè)物體的各階矩量和。

(3)計(jì)算各物體的矩心。(4)計(jì)算各物體的中心矩、標(biāo)稱中心矩和不變性矩，并討論所得結(jié)果。(5)計(jì)算6個(gè)物體的形狀系數(shù)，并討論所得結(jié)果。10-9為什么CONSIGHT系統(tǒng)要使用2個(gè)光源，而不是用1個(gè)光源?10-10在連通性分析中，相鄰2行間的分段情況被定義為下列3種：情況1不重迭中間為零或有更多的列××××××××××情況2不重迭中間為零或有更多的列××××××××××情況3重迭既不同于情況1，又不同于情況2。區(qū)域并合規(guī)則是較高的數(shù)取代較低的數(shù)(除背景“0”外)。(1)從左至右逐行掃描下列8×8二進(jìn)制圖象(圖中b為背景)。指出連通域被并合后圖象矩陣上元素的數(shù)字，作為連通性分析的解答：8bbbbbbbbbb1b0b

2b0b

3b1b

4b1b

5b1b

6b1b7b0b8b0bbbbbbbbbb(2)確定本題(1)中圖象編碼的掃描寬度。第十一章自然語言理解11-1什么是語言和語言理解?自然語言理解過程有哪些層次，各層次的功能如何?11-2自然語言理解和語言自動(dòng)生成的關(guān)系為何?研究這兩者時(shí)有什么共同點(diǎn)。11-3語言的歧義性可出現(xiàn)在各個(gè)層次上：構(gòu)詞、詞類、句法和語義。試各舉一例來說明。11-4寫出下列上下文無關(guān)語法所對(duì)應(yīng)的轉(zhuǎn)移網(wǎng)絡(luò)：S→NPVPNP→AdjectiveNounNP→DeterminerNounPPNP→DeterminerNounVP→VerbAdverbNPVP→VerbVP→VerbAdverbVP→VerbPPPP→PropositionNP11-5考慮下列句子Theoldman′sglasseswerefilledwithsherry.選擇單詞glasses合適的意思需要什么信息?什么信息意味著不合適的意思?11-6考慮下列句子：Puttheredblockontheblueblockonthetable.

(1)寫出句中符合句法規(guī)則的所有有效的句法分析。

(2)如何用語義信息和環(huán)境知識(shí)選擇該命令的恰當(dāng)含義?

11-7對(duì)下列每個(gè)語句給出句法分析樹：(1)DavidwantedtogotothemoviewithLinda.(2)DavidwantedtogotothemoviewithGeorgyWilliam.

(3)Heheardthestorylisteningtotheradio.(4)Heheardtheboyslisteningtotheradio.11-8考慮一用戶與一交互操作系統(tǒng)之間進(jìn)行英語對(duì)話的問題。

(1)復(fù)制和刪除文件、編譯程序和檢索文件目錄等。(2)用你的語義文法對(duì)下列各語句進(jìn)行文法分析：Copyfromnewtestmssintooldtestmss.Copytooldtestmssoutofnewtestmss.(3)用標(biāo)準(zhǔn)的英語文法對(duì)上述兩語句進(jìn)行分析，列出所用文法片斷。(4)上述(2)與(3)的文法有何差別?這種差別與句法和語義文法之間的差別有何關(guān)系?11-9本。11-10試設(shè)計(jì)一個(gè)特定應(yīng)用領(lǐng)域的自然語言問答系統(tǒng)。第十二章智能控制12-1為什么說智能控制是人工智能的重要研究新領(lǐng)域?12-2智能控制有哪幾種結(jié)構(gòu)理論?它們的中心思想和內(nèi)容是什么?有什么特點(diǎn)?12-3Saridis的分級(jí)遞階智能控制的要點(diǎn)是什么?各級(jí)的功能怎樣?如何用熵來度量各級(jí)的作用?12-4設(shè)計(jì)專家控制器時(shí)應(yīng)考慮哪些特點(diǎn)?專家控制系統(tǒng)的一般結(jié)構(gòu)模型為何?12-5什么是學(xué)習(xí)控制系統(tǒng)?它有哪些研究課題?學(xué)習(xí)控制系統(tǒng)的設(shè)計(jì)原則為何?12-6試說明模糊控制器的結(jié)構(gòu)原理和控制規(guī)則。模糊控制器有哪幾種設(shè)計(jì)方法?12-7設(shè)論域X、Y均為有限模糊集合，它們分別為模糊矩陣R表示從X到Y(jié)的一個(gè)模糊關(guān)系。試說明模糊矩陣R的元素rij的含義是什么?12-8模糊控制器工作過程中把輸入的精確量轉(zhuǎn)變?yōu)槟：?模糊化)后，輸出時(shí)又把模糊量變?yōu)榫_量(非模糊化)。這些轉(zhuǎn)換各有什么作用?12-9人工神經(jīng)網(wǎng)絡(luò)有哪些特性使它適于控制?有哪幾種神經(jīng)控制器，它們的結(jié)構(gòu)和作用原理為何?12-10智能控制有哪些應(yīng)用領(lǐng)域?其工作原理和控制性能。第十三章展望13-1你怎樣評(píng)價(jià)人工智能的發(fā)展與爭論？爭論與發(fā)展的關(guān)系如何？13-2人工智能不同學(xué)派在理論、方法和技術(shù)路線上各有何爭論?13-2會(huì)何文化等方面加以說明？13-4試評(píng)述人工智能的未來發(fā)展。13-5你對(duì)“人工智能”或“智能系統(tǒng)”課程及其教學(xué)有何建議？一部分基本搜索算法一、回溯算法回溯算法是所有搜索算法中最為基本的一種算法，其采用了一種“走不通就掉頭”思想作為其控制結(jié)構(gòu)，其相遍歷的方法來構(gòu)造解答樹，可用于找解或所有解以及最優(yōu)解。具體的算法描述如下：[非遞歸算法]＜Type＞Node(節(jié)點(diǎn)類型)＝RecordSitutation:TSituation（當(dāng)前節(jié)點(diǎn)狀態(tài)）;Way-NO:Integer（已使用過的擴(kuò)展規(guī)則的數(shù)目）;End＜Var＞List(回溯表):Array[1..Max(最大深度)]ofNode;pos(當(dāng)前擴(kuò)展節(jié)點(diǎn)編號(hào)):Integer;＜Init＞List＜-0;pos＜-1;List[1].Situation＜-初始狀態(tài);＜MainProgram＞W(wǎng)hile(pos＞0(有路可走))and([未達(dá)到目標(biāo)])doBeginIfpos＞=Maxthen(數(shù)據(jù)溢出,跳出主程序);List[pos].Way-NO:=List[pos].Way-No+1;If(List[pos].Way-NO＜=TotalExpendMethod)then(如果還有沒用過的擴(kuò)展規(guī)則)BeginIf(可以使用當(dāng)前擴(kuò)展規(guī)則)thenBegin(用第way條規(guī)則擴(kuò)展當(dāng)前節(jié)點(diǎn))List[pos+1].Situation:=ExpendNode(List[pos].Situation,List[pos].Way-NO);List[pos+1].Way-NO:=0;

pos:=pos+1;End-If;End-IfElseBeginpos:=pos-1;End-ElseEnd-While;[遞歸算法]ProcedureBackTrack(Situation:TSituation;deepth:Integer);VarI:Integer;BeginIfdeepth＞Maxthen(空間達(dá)到極限,跳出本過程);IfSituation=Targetthen(找到目標(biāo));ForI:=1toTotalExpendMethoddoBeginBackTrack(ExpendNode(Situation,I),deepth+1);End-For;End;范例：一個(gè)M*M的棋盤上某一點(diǎn)上有一個(gè)馬，要求尋找一條從這一點(diǎn)出發(fā)不重復(fù)的跳完棋盤上所有的點(diǎn)的路線。評(píng)價(jià)：回溯算法對(duì)空間的消耗較少，當(dāng)其與分枝定界法一起使用時(shí)，對(duì)于所求解在解答樹中層次較深的問題有應(yīng)避免在后繼節(jié)點(diǎn)可能與前繼節(jié)點(diǎn)相同的問題中使用，以免產(chǎn)生循環(huán)。二、深度搜索與廣度搜索深度搜索與廣度搜索的控制結(jié)構(gòu)和產(chǎn)生系統(tǒng)很相似，唯一的區(qū)別在于對(duì)擴(kuò)展節(jié)點(diǎn)選取上。由于其保留了所有的在產(chǎn)生后繼節(jié)點(diǎn)時(shí)可以去掉一部分重復(fù)的節(jié)點(diǎn)，從而提高了搜索效率。這兩種算法每次都擴(kuò)展一個(gè)節(jié)點(diǎn)的所有的是，深度搜索下一次擴(kuò)展的是本次擴(kuò)展出來的子節(jié)點(diǎn)中的一個(gè)，而廣度搜索擴(kuò)展的則是本次擴(kuò)展的節(jié)點(diǎn)的兄實(shí)現(xiàn)上為了提高效率,所以采用了不同的數(shù)據(jù)結(jié)構(gòu).[廣度搜索]＜Type＞Node(節(jié)點(diǎn)類型)＝RecordSitutation:TSituation（當(dāng)前節(jié)點(diǎn)狀態(tài)）;Level:Integer(當(dāng)前節(jié)點(diǎn)深度);Last:Integer(父節(jié)點(diǎn));End＜Var＞List(節(jié)點(diǎn)表):Array[1..Max(最多節(jié)點(diǎn)數(shù))]ofNode(節(jié)點(diǎn)類型);open(總節(jié)點(diǎn)數(shù)):Integer;close(待擴(kuò)展節(jié)點(diǎn)編號(hào)):Integer;New-S:TSituation;(新節(jié)點(diǎn))＜Init＞List＜-0;open＜-1;close＜-0;List[1].Situation＜-初始狀態(tài);List[1].Level:=1;List[1].Last:=0;＜MainProgram＞W(wǎng)hile(close＜o(jì)pen(還有未擴(kuò)展節(jié)點(diǎn)))and(open＜Max(空間未用完))and(未找到目標(biāo)節(jié)點(diǎn))doBeginclose:=close+1;ForI:=1toTotalExpendMethoddo（擴(kuò)展一層子節(jié)點(diǎn)）BeginNew-S:=ExpendNode(List[close].Situation,I);IfNot(New-SinList)then(擴(kuò)展出的節(jié)點(diǎn)從未出現(xiàn)過)Beginopen:=open+1;List[open].Situation:=New-S;List[open].Level:=List[close].Level+1;List[open].Last:=close;End-IfEnd-For;End-While;[深度搜索]＜Var＞Open:Array[1..Max]ofNode;(待擴(kuò)展節(jié)點(diǎn)表)

Close:Array[1..Max]ofNode;(已擴(kuò)展節(jié)點(diǎn)表)openL,closeL:Integer;(表的長度)New-S:Tsituation;(新狀態(tài))＜Init＞Open＜-0;Close＜-0;OpenL＜-1;CloseL＜-0;Open[1].Situation＜-初始狀態(tài);Open[1].Level＜-1;Open[1].Last＜-0;＜MainProgram＞W(wǎng)hile(openL＞0)and(closeL＜Max)and(openL＜Max)doBegincloseL:=closeL+1;Close[closeL]:=Open[openL];openL:=openL-1;ForI:=1toTotalExpendMethoddo（擴(kuò)展一層子節(jié)點(diǎn)）BeginNew-S:=ExpendNode(Close[closeL].Situation,I);IfNot(New-SinList)then(擴(kuò)展出的節(jié)點(diǎn)從未出現(xiàn)過)BeginopenL:=openL+1;Open[openL].Situation:=New-S;Open[openL].Level:=Close[closeL].Level+1;Open[openL].Last:=closeL;End-IfEnd-For;End;范例：迷宮問題，求解最短路徑和可通路徑。評(píng)價(jià)：廣度搜索是求解最優(yōu)解的一種較好的方法，在后面將會(huì)對(duì)其進(jìn)行進(jìn)一步的優(yōu)化。而深度搜索多用于只要樹中的重復(fù)節(jié)點(diǎn)較多并且重復(fù)較難判斷時(shí)使用，但往往可以用A*或回溯算法代替。2006-4-2117:35回復(fù)3樓dapplehou第二部分搜索算法的優(yōu)化1位粉絲一、雙向廣度搜索廣度搜索雖然可以得到最優(yōu)解理想情況下可以減少二分之一高搜索速度。N個(gè)黑白棋子排成一求出入長度為length的一個(gè)

標(biāo)狀態(tài)，求出最少的轉(zhuǎn)化步數(shù)

如果從初始狀態(tài)和目標(biāo)狀態(tài)

合，則該節(jié)點(diǎn)所連接的兩條路徑所拼成的路

對(duì)廣度搜索算法的改進(jìn)：

1、添加一張節(jié)點(diǎn)表，作為反

2、在while循環(huán)體中在正向

個(gè)for循環(huán)。3、在正向擴(kuò)展出一個(gè)節(jié)點(diǎn)后

找是否有重合節(jié)點(diǎn)。反向擴(kuò)展

對(duì)雙向廣度搜索算法的改進(jìn)：

展正反兩個(gè)方向中節(jié)點(diǎn)數(shù)目較

兩邊的發(fā)展速度保持一定的平

展節(jié)點(diǎn)的個(gè)數(shù)，加快搜索速度

二、分支定界分支定界實(shí)際上是A*算法的一

個(gè)擴(kuò)展出來的節(jié)點(diǎn)給出一個(gè)預(yù)

期值不如當(dāng)前已經(jīng)搜索出來的這個(gè)節(jié)點(diǎn)(包括其子節(jié)點(diǎn))從解達(dá)到加快搜索速度的目的。為Ci款最少。從其最大可能使用次數(shù)向零遞打完折扣后優(yōu)惠的價(jià)格，C為品零售價(jià)之和，則其預(yù)期值為則a=1。對(duì)回溯算法的改進(jìn)：1、添加一個(gè)全局變量BestA優(yōu)解。2、在每次生成一個(gè)節(jié)點(diǎn)時(shí)，與BestAnswer比較。如果不程。三、A*算法A*算法中更一般的引入了一

義為f=g+hg為到達(dá)當(dāng)

表示對(duì)從當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)

其必須滿足兩個(gè)條件：1h必須小于等于實(shí)際的從當(dāng)

點(diǎn)的最小耗費(fèi)h*。2、f必須保持單調(diào)遞增。

A*算法的控制結(jié)構(gòu)與廣度搜索

每次擴(kuò)展的都是當(dāng)前待擴(kuò)展

這個(gè)節(jié)點(diǎn)的估價(jià)函數(shù)值較小，展節(jié)點(diǎn)，具體算法描述如下：3*3的棋盤中有1用這個(gè)空格，用最少的步數(shù)，問題分析：預(yù)期值定義為h=|估價(jià)函數(shù)定義為f=g+h。＜Type＞Node(節(jié)點(diǎn)類型)＝RecordSitutation:TSituation（當(dāng)g:Integer;(到達(dá)當(dāng)前狀態(tài)的h:Integer;(預(yù)計(jì)的耗費(fèi))f:Real;(估價(jià)函數(shù)值)Last:Integer;(父節(jié)點(diǎn))End＜Var＞List(節(jié)點(diǎn)表):Array[1.

數(shù))]ofNode(節(jié)點(diǎn)類型);

open(總節(jié)點(diǎn)數(shù)):Integer;

close(待擴(kuò)展節(jié)點(diǎn)編號(hào)):Int

New-S:Tsituation;(新節(jié)點(diǎn))

＜Init＞List＜-0;open＜-1;close＜-0;List[1].Situation＜-初始狀

＜MainProgram＞W(wǎng)hile(close＜o(jì)pen(還有未擴(kuò)

(open＜Max(空間未用完))an

(未找到目標(biāo)節(jié)點(diǎn))do

BeginBeginclose:=close+1;ForI:=close+1toopendo(尋的節(jié)點(diǎn))BeginifList[i].f＜List[close].Begin交換List[i]和List[close]End-If;End-For;End;ForI:=1toTotalExpendMetho節(jié)點(diǎn)）BeginNew-S:=ExpendNode(List[cl)IfNot(New-SinList[1..clos(擴(kuò)展出的節(jié)點(diǎn)未與已擴(kuò)展的BeginIfNot(New-SinList[close+1(擴(kuò)展出的節(jié)點(diǎn)未與待擴(kuò)展的Beginopen:=open+1;List[open].Situation:=NewList[open].Last:=close;List[open].g:=List[close]List[open].h:=GetH(List[oList[open].f:=List[open].End-IfElseBeginIfList[close].g+cost+GetH

List[same].fthen(擴(kuò)展出來的節(jié)點(diǎn)的估價(jià)函數(shù)

節(jié)點(diǎn))BeginList[same].Situation:=NewList[same].Last:=close;List[same].g:=List[close]List[same].h:=GetH(List[oList[same].f:=List[open].End-If;End-Else;End-IfEnd-For;End-While;對(duì)A*算法的改進(jìn)--分階段A*當(dāng)A*若干個(gè)估價(jià)函數(shù)值較小的節(jié)點(diǎn)2006-4-2117:35回復(fù)4樓dapplehou第三部分搜索與動(dòng)態(tài)規(guī)劃的結(jié)合1位粉絲例1.16面24面35M*N的(1,1)從(1,1)點(diǎn)翻滾到(M,N)點(diǎn)，并且1面向上。分析：這道題目用簡單的搜索很容易發(fā)生超時(shí)，特別當(dāng)M、N較大時(shí)。24種(1,1)(2,1)(1,2)任意（I，J）點(diǎn)的狀態(tài)是由（I-1，J）和（I，J-1）點(diǎn)狀態(tài)推導(dǎo)出來的。所以如果規(guī)定棋子只能向上和向右翻滾，則可以用動(dòng)態(tài)規(guī)劃的方法將到達(dá)（M，N）點(diǎn)的所有可能的狀態(tài)推導(dǎo)出來。顯然，從（1，1）到達(dá)（N，M）這些狀態(tài)的路徑時(shí)最優(yōu)的。如果這些狀態(tài)中有1面向上的，則已求出解。如果沒有，則可以從（M，N）點(diǎn)開始廣度搜索，以（M，N）點(diǎn)的狀態(tài)組作為初始狀態(tài)，每擴(kuò)展一步時(shí)，檢查當(dāng)前所得的狀態(tài)組是否有狀態(tài)與到達(dá)格子的狀態(tài)組中的狀態(tài)相同，如果有，則由動(dòng)態(tài)規(guī)劃的最優(yōu)性和廣度搜索的最優(yōu)性可以保證已求出最優(yōu)解。例2.給出一個(gè)正整數(shù)na出a^n。分析：思路一：這道題從題面上來看非常象一道動(dòng)態(tài)規(guī)劃題，a^n=a^x1*a^x2。在保證a^x1和a^x2的最優(yōu)性之后，a^n的最優(yōu)性應(yīng)a^x1與a^x2的乘法過程中可能有一部分的重復(fù)，所以在計(jì)算a^n時(shí)要減去其重復(fù)部分。由于重復(fù)部分的計(jì)算較繁瑣，所以可以將其化為一組展開計(jì)算。描述如下：I:=n;(拆分a^n)split[n]:=x1;(分解方案)Used[n]:=True;(在乘法過程中出現(xiàn)的數(shù)字)Repeat(不斷分解數(shù)字)Used[I-split[I]]:=True;Used[split[I]]:=True;Dec(I);While(I＞1)and(notUsed[I])dodec(I);UntilI=1;ForI:=ndownto1do(計(jì)算總的乘法次數(shù))IfUsed[I]thencount:=count+1;Result:=count;(返回乘法次數(shù))思路二：通過對(duì)思路一的輸出結(jié)果的分析可以發(fā)現(xiàn)一個(gè)規(guī)律：a^19=a^1*a^18a^18=a^2*a^16a^16=a^8*a^8a^8=a^4*a