人工智能復(fù)習(xí)大綱

1、8.何為狀態(tài)圖和與或圖？圖搜索與問題求解有什么關(guān)系?狀態(tài)圖是描述尋找目標(biāo)或路徑問題的有向圖，即描述一個(gè)實(shí)體基于事件反應(yīng)的動態(tài)行 為，顯示了該實(shí)體如何根據(jù)當(dāng)前所處的狀態(tài)對不同的時(shí)間做出反應(yīng)的。與或圖是一種系統(tǒng) 地將問題分解為互相獨(dú)立的小問題，然后分而解決的方法。與或圖中有兩種代表性的 節(jié)點(diǎn)：“與節(jié)點(diǎn)”和“或節(jié)點(diǎn)”，“與節(jié)點(diǎn)”指所有的后續(xù)節(jié)點(diǎn)都有解時(shí)它才有解;“或節(jié)點(diǎn)”指各個(gè)后續(xù)節(jié)點(diǎn)均完全獨(dú)立，只要其中有一個(gè)有解它就有解。關(guān)系：問題 求解就是在一個(gè)圖中尋找一個(gè)從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑問題，圖搜索模擬的實(shí)際 是人腦分析問題，解決問題的過程，它基于領(lǐng)域知識的問題求解過程。11.什么是與或樹？什么是可

2、解節(jié)點(diǎn)？什么是解樹?答：一棵樹中的弧線表示所連樹枝為“與”關(guān)系，不帶弧線的樹枝為或 關(guān)系。這棵樹中既點(diǎn)是可解節(jié)點(diǎn)；一個(gè)與節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都可解；一個(gè)或節(jié)點(diǎn)可解，只 要其子節(jié)點(diǎn)至少有一個(gè)可解。 解樹實(shí)際上是由可解節(jié)點(diǎn)形成的一棵子樹，這棵子樹的根為初始節(jié)點(diǎn)，葉為終止節(jié)點(diǎn)，且這棵子樹一定是與樹14.請闡述狀態(tài)空間的一般搜索過程。OPEr表與CLOSE表的作用是什么?答：先把問題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，然后檢查 問題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。若出現(xiàn)，貝y搜索成功，找到了問題的解；若沒 出現(xiàn)，貝y再按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為當(dāng)前

3、擴(kuò)展節(jié)點(diǎn)。重復(fù) 上述過程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒有可供操作的節(jié)點(diǎn)為止。所謂對一個(gè)節(jié)點(diǎn) 進(jìn)行“擴(kuò)展”是指對該節(jié)點(diǎn)用某個(gè)可用操作進(jìn)行作用，生成該節(jié)點(diǎn)的一組子節(jié)點(diǎn)。0P EN表用于存放剛生成的節(jié)點(diǎn)，對于不同的搜索策略，節(jié)點(diǎn)在OPEN表中的排序是不同的。CLOSED表用于存放將要擴(kuò)展或者已擴(kuò)展的節(jié)點(diǎn)。15.廣度優(yōu)先搜索與深度優(yōu)先搜索各有什么特點(diǎn)?有與關(guān)系又有或關(guān)系，因此被稱為與或樹。滿足下列條件的節(jié)點(diǎn)為可解節(jié)點(diǎn)。終止節(jié)答：廣度優(yōu)先搜索就是始終先在同一級節(jié)點(diǎn)中考查，只有當(dāng)同一級節(jié)點(diǎn)考查完之后，才考查下一級節(jié)點(diǎn)?；蛘哒f，是以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，向下逐級擴(kuò)展搜索樹。所以，廣度優(yōu)先策只擴(kuò)展一個(gè)子節(jié)點(diǎn)，

