人工智能概述

1、 什么是人工智能？人工智能的研究目什么是人工智能？人工智能的研究目標和意義？標和意義？ 人工智能的研究途徑與方法人工智能的研究途徑與方法 人工智能的分支領域（基于應用領域）人工智能的分支領域（基于應用領域） 人工智能基本技術人工智能基本技術 狀態(tài)圖知識表示狀態(tài)圖知識表示 狀態(tài)圖搜索狀態(tài)圖搜索 窮舉式搜索窮舉式搜索 啟發(fā)式搜索啟發(fā)式搜索 加權狀態(tài)圖搜索加權狀態(tài)圖搜索 與或圖知識表示與或圖知識表示 與或圖搜索與或圖搜索 啟發(fā)式與或樹搜索啟發(fā)式與或樹搜索 博弈樹搜索博弈樹搜索 狀態(tài)空間（狀態(tài)空間（State SpaceState Space）問題的狀態(tài)空間是一個表示該問題全部問題的狀態(tài)空間是一個表示

2、該問題全部的可能狀態(tài)及相互關系的圖。的可能狀態(tài)及相互關系的圖。一般用賦值有向圖，包含一般用賦值有向圖，包含 S S：問題的可能有的初始狀態(tài)的集合；：問題的可能有的初始狀態(tài)的集合； F F：操作的集合；：操作的集合； G G：目標狀態(tài)的集合。：目標狀態(tài)的集合。 狀態(tài)空間常記為三元序列狀態(tài)空間常記為三元序列SG 窮舉式搜索窮舉式搜索 廣度優(yōu)先廣度優(yōu)先 深度有限深度有限 有界深度優(yōu)先有界深度優(yōu)先 啟發(fā)式搜索（九宮重排為例）啟發(fā)式搜索（九宮重排為例） 局部擇優(yōu)局部擇優(yōu) 全局擇優(yōu)全局擇優(yōu) 加權狀態(tài)圖搜索加權狀態(tài)圖搜索 分支界限分支界限 最近擇優(yōu)（瞎子爬山）最近擇優(yōu)（瞎子爬山） 與或圖相關概念與或圖相關概

3、念 本原問題、終止節(jié)點、端節(jié)點、與節(jié)點、本原問題、終止節(jié)點、端節(jié)點、與節(jié)點、或節(jié)點或節(jié)點與或圖也是一個三元組與或圖也是一個三元組 Q Q0 0 , F , Q , F , Qn n）博弈樹知識表示博弈樹知識表示 與或樹搜索與或樹搜索 可解性判定可解性判定 廣度優(yōu)先、有界深度優(yōu)先廣度優(yōu)先、有界深度優(yōu)先 有序搜索有序搜索 解樹（樹根）代價的計算方法解樹（樹根）代價的計算方法 和代價法和代價法 最大代價法最大代價法 有序搜索過程有序搜索過程 極小極大分析法極小極大分析法 剪枝技術剪枝技術 相關定義及概念相關定義及概念 化子句集的過程化子句集的過程 命題邏輯的歸結原理命題邏輯的歸結原理 替換與合一替換

4、與合一 謂詞邏輯中的歸結原理謂詞邏輯中的歸結原理 應用歸結原理求取問題答案應用歸結原理求取問題答案 歸結策略歸結策略 1、消去蘊含詞和等值詞。、消去蘊含詞和等值詞。 2、使否定詞僅作用于原子公式。、使否定詞僅作用于原子公式。 3、適當改名使量詞間不含同名指導變元。、適當改名使量詞間不含同名指導變元。 4、消去存在量詞。、消去存在量詞。 5、消去全稱量詞。、消去全稱量詞。 6、化公式為合取范式。、化公式為合取范式。 7、適當改名，使子句間無同名變元。、適當改名，使子句間無同名變元。 8、消去合取詞，以子句為元素組成一個集合、消去合取詞，以子句為元素組成一個集合S。 設設C1， C2是命題邏輯中的

5、兩個子句是命題邏輯中的兩個子句 C1中有文字中有文字L1 ，C2中有文字中有文字L2 ，且，且L1與與L2互補，互補， 從從C1 、 C2中分別刪除中分別刪除L1 、L2 ，再將剩余部分析取起來，記構成的新子句為再將剩余部分析取起來，記構成的新子句為C1 2，則，則C1 2為為C1 、 C2的歸結式。的歸結式。)L(C)L(CCC221121 一個替換（一個替換（Substitution）是形如）是形如 t1/x1, t2/x2, , tn/xn的有限集合的有限集合 設設是原子公式集是原子公式集S的一個合一，如果的一個合一，如果對對S的任何一個合一的任何一個合一都存在一個替換都存在一個替換，使

6、得使得 則稱則稱為為S的的最一般合一最一般合一(Most General Unifier),簡簡稱稱MGU。 C1，C2為無相同變元的子句；為無相同變元的子句； L1，L2為其中的兩個文字，為其中的兩個文字， L1和和L2有最一般合一有最一般合一； C1，C2的二元歸結式（二元消解式）的二元歸結式（二元消解式）為：為： C1 L1 ） （ C2 L2 ）（1 1）先為待求解的問題找一個合適的）先為待求解的問題找一個合適的求證目標謂詞求證目標謂詞；（2 2）再對目標否定子句增配（）再對目標否定子句增配（以析取形式以析取形式）一個）一個輔助輔助謂詞謂詞，該謂詞的，該謂詞的變元變元必須與對應必須與對應目標謂詞目標謂詞中的中的變元變元完全完全一致一致；（3 3）進行歸結；）進行歸結；（4 4）當歸結是剛好）當歸結是剛好只剩下輔助謂詞只剩下輔助謂詞時，輔助謂詞中原時，輔助謂詞中原變元位置上的變元位置上的項項就是就是所求所求的結果。的結果。 刪除策略刪除策略 支持集策略支持集策略 線性歸結策略線性歸結策略 輸入歸結策略輸入歸結策略 單元歸結策略單元歸結策略 祖先過濾型策略