人工智能復習考試

1、AI ：20 世紀 70 年代以來被稱為三大科學技術成就之一， 21 世紀三大尖端技術之一；是一門研究如何使計算機系統(tǒng)顯示智能行為的學科，即研究如何讓計算機完成那些過去只有人才能做的富有智能的工作。 Nilsson（知識） Winston（功能）Feigenbaum（系統(tǒng)）。研究目標 ：近期 :使計算機更聰明、更有用. 主要研究依賴于用計算機去模擬人類某些智能行為的基本理論、基本技術和基本方法；遠期 : 探討智能的基本機理，研究如何利用自動機去模擬人的某些思維過程和智能行為，最終構造智能機器，使其高效率地解決問題。發(fā)展概況 ：1956 達特茅斯產(chǎn)生；表處理語言LISP、PROLOG 系統(tǒng)。研究

2、領域 ：自然語言理解、知識表示、自動推理、機器學習、計算機視覺、機器人技術。研究成果 ：博弈方面。 1991 年 8 月悉尼舉行的第 12 屆國際人工智能聯(lián)合會議上 IBM 的 DeeThought 2以 1:1 戰(zhàn)平澳大利亞象棋冠軍約翰森。卡斯珀羅夫和 “深藍 ”的人機大戰(zhàn)，雖然， “深藍 ”以 2:4 輸?shù)袅说谝淮蔚谋荣?，但在一年后的第二次比賽中?3.5:2.5 擊敗世界棋王，可見，在博弈方面，人工智能取得了很出色的成績。三個流派 ：符號智能、計算智能、群體智能。產(chǎn)生式表示形式 ：前提結(jié)論、事實?；窘Y(jié)構：綜合數(shù)據(jù)庫、產(chǎn)生式規(guī)則、控制系統(tǒng)。特點：綜合數(shù)據(jù)庫：依據(jù)推理情況內(nèi)容動態(tài)變化，存放

3、初始狀態(tài)、已知事實、推理的中間結(jié)果及結(jié)論等。規(guī)則庫：存放一系列規(guī)則，有相對固定的格式，規(guī)則獨立，具有高度模塊化。用于描述狀態(tài)的轉(zhuǎn)換關系、前提與結(jié)論間的因果關系等。 控制系統(tǒng)：如何應用規(guī)則，與問題無關，可分匹配、選擇（沖突解決）和應用（操作）三步。關系 : 綜合數(shù)據(jù)庫是基礎，產(chǎn)生式規(guī)則是進行推理的依據(jù)，控制系統(tǒng)是中樞?？刂撇呗苑诸?：不可撤回方式：利用問題給出的局部知識來決定如何選取規(guī)則，不必考慮撤回已用過的規(guī)則；試探方式：回溯方式，建立一個回溯點和圖搜索方式，狀態(tài)變化過程用圖結(jié)構記錄下來。產(chǎn)生式系統(tǒng)的類型 ：正向、逆向、雙向產(chǎn)生式系統(tǒng)；可交換的產(chǎn)生式；可分解的產(chǎn)生式系統(tǒng)。爬山法停滯三種情況 :