4、不斷地向縱深前進(jìn)，直到不能再前進(jìn)（到達(dá)葉子節(jié)點(diǎn)或受到深度限制） 時(shí)，才從當(dāng)前節(jié)點(diǎn)返回到上一級節(jié)點(diǎn)，沿另一方向又繼續(xù)前進(jìn)。這種方法的搜索樹是從樹 根幵始一枝一枝逐漸形成的。深度優(yōu)先搜索亦稱為縱向搜索。由于一個(gè)有解的問題樹可能含有無窮分枝，深度優(yōu)先搜索如果誤入無窮分枝（即深度無限），則不可能找到目標(biāo)節(jié)點(diǎn)。所以，深度優(yōu)先搜索策略是不完備的。另外，應(yīng)用此策略得到的解不一定是最佳解 徑）O廣度優(yōu)先搜索與深度優(yōu)先搜索都屬于盲目搜索。3.8判斷下列公式是否為可合一，若可合一，則求出其最一般合一。P(f(x), b), P(y, z)P(f(x), y), P (y, f(b)P(f(y), y, x), P

5、(X, f(a), f(b)(5) P(x, y), P(y, x)不可合一O略的搜索樹是自頂向下一層一層逐漸生成的。深度優(yōu)先搜索就是在搜索樹的每一層始終先（最短路(1)P(a, b), P(x, y)解:（1）可合一，其最一般和一為:(T=a/x, b/yo可合一，其最一般和一為:(T=y/f(x), b/z可合一，其最一般和一為:(T= f(b)/y, b/x可合一，其最一般和一為:（5）第一章：1.人工智能的主要學(xué)派：符號主義學(xué)派（Sysmbolicism ），a)b)c)(T= y/xO又稱為邏輯主義學(xué)派，心理學(xué)派，計(jì)算機(jī)學(xué)派。符號主義（功能模擬）認(rèn)為知識是智能的基礎(chǔ)，人工智能的核心冋

6、題是知識的表示與知識推理。聯(lián)結(jié)主義學(xué)派（Connectionism ）：又稱為仿生學(xué)派，生理學(xué)派。用人工神經(jīng)網(wǎng)絡(luò)模仿人類 智能。（結(jié)構(gòu)模擬）行為主義學(xué)派（Actionism ）：又稱為進(jìn)化主義學(xué)派，控制論學(xué)派。認(rèn)為智能取決于感知， 表現(xiàn)為行動。（行為模擬）a)b)c)d)e)f)g)h)i)j)第二章：1.一階謂詞邏輯表示法1. 命題：它的取值為真或假2. 謂詞3. 謂詞公式4. 謂詞公式的解釋： 對于每一個(gè)解釋，謂詞公式都可以求出一個(gè)真值5.謂詞公式的永真性，可滿足性，不可滿足性永真性：如果謂詞公式 P 對個(gè)體域 D 上的任何一個(gè)解釋都取得真值 T,則稱 P 在 D 上是永真的。 可滿足性：

7、對于謂詞公式 P,如果至少存在一個(gè)解釋使得公式 P 在此解釋下的真值為 To不可滿足性：如果謂詞公式 P對于個(gè)體域 D 的任何一個(gè)解釋都取得真值為 Fo6. 謂詞公式的等價(jià)性o設(shè) P 與 Q 是兩個(gè)謂詞公式，D 是它們共同的個(gè)體域，若對 D 上的任何一個(gè)解釋，P 與 Q 都有相 同的真值，則稱公式 P 和 Q 在 D 上是等價(jià)的。如果 D 是任意的個(gè)體域，則稱 P 和 Q 是等價(jià)的。記為 PQ公式：一階謂詞表示方法1. 一階謂詞表示方法例題：2. 一階謂詞表示方法的優(yōu)點(diǎn)。自然性，準(zhǔn)確性，嚴(yán)密性，容易實(shí)現(xiàn)。3. 一階謂詞表示方法的缺點(diǎn)不能表示不確定性的知識，組合爆炸，效率低。2. 產(chǎn)生式表示方法

