人工能簡答題1、 20世紀40位圖靈獎獲得者中有6位人工智能學者：MarvinMinsky（1969年）JohnMcCarthy（1971年）HerbertSimon和AllenNewell（1975年）EdwardFeigenbaum和RajReddy（1994年）1969年第一屆國際人工智能聯合會議（InternationalJointConferenceonAI）召開,此后每兩年開一次，成為人工智能界最高級別的學術盛會。2、 簡述人工智能的概念，目標人工智能又稱為智能模擬，用計算機模擬人腦的智能行為。包括感知、學習、推理、對策、決策、預測、直覺、聯想。根本目標要求計算機不僅能模擬而且可以延伸、擴展人的智能，達到甚至超過人類智能的水平3、 人工智能的研究學派符號主義/邏輯主義學派--符號智能連接主義--計算智能行為主義--低級智能4、 人工智能的主要研究領域有哪些？自動推理、專家系統、機器學習、自然語言理解、機器人學和智能控制、模式識別、基于模型的診斷、智能規劃、智能agent、神經網絡、智能信息檢索、自動程序設計、博弈5、 機器學習一般分為哪幾種類型？監督學習、無監督學習、半監督學習、增強學習6、 常用的知識表示方法有哪幾種？簡要回答各自的特點。（1） 非結構化方法邏輯表示法QA3,STRIPS,DART,MOMO產生式系統DENDRAL，MYCIN（2） 結構化方法框架、語義網絡（3）過程式知識表示法7、 產生式系統產生式系統是人工智能系統中常用的一種程序結構，是一種知識表示系統。通常由以下三部分組成：綜合數據庫、產生式規則集、控制系統。綜合數據庫：存放問題的狀態描述的數據結構。產生式規則形式：當規則的前提條件被某一狀態描述滿足時，就對該狀態施行規則所指出的操作。控制系統：（1） 選擇規則：對同一個狀態的多個可用規則排序。（2） 檢驗狀態描述是否滿足終止條件。如果滿足終止條件，則終止產生式系統的運行，并用使用過的規則序列構造出問題的解。8、 產生式系統的基本過程ProcedurePRODUCTIONDATA-初始狀態描述untilDATA滿足終止條件，do:begin在規則集合中，選出一條可用于DATA的規則RDATA-把R應用于DATA所得的結果End9、 產生式系統的特點一、 模塊性強。綜合數據庫、規則集和控制系統相對獨立，程序的修改更加容易。二、 各產生式規則相互獨立，不能互相調用，增加一些或冊怯一些產生式規則都十分方便。三、 產生式規則的形式與人們推理所用的邏輯形式十分接近，人們具有的知識轉換成產生式規則很容易，產生式規則也容易被人們讀懂。DENDRAL和MYCIN都采用了產生式系統的結構。10、 回答產生式系統控制策略的分類，并說明各自的優缺點。（1） 不可撤回的控制策略優點：空間復雜度很低，速度快。缺點：爬山函數有多個局部極大值時，會失敗，有很大局限性。（2） 回溯控制策略優點：占空間較少，應用最廣。缺點：時間復雜性一般；如果系統不包括有關解的知識，則規則選取是盲目的，要多次回溯；如果深度限制得很低，可能找不到解。（3） 圖搜索控制策略優點：一定能找到解。缺點：占空間大，速度較慢。11、 什么叫正向產生式系統？什么叫反向產生式系統？它們各自適合于怎樣的實際問題？正向產生式系統：從初始狀態出發，不斷地應用F規則，直到產生目標狀態為止。適用條件：初始節點數^目標節點數反向產生式系統（目標驅動控制）：從目標狀態出發，利用反向的產生式規則（B規則）不斷地產生子目標，直到產生出與初始狀態相同的子目標為止。適用條件：初始節點數2目標節點數12、 敘述什么樣的產生式系統是可交換產生式系統。（什么是可交換產生式系統？）在某些產生式系統中。規則應用的次序對產生的狀態無影響，即從初始狀態到目標狀態不依賴規則次序，因此可應用不可撤回式控制策略，從而提高了產生式系統的效率，這類產生式系統就是可交換的產生式系統。13、 敘述可交換產生式系統的主要特征，說明哪種搜索策略用可交換產生式系統比較合適。a）每一條對D可應用的規則對于對D應用一條可應用規則后所產生的狀態描述仍是可應用。如果D滿足目標條件，則對D應用任何一條可應用的規則所產生的狀態描述也滿足目標條件。對。應用一個由可應用于D的規則所構成的規則序列所產生的狀態描述不因序列的次序不同而改變。不可撤回的控制方式比較合適。14、 什么是可分解的產生式系統？試述可分解的產生式系統求解問題的一般步驟。能夠把產生式系統綜合數據庫的狀態描述分解為若干組成部分，產生式規則可以分別用在各組成部分上，并且整個系統的終止條件可以用在各組成部分的終止條件表示出來的產生式系統，稱為可分解的產生式系統ProcedureSPLITDATA一初始狀態描述(Di}-DATA的分解結果；每個Di看成是獨立的狀態描述until對所有的Die(Di},Di都滿足終止條件,do:begin在(Di}中選擇一個不滿足終止條件的D*從(Di}中刪除D*從規則集合中選出一個可應用于D大的規則RD一把R應用于D*的結果(di}-D的分解結果把(di}加入(Di}中end15、 一般的圖搜索過程ProcedureGRAPHSEARCH1.G—(s},OPEN—(s)..CLOSED—NIL..LOOP:IFOPEN二NIL,THENFAIL..n—FIRST(OPEN),OPEN—TAIL(OPEN),CONS(n,CLOSED)..IFTERM(n),THEN成功結束(解路徑可通過追溯G中從n到s的指針獲得)。6.擴展節點n,令M=(m|m是n的子節點，且m不是n的祖先｝，G—GUM.(設置指針，調整指針)對于meM,(1)若m?CLOSED,m?OPEN,建立m到n的指針，并CONS(m,OPEN).⑵(a)meOPEN,考慮是否修改m的指針.(b)meCLOSED,考慮是否修改m及在G中后裔的指針。.重排OPEN表中的節點(按某一任意確定的方式或者根據探索信息)。.GOLOOP16、 無信息的圖搜索方法主要有哪兩種？深度優先搜索：排列OPEN表中的節點時按它們在搜索樹中的深度遞減排序。深度最大的節點放在表的前面，深度相等的節點以任意方式排序。寬度優先搜索：在排列OPEN表中節點時按它們在搜索圖中的深度遞增順序，深度最小的節點放在表的前面。深度相等的節點以任意方式排序。17、 什么叫啟發信息？它是如何使用的？啟發式信息：用于幫助減少搜索量的與問題有關的信息或知識。使用啟發信息的一種重要方法是采用估價函數。估價函數值低的節點排在OPEN表的前面。18、 請寫出圖搜索過程的A算法。分別指出A*和AO*算法是否可采納，如果不是，給出可采納的條件。A算法:使用估價函數f(n)=g(n)+h(n)排列OPEN表中節點順序的GRAPHSEARCH算法。A*算法:對任何節點n都有h(n)<h*(n)的A算法。如果一個搜索算法對于任何具有解路徑的圖都能找到一條最佳路徑，則稱此算法為可采納的。A*算法是可采納的(如果解路徑存在，A*一定由于找到最佳解路徑而結束)。AO*算法是不可采納的。采納的條件：如果一個AND/OR圖存在解圖，如果對于圖中所有的節點。都有好h(n)<h*(n)，并且啟發函數滿足單調限制，則AO*算法必然終止于找到最佳解圖。19、 什么叫A*算法？A*算法的主要性質是什么？定理1GRAPHSEARCH對有限圖必然終止。定理2若存在s到目標的解路徑，則算法A*終止前的任何時刻，OPEN表中總存在一個節點n’，n'在從s到目標的最佳解路徑上，且滿足f(n’)<f*(s)。定理3若存在解路徑，則A*算法必終止。定理4算法入*是可采納的。(若解路徑存在A」定找到最佳解路徑而終止)。定理5算法A*選擇的任意擴展點n都有f(n)<f*(s)o20、 兩個A*算法如何比較好壞？設A1和A2是兩個入*算法，分別使用如下兩個估價函數：f1(n)=g1(n)+h1(n)f2(n)=g2(n)+h2(n)其中，h1(n)和h2(n)是h*(n)的兩個下界。若對于所有的非目標節點n，都有h2(n)>h1(n)，則稱算法A2比算法A1有較多的信息。21、 影響算法A啟發能力的三個重要因素：算法A所找到的解路徑的費用。算法A在尋找這條解路徑的過程中所需要擴展的節點數。計算啟發函數所需要的計算量22、 估價函數一般定義為f(n)=g(n)+h(n)，指明定義中各部分的含義，并說明為什么使用這種定義方式？f(n):表示從起點到目標，經由節點n最小費用路徑上費用的估計。g(n):已經求得的當前搜索圖中從初始節點到當前節點n的最優路徑費用。h(n):從n到目標節點的最優路徑費用的估計值。便于找到最佳解路徑。23、 搜索方法的啟發能力有哪幾種基本的度量方法？滲透度是對一個搜索算法的搜索性能的度量，表示搜索集中指向某個目標的程度，而不是在無關的方向上徘徊。定義為：P=L/T其中，L是算法發現的解路徑的長度，T是算法在尋找這條解路徑期間所產生的節點(不包括初始節點，包括目標節點)有效分枝系數就是一棵搜索樹的平均分枝數.設搜索樹的深度是L，算法所產生的總節點數為「有效分枝系數是B,則有B+B2t..+BL=T或B(BL-1)/(B-1)二T24、 試述博弈樹極大極小過程。.按寬度優先生成0至L層所有節點。).使用靜態估值函數計算第L層節點的函數值。).按極小極大原則計算各層節點的倒推值，直到求出初始節點的倒推值為止。實現該倒推值的走步就是相對好的走步25、 敘述a、8剪枝規則。什么情況下效率最高？(A)(1)a剪枝：如果一個MIN節點的8值小于或等于它的某一個MAX祖先節點的a值，則剪枝發生在該MIN節點之下。(2)8剪枝：如果一個MAX節點的a值大于或者等于它的某一個MIN祖先節點的8值，則剪枝發生在該MAX節點之下。(B)a-8以各節點最終的返回值的順序產生后繼節點，即對MIN節點來說先產生具有最小值的后繼，對MAX節點來說先產生具有最大值的后繼(人為安排)。這種情況下，a-8搜索所產生的剪枝數最多，需要產生的尖端節點數最小，效率最高。使用相同存儲空間，搜索深度可擴大一倍。26、 邏輯符號?、-的含義和差別。:蘊含符號，G、H是公式，對任一解釋I,若I滿足G，則I也滿足H，稱G蘊含H，記作G?H。-：邏輯連接詞，G-H表示’巖G，則H”。G-H是公式，G?H不是公式，G?H當且僅當G-H恒真。27、 一階邏輯中，公式是怎樣定義的？—階邏輯中的公式，被遞歸定義如下：1） 原子是公式。2） 若H,G是公式，則（~H）,,（HvG）,（HaG）,（H-G）,（H6）是公式。3） 若G是公式，x是G中的自由變量，則（？x）G,（?x）G是公式。）所有公式都是有限次使用1）-3）生成的符號串。28、 敘述一階邏輯解釋的定義。一階邏輯解釋中公式G的一個解釋I,是由非空區域D和下列對G中常量符號、函數符號、謂詞符號的一組指定組成：1）對每一個常量符號，指定D中一個元素。）對每個n元函數符號，指定一個函數，即指定Dn到D的一個映射）對每個n元謂詞符號，指定一個謂詞，即指定Dn到D到{T,F}的一個映射。21、命題邏輯中，常用哪兩種公式范式？一階邏輯中，常用哪兩種范式？析取范式和合取范式有限個短語的析取式成為析取范式有限個子句的合取式成為合取范式前束范式，Skolem范式29、 什么叫子句集的Herbrand域？設S為子句集，令H0是出現于子句集S的常量符號集。如果S中無常量符號出現，則H0由一個常量符號a組成。對于i=1,2,...,Hi=Hi-1?{所有形如f(t1，…,tn)的項}其中f(t1,...,tn)是出現在S中的所有n元函數符號，tjuHi-1,j=1,...,n.稱Hi為S的i級常量集，H8稱為S的Herbrand域，簡稱S的H域。30、 在語義上證明子句集恒假時，僅考慮該子句集的Herbrand解釋是否夠用？為什么？夠用，因為子句集S恒假，當且僅當S被其所有的H解釋弄假。31、 簡要說明子句集S的Herbrand解釋與普通解釋的關系。子句集S的H解釋是S的普通解釋。S的普通解釋不一定是S的H解釋：普通解釋不是必須定義在H域上，即使定義在H域上，也不一定是一個H解釋。任取普通解釋I,依照I,可以按如下方法構造S的一個H解釋I*,使得若S在I下為真則S在I*下也為真32、 在合一算法中，設W是非空表達式集合，D是W的差異集合，則當D具有怎樣的形式時，W是不可合一的？若D中無變量符號為元素，則W是不可合一的。例.W={P(f(x)),P(g(x))},D={f(x),g(x)}若D中有奇異元素和非奇異元素，則W是不可合一的。W={P(x),P(x,y)},D={。,y}若D中元素有變量符號x和項t,且x出現在t中，則W是不可合一的。33、 什么是從子句集，推出子句C的歸結演繹？設S是子句集。從S推出子句C的一個歸結演繹是如下一個有限子句序列：C1,C2,..,Ck其中Ci或者是S中子句，或者是Cj和Cr的歸結式(j<=""p=""r<="">稱從子句集S演繹出子句C,是指存在一個從S推出C的演繹34、 在基于規則正向演繹系統中，規則和目標各要求怎樣的形式？初始狀態描述：事實表達式的AND/OR形轉換，與化Skolem范式過程類似F規則的形式：L-W是正常Skolem化后恢復成蘊涵式，且要求:L是單文字；W是AND/OR形公式