4、 局部極大點、平頂、山脊。搜索策略的任務 : 確定選擇規(guī)則的方式。兩種基本方式 ：盲目搜索 (無信息引導：按固定的步驟；啟發(fā)式搜索 (有：考慮領域的知識。狀態(tài)空間 ：求任一解路： 回溯、爬山、寬度、深度、限定范圍搜索、好的優(yōu)先搜索 .求最佳解路：大英博物館法、分支限界法、動態(tài)規(guī)劃法、最佳圖搜索法A*.問題歸約 ：求與或圖： AO* 、 極大極小法、 -剪支法、啟發(fā)式剪支法搜索：通過搜索某部分狀態(tài)空間 , 以求得由規(guī)則序列組成的一個解答的過程，它對應于將一個隱式圖中包含目的節(jié)點的一部分狀態(tài)變?yōu)轱@式圖的過程?；厮莶呗?：按規(guī)則的一個固定排序，系統(tǒng)地嘗試狀態(tài)空間中各種不同路徑的技術.是一種盲目搜索。

5、從初始狀態(tài)出發(fā)，不停地、試探地尋找路徑 , 當遇到 “死胡同 ”就回溯到路徑中最近的父節(jié)點上，查看該節(jié)點是否還有其他的子節(jié)點未被擴展，如有，則沿這些子節(jié)點繼續(xù)搜索；如果找到目標，就成功退出搜索，返回解的路徑。呈現(xiàn)出遞歸的圖搜索策略 ：分 3 種情況考慮 mi=mj mk ml ；mj 為 Open 和 Closed 中未出現(xiàn)過的mk 表示已出現(xiàn)在 Open 中的子節(jié)點， ml 表示已出現(xiàn)在 Closed 中的子節(jié)點。寬度優(yōu)先 ：按生成次序加入到Open 表后端，先進先出；有解時，一定能找到解。深度優(yōu)先 ：按生成次序加入到Open 表前端，后進先出；可能找不到解。A 算法：控制策略， OPEN

6、中的節(jié)點按 f 值從小到大排序；結(jié)論， A 是好優(yōu)先搜索策略。A* ：在算法 A 中，當 h（n） h*（ n）。完備性：如果問題有解，則算法一定能找到解；可采納性：如果問題有解，則算法一定能找到最佳解；最優(yōu)性：設A1 和A2 為某問題求解的兩個A* 算法，若對所有非目標節(jié)點均有h1（n） h2（n） h*（ n）則算法 A1 展開的節(jié)點數(shù)目至少和 A2 一樣多。結(jié)論： A* 算法結(jié)束前， OPEN 表中必存在 f（n） f*（S）的節(jié)點（ n 是在最佳路徑上的節(jié)點）； OPEN 表上任一具有 f（n） f*（S）的節(jié)點 n，最終都將被 A* 選作擴展的節(jié)點； A* 選作擴展的任一節(jié)點，有 f

7、（n） f*（S）。問題歸約法 : 當問題復雜時，可把初始問題分解成若干簡單的子問題，若子問題仍復雜，可再進一步分解，直到這些子問題的解可直接得到。與或圖搜索 ：目的在于標明起始節(jié)點是有解的；搜索不是去尋找到目標節(jié)點的一條路徑，而是尋找一個解圖。AO* 與 A* 算法的區(qū)別 ：評價函數(shù)只考慮 h(n: 理由 : 算法有自下而上的修正費用的的操作 , 實際上局部解圖費用值的估計是在起始節(jié)點 S 比較 ,計算 g 既無必要也不可能；不能優(yōu)先擴展具有最小費用的節(jié)點 :理由 : K- 連接符連接的有關子節(jié)點對父節(jié)點的可解性及費用值的估計都會產(chǎn)生影響；僅適用于無環(huán)圖 ,否則耗散值遞歸計算不收斂 :方法

8、: 當新生成的節(jié)點已在圖中時 ,判斷是否為正被擴展節(jié)點的先輩節(jié)點；控制策略不同 :沒有 OPEN 表和 CLOSED 表 , 只用生成的解圖結(jié)構 G, h(n 是最佳解圖的費用估計 .博弈樹的極大極小搜索法 ：預先考慮雙方對弈若干步之后的局勢，從當前侯選的走步中選一個相對好的走步來走，即在有限搜索深度范圍內(nèi)進行求解。極大極小搜索缺陷 : 把生成樹和棋局估值兩個過程完全分離，即先生成全部的搜索樹，然后再進行端節(jié)點估值和倒推值計算，這導致效率降低。-搜索：若兩個過程同時進行，再依一定的條件判斷，有可能盡早剪掉一些無用的分支，那么就可能減少搜索量。極大值層的倒推值下界值永不下降；極小值層的倒推值上界

9、值永不上升。剪枝：若任一極小值層節(jié)點的值小于或等于它任一先輩極大值層節(jié)點的值，即 （先輩層 （后繼層），則可終止該 MIN 層中這個 MIN 節(jié)點以下的搜索，并設置這個 MIN 節(jié)點的最終的倒推值為 .(位置： MIN 層的剪枝剪枝：若任一極大值層節(jié)點的值大于或等于它任一先輩極小值層節(jié)點的值，即 （后繼層 先輩層），則可終止該 MAX 層中這個 MAX 節(jié)點以下的搜索，并設置這個 MAX 節(jié)點的最終倒推值為 .(位置： MAX 層的剪枝遺傳算法 ：物競天擇、適者生存，Holland；選擇、交配、變異3 個主要操作。蟻群算法 ：模仿螞蟻群體在覓食過程中所體現(xiàn)出的智能行為而提出的。優(yōu)點 :良好的魯

10、棒性、正反饋、及分布式并行計算等；缺點 :迭代次數(shù)過多 ,易陷入局部最優(yōu) ,精度欠佳 .前束范式 : 若一個謂詞公式P 的所有量詞均非否定地出現(xiàn)在P 的前部，且量詞轄域是整個公式，稱P 為前束范式 . 如 F (Q1x1(QnxnM; (Qi:2 值,M: 析取式SKOLEM 范式 :消去前束范式中的所有量詞后所得到的謂詞公式,也稱 SKOLEM 標準型。 : 若變量不受全稱量詞的約束(左邊無 ,可用任意常量代替該變量; 否則 , 用以其為因變量的函數(shù)代替該存在量詞.,函數(shù)形式 (幾元函數(shù)依賴于受幾個全稱量詞約束。 : 省略.合成置換 : 有時需對表達式進行多次置換，如用s2），這時可以把兩個

11、置換合成為一個置換（記為s1、 s2 依次進行置換（即（s1 s2）E s1）知識類型 ：敘述型知識、過程型知識、控制型知識。知識模型的變換 ：同構變換：使問題更明確，便于求解；同構問題的解答等價于原始問題的解答。同態(tài)變換：使問題更加簡化，易于求解。語義網(wǎng)絡 ：是一種采用網(wǎng)絡形式表示人類知識的方法；形式：帶標識的有向圖；優(yōu)點 : 自然性 , 聯(lián)想性 ,效率較高 ; 缺點 : 不嚴格 ,不便于表達判斷性的和深層知識 .框架定義 : 人們無法把過去的經(jīng)驗都一一存儲在腦子里，而只能以一個通用的數(shù)據(jù)結(jié)構的形式存儲以往的經(jīng)驗。這樣的數(shù)據(jù)結(jié)構，稱為框架。區(qū)別 : 語義網(wǎng)絡注重表示對象間的關系，而框架更注重對象的內(nèi)部結(jié)構 .歸結(jié)反演存在的問題 ：歸結(jié)方法不自然、效率低、可能會丟失控制信息條件概率 :設 A 和 B 是某隨機試驗中的兩個事件，如果在事件 B 發(fā)生的條件下考慮事件 A 發(fā)生的概率，就稱它為事件 A 的條件概率，記 P（ A|B）。若 P