8、1. 可交換的產(chǎn)生式系統(tǒng)2. 可分解的產(chǎn)生式系統(tǒng)3. 可恢復(fù)的產(chǎn)生式系統(tǒng) 產(chǎn)生式表示法的特點(diǎn) 第三章：搜索方法3.1 問題求解過程的形式表示2.人工智能的研究和應(yīng)用領(lǐng)域 (10 個(gè)) 定理證明 專家系統(tǒng) 機(jī)器學(xué)習(xí) 自然語言理解 智能檢索 機(jī)器學(xué)習(xí) 自動程序設(shè)計(jì) 組合調(diào)度問題 模式識別 機(jī)器視覺 知識表示法3.1.1 狀態(tài)空間表示法3.1.2 與/ 或圖表示法3.2狀態(tài)空間的搜索方法盲目搜索算法be48f-Numbered_114d4c7b-977a-4d4d-941d-d1d7184053d9-Numbered_dd4ecac1-37be-4a5a-8e90-065641cd6d00(無代價(jià)的

9、寬度優(yōu)先搜索 ：在搜索樹的生成過程中， 只有對搜索樹中同一層的所有節(jié)點(diǎn)都考察完之 后，才對下一層的節(jié)點(diǎn)進(jìn)行考察。be48f-Numbered_114d4c7b-977a-4d4d-941d-d1d7184053d9-Numbered_dd4ecac1-37be-4a5a-8e90-065641cd6d00(無代價(jià)的深度優(yōu)先搜索 ：在搜索樹的生成過程中，對 open 表中同一層的節(jié)點(diǎn)只選擇表中一個(gè)節(jié) 點(diǎn)進(jìn)行考察和擴(kuò)展，只有當(dāng)這個(gè)節(jié)點(diǎn)是不可擴(kuò)展的，才選擇同層的兄弟節(jié)點(diǎn)進(jìn)行考察和擴(kuò)展。2.啟發(fā)式搜索算法例子：3.3 與或圖的搜索方法： 啟發(fā)式搜索算法的解樹的代價(jià)例子： 第四章：邏輯推理 4.1 推理

10、的基本概念 推理的控制策略推理方向正向推理： 從用戶提供的初始已知事實(shí)出發(fā)， 在知識庫 KD 中找到當(dāng)前可用的知識，構(gòu)成可 用知識集 KS,然后按照某種沖突消解策略從 KS 中選中一條知識進(jìn)行推理，并將推出的新 事實(shí)加入到數(shù)據(jù)庫 DB 中作為下一次推理的已知事實(shí)，在此之后再在知識庫中選取可用知識 進(jìn)行推理，如此反復(fù)進(jìn)行這一過程，知道求的要求的解或知識庫中再無可用的知識為止。 逆向推理：首先選擇一個(gè)假設(shè)目標(biāo)， 然后尋找支持該假設(shè)的依據(jù)，若所需的證據(jù)都能找到， 則說明假設(shè)是成立的，若無論如何都找不到，則說明不成立，此時(shí)需要選定新的假設(shè)。 混合推理沖突消解策略目前已有多種消解策略，其基本思想都是對知

11、識進(jìn)行排序1） 按針對性排序2） 按匹配度排序3） 根據(jù)領(lǐng)域問題的特點(diǎn)排序 歸結(jié)演繹推理基于歸結(jié)反演的問題求解 歸結(jié)反演的改進(jìn)策略1） 刪除策略2）限制策略 第五章：專家系統(tǒng)專家系統(tǒng)的概念： 專家系統(tǒng)是一種模擬人類專家解決領(lǐng)域問題的計(jì)算機(jī)軟件系統(tǒng)。專家系統(tǒng)的結(jié)構(gòu)與開發(fā)方法3. 寬度優(yōu)先和深度優(yōu)先的區(qū)別 寬度優(yōu)先搜索生成的子節(jié)點(diǎn)放入 open 表的表尾，深度優(yōu)先搜索生成的子節(jié)點(diǎn)放入 open 表 的表首。 如果問題有解，那么寬度優(yōu)先搜索總能找到最優(yōu)解。寬度優(yōu)先搜索時(shí)完備的，深度優(yōu)先搜 索是非完備的。 如果搜索最大深度設(shè)置合理，那么深度優(yōu)先搜索能找到一條解路徑，但不一定是最優(yōu)解。 深度優(yōu)先搜索的時(shí)

12、空開銷小于寬度優(yōu)先。a)b)c)例子：提示：無代價(jià)深度優(yōu)先搜索的open表是將新擴(kuò)展生成的子節(jié)點(diǎn)按節(jié)點(diǎn)序號 從小到大排序后放入open表首有代價(jià)深度優(yōu)先搜索的open表是將 新擴(kuò)展的子節(jié)點(diǎn)按照價(jià)值 從小到大放入open表首有代價(jià)寬度優(yōu)先搜索的open表中所有節(jié)點(diǎn)按代價(jià) 從小到大排序a)b)c)4.24.34.4d）e）f）第六章：1.模糊集合的定義與運(yùn)算（大題） 2. 模糊知識表示與模糊匹配（概念）a） 模糊知識表示 模糊命題：含有模糊概念，模糊數(shù)據(jù)，或帶有可信度的語句。X is A 或 x is A （CF） 模糊語言：是指表示大小，長短，輕重，快慢，多少等程度的 模糊規(guī)則：if E then H （CF, 入）E:模糊條件H:模糊結(jié)論CF 模糊規(guī)則的可信度因子 入：是規(guī)則的閾值，用于指出規(guī)則可被使用的限制 匹配度：兩個(gè)模糊命題的相似程度 貼近度：兩個(gè)模糊概念互相貼近的程度 語義距離： 相似度：知識庫 ：以某種存儲結(jié)構(gòu)存儲領(lǐng)域?qū)＜业闹R全局?jǐn)?shù)據(jù)