人工智能總結(jié)

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