人工智能總結(jié)

形象思維、抽象思維、靈感思維人工智能的核心內(nèi)容：搜索技術(shù)、推理技術(shù)、知識表示、人工智能語言應(yīng)用領(lǐng)域：專家系統(tǒng)、知識庫系統(tǒng)、決策支持系統(tǒng)、自然語言理解、智能機器人、模式識別知識表示方法：謂詞邏輯表示法、語義網(wǎng)絡(luò)表示法(結(jié)構(gòu)性好、明確簡潔、直觀，推理規(guī)則不明顯，表達范圍有限)、產(chǎn)生式規(guī)則表示法(格式固定、形式單一、規(guī)則間相互獨立、模塊性好、自然性好、求解效率低，專家系統(tǒng)首選)、框架表示法(對事物描述有層次，適應(yīng)性強、結(jié)構(gòu)性好、推理方式靈活，能把陳述性知識和過程性知識相結(jié)合，但缺乏形式理論)、概念從屬表示法、劇本表示法(開場條件、角色、道具、場景、結(jié)果組成，呆板，知識表示范圍窄)逆否律：X1一X2D-IX2一-IX1深度優(yōu)先：深度深的節(jié)點排在OPEN表的前面，深度淺的節(jié)點排在后面定理1：隱含圖為有限(無限)時，如果從初始結(jié)點到目標結(jié)點存在一條路徑，則算法A(A*)一定成功結(jié)束。引理：A*結(jié)束前，OPEN表中必存在f(n)Wf*(s)的節(jié)點。OPEN表上任一具有f(n)<f*(s)的結(jié)點最終都被A*選為擴展的結(jié)點A*選作擴展的任意結(jié)點n，有f(n)Wf*(s)。定理6：若h(n)滿足單調(diào)限制，則由A*所擴展的結(jié)點序列，其f值是非遞減的。A*算法應(yīng)用舉例(1)八數(shù)碼問題h(n)=0,h(n)w(n)一不在位將牌個數(shù),h(n)=p(n)一將牌與其目標位之間的距離(2)傳教士與野人問題N個傳教士與N個野人h(n)=M+C-2B，船在左岸B=1，在右岸B=0(3)迷宮問題h(n)=|Xg-xn|+|Yg-yn|,取g(n)=d(n)有f(n)=d(n)+h(n)影響算法A啟發(fā)能力的3個重要因素：路徑耗散值、擴展結(jié)點數(shù)、計算h所需要的工作量子句：例如?pVqVs是子句，子句集：將合取范式中的合取符號換成逗號歸結(jié)式：有子句：C1=PVC1',C2=?PVC2'，存在互補對，可得歸結(jié)式C12=C1VC2例：P[x,f(A)]VP{x,f(y)]VQ(y)和-P[z,f(A)]V-Q(z)取{li}={P[x,f(A)]}{mi}={-P[z,f(A)]}，s={z/x}得P[z,f(y)]V-Q(z)VQ(y)取{li}={P[x,f(A)],P{x,f(y)]}，{mi}={-P[z,f(A)]}，s={z/x,A/y}得Q(A)V-Q(z)題型1：將下式化為Skolem標準型消去蘊含符號、?深入到量詞內(nèi)部、變元易名、存在量詞左移，直到所有量詞移到前面，由此得到前束范式，再消去存在量詞，略去任意量詞題型2：用歸結(jié)原理證明公式將代證明的公式轉(zhuǎn)化為代歸結(jié)命題公式如：(p-q)-(~q-~p)=>(p-q)分別將公式前項化為合取范式，結(jié)論求反的后項化為合取范式，兩項合并后化為合取范式，求子句集，對子句集中的字句進行歸結(jié)題型3：命題邏輯的歸結(jié)過程建立待歸結(jié)命題公式2.求合取范式3.建立子句集4.對子句集中的子句用歸結(jié)規(guī)則(歸結(jié)式作為新子句加入子句集進行歸結(jié)，得到空子句，停止)題型4：謂詞邏輯的歸結(jié)過程1.寫出謂詞關(guān)系式2.用反演法寫出謂詞表達式3.化為Skolem標準型4.求取子句集S5.對S中可歸結(jié)的子句進行歸結(jié)6.歸結(jié)式放入S中，反復(fù)歸結(jié)過程7.得到空子句8.命題得證爬山法算法過程Hill-Climingn=s;LOOP:IFGOAL(n)THENEXIT(SUCCESS);EXPAND(n){mi},計算h(mi),nextn=m;//minh(mi)的結(jié)點，h(n)表示山頂與當前位置n的高度差I(lǐng)Fh(n)<h(nextn)THENEXIT(FAIL);n=nextn;GOLOOP;可分解產(chǎn)生式系統(tǒng)DATA 初始數(shù)據(jù)庫{Di} DATA的分解式；每個Di元素都看成單獨的數(shù)據(jù)庫until{Di}的所有元素都滿足結(jié)束條件,do：begin從{Di}中選一個不滿足結(jié)束條件的D*從{Di}中刪去D*在規(guī)則集中選擇一條可應(yīng)用于D*的規(guī)則RDR應(yīng)用到D*得到的結(jié)果{di}D的分解式在{Di}上添加diend回溯策略遞歸程序BACKTRACK(DATA)1.ifTERM(DATA),returnNIL//謂詞Termination判斷DATA是否滿足結(jié)束條件2.ifDEADEND(DATA),returnFAIL//DEADEND判斷從DATA表示的狀態(tài)是否能繼續(xù)下去RULES APPRULES(DATA)//APPRULES是一個函數(shù)，返回適用于DATA的規(guī)則表LOOP:ifNULL(RULES),returnFAIL//謂詞NULL判斷RULES是否空表RFIRST(RULES)//挑選出規(guī)則表中第一條規(guī)則RULESTAIL(RULES)//把規(guī)則表中地第一條規(guī)則刪去RDATA R(DATA)//把規(guī)則R用于DATA產(chǎn)生一個新的DATAPATH BACKTRACK(RDATA)//在新的DATA上遞歸地調(diào)用BACKTRACKifPATH=FAIL,goLOOP//判斷是否失敗，轉(zhuǎn)移到另一規(guī)則進行測試returnCONS(R,PATH)//把試探成功的規(guī)則串成一個表圖搜索過程過程：GRAPHSEARCHG s,OPEN(s)；建立一個搜索圖G,它只含有起始結(jié)點s。建立一個OPEN表,它只含有起始結(jié)點s,用于存放未被擴展的結(jié)點CLOSED ()；LOOP:ifOPEN=(),thenreturnFAILn FIRST(OPEN),OPENTAIL(OPEN),CLOSEDCONS(n,CLOSED)5.ifn 目標集，thenreturn[s...n]M expand(n),G'G,G{M,G}//擴展n,建立集M使M僅含有n的后繼者而不含有n的祖先，并把M中的結(jié)點加入到G中。對M中所有結(jié)點m:ifmG’，then建立指針mn,OPENCONS(m,OPEN)ifmG’，then決定是否應(yīng)改變指針mnifmCLOSED,then決定是否應(yīng)改變m的后代的指針對OPEN表中的結(jié)點重新排序；這種排序可以是任意的，也可以是啟發(fā)式的goLOOP深度優(yōu)先搜索過程DEPTH-FIRST-SEARCHG s,OPEN(s)；CLOSED ()；LOOP:ifOPEN=(),thenreturnFAIL；n FIRST(OPEN),OPENTAIL(OPEN),CLOSEDCONS(n,CLOSED)；5.ifn 目標集，thenreturn[s...n]；M expand(n),G'G,G{M,G}；ADD(M,OPEN)；標記M到n的指針；goLOOP寬度優(yōu)先搜索過程BREADTH-FIRST-SEARCHG s,OPEN(s)；CLOSED ()；LOOP:ifOPEN=(),thenreturnFAIL；n FIRST(OPEN),OPENTAIL(OPEN),CLOSEDCONS(n,CLOSED)；5.ifn 目標集，thenreturn[s...n]；M expand(n),G'G,G{M,G}；ADD(OPEN,M)；標記M到n的指針；goLOOP與或圖的AO*算法G={s},q(s)=h(s),ifs目標集thenSOLVED(s)TuntilSOLVED(s),dobegin計算局部解圖G‘(從s跟蹤標記的連接符)選出一個非終葉結(jié)點n G'Pexpand(n),ifP= thenq(n)elsep PifpGthenq(p) h(p)ifp 目標集thenSOLVED(p) T,G {G,P}〃擴展結(jié)點n，產(chǎn)生它的所有后繼結(jié)點并把它們接入仔，若不在G中，則賦值h(p)S{n}untilS=,dobegin從S中移出一個結(jié)點m,該結(jié)點在G中的所有后代都不在S中q'(m)q(m)qi(m)=ci+q(n1i)+...+q(nki)q(m)=miniqi(m)標記對應(yīng)于q(m)的連接符r,抹掉不同的連接符標記ifjSOLVED(njr)=TthenSOLVED(m)TifSOLVED(m)Vq(m)q'(m)then將向m發(fā)出標記的連接符的那些父結(jié)點加入到S中endend控制策略CLAUSES=SuntilNILeCLAUSES,dobegin在CLAUSES中選擇兩個不同的可歸結(jié)的子句Ci和Cj計算Ci和Cj的歸結(jié)式rijCLAUSES=CLAUSESV{rij}endmgu遞歸程序UNIFY(E1,E2)ifatom(E2)then交換E1,E2ifatom(E1)thenbeginifE1=E2,thenreturn NILifE1為變量thenbeginifE2中有E1,thenreturnFAIL//xf(x)elsereturn{E2/E1}endifE2為變量 then return {E1/E2}elsereturn FAILend //E1和E2都是表13.F1(CARE1),T1(CDRE1