人工智能一紙開卷

1、緒論：人工智能：計(jì)算機(jī)科學(xué)，控制論，信息論，神經(jīng)生理學(xué)，心理學(xué)，語言學(xué)等多種學(xué)科相互滲透而發(fā)展起來的一門綜合性學(xué)科。研究如何運(yùn)用知識(shí)，以便象人類一樣完成富有智能的工作人工智能的本質(zhì)：是一門研究如何制造出人造的智能機(jī)器或者智能系統(tǒng)，來模擬人類智能活動(dòng)的能力，以延伸人們智能的科學(xué)圖靈測(cè)試：計(jì)算機(jī)和測(cè)試者分別在兩個(gè)房間且測(cè)試者看不到，測(cè)試者通過提問，判斷哪個(gè)房間是志愿者，哪個(gè)房間是計(jì)算機(jī).如果測(cè)試者在一系列的這種測(cè)試中，不能準(zhǔn)確的判斷出誰是計(jì)算機(jī)，誰是人，則說明該計(jì)算機(jī)通過了圖靈測(cè)試，具有了圖靈測(cè)試意義下的智能（提問題由計(jì)算情感（機(jī)器不會(huì)煩躁）兩方面來提）人工智能研究的基本內(nèi)容：搜索技術(shù)、知識(shí)表示、

2、規(guī)劃方法、機(jī)器學(xué)習(xí)、認(rèn)知科學(xué)、自然語言理解和機(jī)器翻譯、專家系統(tǒng)與知識(shí)工程、定理證明、搏弈、機(jī)器人、數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)、多agent系統(tǒng)、復(fù)雜系統(tǒng)、足球機(jī)器人、人機(jī)交互人工智能的發(fā)展階段：第一階段：萌芽期（1956年以前）第二階段：形成期（1956年-1961年）第三階段：發(fā)展期（1961年-1980年）第四階段：新的神經(jīng)元網(wǎng)時(shí)代（80年代初-90年代初）第五階段：（90年代初-現(xiàn)在）產(chǎn)生式系統(tǒng)：產(chǎn)生式（規(guī)則）：用于表示事物間的因果關(guān)系（也是前提和結(jié)論之間的關(guān)系）產(chǎn)生式的一般形式：IF相提/條件THEN咨論/行動(dòng)或者簡寫為：前提結(jié)論注：前提或條件部分可以是一些事實(shí)的合取或析取，結(jié)論是某一事實(shí)。后

3、件由前件來觸發(fā)。一個(gè)產(chǎn)生式生成的結(jié)論可以作為另一個(gè)產(chǎn)生式的前提。產(chǎn)生式系統(tǒng)定義：大多數(shù)專家系統(tǒng)都是以產(chǎn)生式表示知識(shí)，把一組產(chǎn)生式放在一起，讓它們相互配合，協(xié)同的工作，一個(gè)產(chǎn)生式生成的結(jié)論可以供另一個(gè)產(chǎn)生式作為前提使用，以這種方式求得問題的解的系統(tǒng)叫做產(chǎn)生式系統(tǒng)。產(chǎn)生式系統(tǒng)的結(jié)構(gòu)：組成三要素。1一個(gè)綜合數(shù)據(jù)庫（存放信息）（2組產(chǎn)生式規(guī)則（規(guī)則庫）（知識(shí)）一個(gè)控制系統(tǒng)（推理機(jī)）-規(guī)則的解釋或執(zhí)行程序（控制策略）推理機(jī)：1.按照一定策略從規(guī)則庫中選擇規(guī)則與數(shù)據(jù)庫的已知事實(shí)進(jìn)行匹配。在匹配中，出現(xiàn)下面三種情況。1匹配成功，則此規(guī)則將列入被激活侯選集（沖突集）C2匹配失敗，即輸入條件與已知條件矛盾，則此

4、條規(guī)則被完全放棄，今后不予考慮。匹配無結(jié)果，即規(guī)則前件與輸入事實(shí)無關(guān)，該規(guī)則被放入待測(cè)試規(guī)則集。2.當(dāng)匹配成功的規(guī)則多于一條時(shí)，需要從匹配成功的規(guī)則中選出一個(gè)加以執(zhí)行，即根據(jù)一定的策略解消沖突（例如選擇編號(hào)最小的）3.解釋執(zhí)行規(guī)則后件的動(dòng)作。如果該規(guī)則的后件不是問題的目標(biāo)，將其加入數(shù)據(jù)庫中。如果這些后件是一個(gè)或者多個(gè)操作時(shí)，根據(jù)一定的策略，有選擇有順序的執(zhí)行。4.掌握結(jié)束產(chǎn)生式系統(tǒng)運(yùn)行的時(shí)機(jī)。對(duì)要執(zhí)行的規(guī)則，如果該規(guī)則的后件滿足問題的結(jié)束條件，則停止推理。字符轉(zhuǎn)換的例子（手寫）產(chǎn)生式系統(tǒng)的推理：正向推理反向推理雙向推理產(chǎn)生式系統(tǒng)的特點(diǎn)：數(shù)據(jù)驅(qū)動(dòng)、知識(shí)的無序性、控制系統(tǒng)與問題無關(guān)、數(shù)據(jù)、知識(shí)和控

5、制相互獨(dú)立語義網(wǎng)絡(luò)：是用實(shí)體及其語義關(guān)系來表示知識(shí)的知識(shí)表示方法，由最基本的語義單元組成（稱為:語義基元）;由多個(gè)語義基元用相應(yīng)的語義聯(lián)系關(guān)聯(lián)在一起形成一個(gè)語義網(wǎng)絡(luò)語義基元（手寫）:結(jié)點(diǎn)代表實(shí)體，弧是有方向和標(biāo)注的：方向體現(xiàn)了結(jié)點(diǎn)所代表的實(shí)體的主次關(guān)系即結(jié)點(diǎn)1為主，結(jié)點(diǎn)2為輔,弧上的標(biāo)注表示了它所連接的兩個(gè)實(shí)體之間的語義聯(lián)系產(chǎn)生式系統(tǒng)的搜索策略：搜索策略的主要任務(wù)：確定如何選取規(guī)則的方式盲目搜索方法：不考慮給定問題具有的特定知識(shí)，系統(tǒng)根據(jù)事先確定好的某種固定排序，依次調(diào)用規(guī)則或者隨機(jī)調(diào)用規(guī)則啟發(fā)式搜索方法：考慮問題領(lǐng)域可應(yīng)用的知識(shí)，動(dòng)態(tài)地確定規(guī)則的排序，優(yōu)先調(diào)用較合適的規(guī)則搜索問題：如何在一個(gè)

6、比較大的問題空間中，只通過搜索比較小的范圍，就找到問題的解回溯策略(屬于盲目搜索):首先將規(guī)則給出固定的排序，在搜索時(shí)，1)對(duì)當(dāng)前狀態(tài)依次測(cè)每一條規(guī)則，在當(dāng)前狀態(tài)未使用的規(guī)則中找到第一條可應(yīng)用的規(guī)則，應(yīng)用于當(dāng)前狀態(tài)，得到的新的狀態(tài)重新設(shè)置為當(dāng)前狀態(tài)，并重復(fù)以上搜索。2)如果當(dāng)前狀態(tài)無規(guī)則可用，或所有規(guī)則都已經(jīng)試探過，仍未找到問題的解，則將當(dāng)前狀態(tài)的前一個(gè)狀態(tài)設(shè)置為當(dāng)前狀態(tài)3)重復(fù)以上搜索，直到找到問題的解，或者找不到問題的解?；厮莶呗运惴ǎ哼f歸過程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;/data滿足條件返回空表2, IFDEADEND(DATA)RET

7、URNFAIL;似口果狀態(tài)不合法返回fall必須回溯3, RULESkAPPRULES(DATA);APPRULESDATA的可應(yīng)用規(guī)貝U集以某種原貝U排序后賦給RULES4, LOOP:IFNULL(RULES)RETURNFAIL;/隹部規(guī)則應(yīng)用均失敗，回溯5, R:=FIRST(RULES);取第一條可應(yīng)用規(guī)則6, RULESkTAIL(RULES)刪除第一條規(guī)貝U7, RDATA:=GEN(R,DATA);M據(jù)規(guī)貝UR與DATA生成新狀態(tài)RDATA8, PATHkBACKTRACK(RDATA對(duì)新狀態(tài)遞歸調(diào)用本過程9, IFPATH=FAILGOLOOP;/遞歸調(diào)用失敗，則轉(zhuǎn)移調(diào)用另一

8、規(guī)則進(jìn)行測(cè)試10, RETURNCONS(R,PATH);邊程返回解路徑規(guī)則表(或局部解路徑字表)兩個(gè)回溯點(diǎn)分別在2、4存在的問題：分支具有無窮個(gè)狀態(tài)，算法可能會(huì)落入某個(gè)“深淵”，永遠(yuǎn)也回溯不回來。2某一分支具有環(huán)路進(jìn)入死循環(huán)解決辦法：。對(duì)搜索深度加以限制。2記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑。即增加兩個(gè)回溯點(diǎn)。DATALIST從初始到當(dāng)前的狀態(tài)表(逆向)初始狀態(tài)排在表的最后，當(dāng)前狀態(tài)排在最前返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑(以規(guī)則表的形式表示)或FAILBACKTRACK1(DATALIST1, ,DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATAL

9、IST如果DATA在DATALIS伸存在表示有回路必須回溯RETURNFAIL;/TALL是取表尾操作3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUNDt索長度大于給定值BOUND時(shí)回溯RETURNFAIL;6, RULES:=APPRULES(DATA);7, LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=C

10、ONS(RDATA,DATALIS將新狀態(tài)力口入至U表DATALIST12, PATH:=BACKTRCK1(RDATALIST表遞歸調(diào)用本過程13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);回溯策略一舉例：四皇后問題(手寫)圖搜索策略：因?yàn)榛厮菟阉髦槐Ａ魪某跏紶顟B(tài)到當(dāng)前狀態(tài)的一條路徑，節(jié)省存儲(chǔ)空間但被回溯掉的已經(jīng)搜索過的部分，不能被以后利用。所以引出圖搜索：保留所有已經(jīng)搜索過的路徑基本概念：根節(jié)點(diǎn)深度=0;路徑：即n0到nk的結(jié)點(diǎn)序列；路徑耗散值：一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散

11、值；擴(kuò)展一個(gè)節(jié)點(diǎn)：生成該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出他們之間的耗散值。一般的圖搜索算法：1, G=G0(G0=s),OPEN:=(s);/G圖；s-初始結(jié)點(diǎn)；設(shè)置open表最初只含s2, CLOSED:=();3, LOOP:IFOPEN=()THENEXIT(FAIL);4, n:=FIRST(OPEN),REMOVE(n,OPEN),/當(dāng)前節(jié)點(diǎn)ADD(n,CLOSED);5, IFGOAL(n)THENEXIT(SUCCESS成/功返回n至Us的路徑指針，可給出解路徑6, EXPAND(n戶mi,G:=ADD(mi,G);擴(kuò)展當(dāng)前結(jié)點(diǎn)，否則不能向下求解7,標(biāo)記和修改指針：/mj為open表和

12、closed表中均未出現(xiàn)過的點(diǎn)ADD(mj,OPEN),并標(biāo)記mj到n的指針；/mk已出現(xiàn)在open表中的子節(jié)點(diǎn)計(jì)算是否要修改mk、ml到n的指針；/ml已出現(xiàn)在closed表中的子節(jié)點(diǎn)計(jì)算是否要修改ml到其后繼節(jié)點(diǎn)的指針；8,對(duì)OPEN中的節(jié)點(diǎn)按某種原則重新排序；9,GOLOOP無信息圖搜索：深度優(yōu)先搜索寬度優(yōu)先搜索1, G:=G0(G0=s),OPEN:=(s),CLOSED:=();2, LOOP:IFOPEN=()THENEXIT(FAIL);3, n:=FIRST(OPEN);4, IFGOAL(n)THENEXIT(SUCCESS);5, REMOVE(n,OPEN),ADD(n,

13、CLOSED);5',IFDEPTH(n異DmGOLOOP;只在深度優(yōu)先中存在此步驟6, EXPAND(n)-mi,G:=ADD(mi,G);s7,ADD(mj,OPEN)并標(biāo)記mj到n的指針;/體現(xiàn)深度優(yōu)先K7,ADD(OPEN,mj)并標(biāo)記mj到n的指針;/體現(xiàn)寬度優(yōu)先8,GOLOOP;深度優(yōu)先：一般不能保證找到最優(yōu)解；若不限制深度可能進(jìn)入深淵寬度優(yōu)先：當(dāng)問題有解時(shí)一定能找到解；當(dāng)問題為單位耗散值，且問題有解時(shí)，一定能找到最優(yōu)解。二者均屬于圖搜索、效率不高、方法于問題無關(guān)具有通用性。啟發(fā)式圖搜索：基本思想：定義一個(gè)評(píng)價(jià)函數(shù)f,對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來擴(kuò)展。

14、(引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率)啟發(fā)式搜索算法A算法：評(píng)價(jià)函數(shù)：f(n)=g(n)+h(n)注：f(n):評(píng)價(jià)函數(shù)/h(n)：啟發(fā)函數(shù)/g*(n):從s到n的最短路徑的耗散值/h*(n):從n至ijg的最短路徑的耗散值/f*(n)=g*(n)+h*(n):從s經(jīng)過n到g的最短路徑的耗散值/g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計(jì)值算法：1,OPEN:=(s),f(s):=g(s)+h(s);2, LOOP:IFOPEN=()THENEXIT(FAIL);3, n:=FIRST(OPEN);4, IFGOAL(n)TH

15、ENEXIT(SUCCESS);5, REMOVE(n,OPEN),ADD(n,CLOSED);6, EXPAND(n)-mi,計(jì)算f(n,mi):=g(n,mi)+h(mi);ADD(mj,OPEN),標(biāo)記mj到n的指針;最佳圖搜索算法若存在初始節(jié)點(diǎn)IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),標(biāo)記mk至ijn的指針；IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml),標(biāo)記ml到n的指針，ADD(ml,OPEN);/見注7, OPEN中的節(jié)點(diǎn)按f值從小到大排序；8, GOLOOPA*：在A算法中，如果滿足條件h(n)wh*(n)則A算法稱為

16、A*算法。性質(zhì)s到目標(biāo)節(jié)點(diǎn)t的路徑，則A*必能找到最佳解結(jié)束。注：A/A*算法在第六步ADD(ml,OPEN);導(dǎo)致多次擴(kuò)展同一結(jié)點(diǎn)。原因:在前面的擴(kuò)展中，并沒有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑。解決途徑：G)對(duì)h加以限制。2對(duì)算法加以改進(jìn)(未仔細(xì)看)與或圖搜索：搜索從初始節(jié)點(diǎn)到一組終節(jié)點(diǎn)集N的一個(gè)解圖基本概念：C1與或圖是一個(gè)超圖，節(jié)點(diǎn)間通過連接符連接。2K-連接符：指向K個(gè)后繼節(jié)點(diǎn)就是k階連接符。O耗散值的計(jì)算：k(n,N)=Cn+k(n1,N)+;耐陽節(jié)點(diǎn)集Cn為連接符的耗散值C4若n是N的一個(gè)元素，則k(n,N)=0解圖的求法是：從節(jié)點(diǎn)n開始，正確選擇一個(gè)外向連接符，再從該連接符所指

17、的每一個(gè)后繼結(jié)點(diǎn)出發(fā)，繼續(xù)選一個(gè)外向連接符，如此進(jìn)行下去直到由此產(chǎn)生的每一個(gè)后繼節(jié)點(diǎn)成為集合N中的一個(gè)元素為止。6具有最小耗散值的解圖稱為最佳解圖能解節(jié)點(diǎn)(SOLVED®終節(jié)點(diǎn)是能解節(jié)點(diǎn)。2若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)至少有一個(gè)能解時(shí)，該非終節(jié)點(diǎn)才能解。3若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)均能解時(shí)，該非終節(jié)點(diǎn)才能解。注：其他情況均為不能解節(jié)點(diǎn)與或圖的啟發(fā)式搜索算法AO*:通過評(píng)價(jià)函數(shù)f(n),通過對(duì)某一個(gè)結(jié)點(diǎn)的評(píng)價(jià)來實(shí)現(xiàn)對(duì)整個(gè)局部圖的評(píng)價(jià)從而選擇待擴(kuò)展的節(jié)點(diǎn)(注：普通圖：f(n)=g(n)+h(n)表面上是對(duì)結(jié)點(diǎn)n的評(píng)價(jià)，實(shí)際上是對(duì)從s到目標(biāo)結(jié)點(diǎn)(通過n)的

18、這條路徑的評(píng)價(jià))AO*算法一過程AO*:C1建立一個(gè)搜索圖G,G:=s,計(jì)算q(s)=h(s),IFGOAL(s)THENM(s,SOLVED)©Untils已標(biāo)記為SOLVED,do:C3Begin0G':=FIND(G)/根據(jù)連接符找出一個(gè)彳f擴(kuò)展的局部圖G'C5)n:=G中的任一非終節(jié)點(diǎn)(選一個(gè)非終節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn))。®EXPAND(n)生成子節(jié)點(diǎn)集ni,其中ni不屬于G,G:=ADD(ni,G),計(jì)算q(ni)=h(ni),IFGOAL(ni)THENM(ni,SOLVED);/對(duì)G中未出現(xiàn)的子結(jié)點(diǎn)添加到G中，并計(jì)算其耗散值，若有終節(jié)點(diǎn)則加能解標(biāo)記。

19、然后把n的子節(jié)點(diǎn)添加到G中S:=n;建立含n的單一節(jié)點(diǎn)集合S.(待修正的節(jié)點(diǎn)集合)©UntilS為空，do:C9BeginREMOVE(m,S),mc不屬于S;這個(gè)m的子結(jié)點(diǎn)mc應(yīng)不在S中。初修改m的耗散值q(m):對(duì)m指向節(jié)點(diǎn)集(n1i,n2i,nki)的每個(gè)連接符i分別計(jì)算qi,qi(m)=Ci+q(n1i)+q(nki),q(m):=minqi(m);加指針到minqi(m)的連接符上，或把指針修改到minqi(m)的連接符上，即原來指針與新確定的不一致時(shí)應(yīng)刪去.IFM（nji,SOLVED）THENM（m,SOLVED）,（j=1,）/若力方k接符的所有子節(jié)點(diǎn)都是能解的，則m

20、也標(biāo)上能解.IFM（m,SOLVED）V（q（m）!=q0（m）THENADD（ma,S）;/m能解或修正的耗散值與原先估算q0不同，則把m的所有先輩節(jié)點(diǎn)ma,添加到S中.（修正向上傳遞）Oend（與9匹配）end（與3匹配）算法分為兩個(gè)部分：。4-是一個(gè)自上而下的圖生長過程，先通過有標(biāo)記的連接符，找到目前為止最好的一個(gè)局部解圖。7-是一個(gè)自下而上的耗散值修正計(jì)算，連接符的標(biāo)記以及結(jié)點(diǎn)的能解標(biāo)記。AO*算法例子見書博弈樹搜索：（博弈:雙人、一人一步）Grundy博弈（分錢幣游戲）：（手寫）極小極大搜索過程：假定一個(gè)評(píng)價(jià)函數(shù)可以對(duì)所有的棋局進(jìn)行評(píng)價(jià)，當(dāng)評(píng)價(jià)函數(shù)>0時(shí)，表示對(duì)我方有利，越大越

21、有利；當(dāng)評(píng)價(jià)函數(shù)<0時(shí)，表示對(duì)對(duì)方有利，越小越有利。2極小極大搜索策略是：是考慮雙方對(duì)弈若干步之后，從可能的走步中選一個(gè)相對(duì)較好的走法來走，即在有限的搜索深度范圍內(nèi)進(jìn)行求解。定義靜態(tài)估計(jì)函數(shù)f;f>0,表對(duì)我方有利，f<0,表對(duì)方有利，f=0,表勢(shì)均力敵；f=正無窮，表我方勝，£=負(fù)無窮表對(duì)方勝。4過程;端點(diǎn)值用靜態(tài)函數(shù)計(jì)算得到，其他節(jié)點(diǎn)用倒推法取值（MAX考慮最好情況選最大）算法的三個(gè)階段：用寬度優(yōu)先法生成規(guī)定深度的全部博弈樹，然后對(duì)其端結(jié)點(diǎn)計(jì)算其靜態(tài)估計(jì)函數(shù)（對(duì)應(yīng)算法234）（2從底向上逐級(jí)求非端結(jié)點(diǎn)的倒推估計(jì)值，直到求出初始結(jié)點(diǎn)的倒推值f（s）為止（對(duì)應(yīng)算法6

22、78）再由f（s）選出相對(duì)較好的走步算法的一點(diǎn)說明：對(duì)手回應(yīng)后當(dāng)以當(dāng)時(shí)的態(tài)作為起始狀態(tài)s,重復(fù)調(diào)用該過程。舉例:九宮格棋牌（手寫）a-P剪枝:基本思想：把生成和倒推估值結(jié)合起來進(jìn)行，再根據(jù)一定的條件判定，有可能盡早剪掉一些無用的分支極大節(jié)點(diǎn)的下界為ao極小節(jié)點(diǎn)的上界為P口剪枝：若任一極小值層節(jié)點(diǎn)的B值M它任一先輩極大值層節(jié)點(diǎn)的口值；即后輩節(jié)點(diǎn)的P值w祖先節(jié)點(diǎn)的a值時(shí)，西枝：若任一極大值層節(jié)點(diǎn)的u值大于或等于它任一先輩極小值層節(jié)點(diǎn)的口值，即a（后繼層）P（先輩層）例子見書口串剪枝注意的問題：比較實(shí)在極大與極小間進(jìn)行。2比較是與先輩（已經(jīng)有了值的節(jié)點(diǎn)）比較當(dāng)只有一個(gè)節(jié)點(diǎn)的值固定后，其值才能向父結(jié)點(diǎn)

23、傳遞。4：一剪枝與極大極小結(jié)果一致。5：-一：剪枝效率高，極大極小效率低謂詞邏輯與歸結(jié)原理：（命題以及公式自己寫）歸結(jié)原理是一種主要基于謂詞邏輯知識(shí)表示的推理方法。是一種形式語言，具有嚴(yán)密的理論體系Q是一種常用的知識(shí)表示方法謂詞基本概念：聯(lián)結(jié)詞：，A,V,T,H優(yōu)先級(jí)：最優(yōu)先其次是同級(jí)最后T,1同級(jí)；同級(jí)從左向右計(jì)算量詞：-，-I子句：如下形式的合式公式（wff）：（Liw,.vLs）每個(gè)Li是文字（原子或原子的非）/一些文字的析取（文字：不含任何連接詞的謂詞公式）子句集：所有子句的集合化子句集的方法：例：3<(p(X)由(p(YAq(YX,f(a)x(p(X)-y(p(Y)，q(YX,

24、f(a)(1)去掉蘊(yùn)涵理論根據(jù)：abab3(p(X)Wy(q(YX,f(a)vp(Y)kH(p(X)冠y(q(YX,f(a)5P(Y)(2)移動(dòng)否定符，將內(nèi)移到原子公式前：理論根據(jù)：(ab)=a-b(ab)-a-b(x)P(x).(-x)P(x)(-x)P(x>(x)P(x)3(p(X)而(q(YX,f(a)5P(Y)麗(p(X)亙(q(YX,f(a)八p(Y)(3)變量標(biāo)準(zhǔn)化，將各約束變量換名，以避免混淆，即：不同的約束，對(duì)應(yīng)于不同的變量(x)A(x)(x)B(x).(x)A(x)(y)B(y)3(p(X),Ny(q(YX,f(a)v-p(Y)A-u(-p(U)v(q(V,U,f(a)

25、p(V)(4)去掉三(skolem變換)原式為:%p(X)而y(q(YX,f(a)5P(Y)-u(-p(U)v(q(V,U,f(a)p(V)去掉三后：(p(c)-y(q(Yc,f(a)p(Y)u(p(U)(q(h(U),U,f(a)p(h(U)(5)將全稱量詞提到最前面：所用公式：(B-yA(X)-y(BA(X)VyVu(p(c)Mq(Yc,f(a)v-p(Y)(p(U)(q(h(U),U,f(a)p(h(U)略去全稱量詞為：(p(c)八(q(Yc,f(a)v-p(Y)A(p(U)(q(h(U),U,f(a)p(h(U)(6)將上式化為合取范式(p(c)八(q(Yc,f(a)5P(Y)a(p(

26、U)(q(h(U),U,f(a)(-p(U)p(h(U)(7)表不為子句的形式p(c),q(Yc,f(a)Mp(Y),-p(U)Vq(h(U),U,f(a),-p(U)Vp(h(U)注:轉(zhuǎn)化不意味著等價(jià)性，但可保證其保持“不可滿足性”這里h(X)稱為Skolem函數(shù).skolem變換：將謂詞公式中所有存在量詞消去得到該謂詞公式的skolem標(biāo)準(zhǔn)型.在消去存在量詞時(shí)，有兩種情況：a.存在量詞不在任何全稱量詞的轄域內(nèi)例如：x：(X)變?yōu)?(c),(注：c必須是一個(gè)新的常量，稱為skolem常數(shù),不能在原來的a中)b.存在量詞在某些全稱量詞的轄域內(nèi)，例如：弘三yheight(X,Y)(公式中X依賴于

27、Y)變?yōu)?quot;xheight(X,h(X)歸結(jié)原理：基本思想：將待證明的邏輯公式的結(jié)論(F),通過等值公式轉(zhuǎn)換成附加前提(結(jié)論取反)，再證明該邏輯公式是不可滿足的歸結(jié)方法：G=LQ'；G=(L)vQ'(消去互補(bǔ))構(gòu)成一個(gè)新的子句C=G'謂詞邏輯中，由于子句中包含有變?cè)?，所以不能直接消去互補(bǔ)文字(L和L)所以要做變量的置換和合一置換提形如tl/xi,tn/Xn的有限集淇中Xi是互不相同的變量，ti是不等于X的項(xiàng)，且Xi與ti互不循環(huán)出現(xiàn).若&,則稱為空置換(表示不做置換，記為置換就是將Xi替換成ti置換乘法：令日=s1/y1,Sm/ym,仃=t1/X1,tn

28、/Xn,乘法曲的直觀含義是先做B,在彳仃.上述乘法仕!的意思、是從S1Hy1,Smcr/ym,t1/X1,tn/Xn中刪除：(1)若S1G=yi,則刪除Sicr/yi項(xiàng).(2)若XiW(y1，ym,則刪除ti/Xi.所得到的新的置換.比前的，即乘法是不可交換的.合一:公式集S=E1,.石,若存在置換剛?cè)?=E1H，則例為S的一個(gè)合一，S稱是可合一的最廣合一(mgu):如果對(duì)S的任意一個(gè)合一仃,存在一個(gè)置換¥使的審,則稱6是S的一個(gè)最廣合一記為mgu.求最廣合一的目的是：使子句集中子句的文字形式結(jié)構(gòu)完全一致，從而達(dá)到取消互補(bǔ)文字的目的差異集：合一算法：謂詞邏輯的歸結(jié)舉例：是否能進(jìn)行歸結(jié)

29、可以通過置換看出設(shè)集合：歸結(jié)圖手寫(1) (VX)(R(xHL(x)(2) (-x)(D(x)>-L(x)(3) (x)(D(x)I(x)求證：(x)(I(x)R(x)化子句集：(-x)(R(x)>L(x)=>(-x)(-R(x)L(x)去全稱量詞：R(x)L(x)(2) (-x)(D(x)L(x)=>(-x)(-D(x)L(x)去全稱量詞：D(x)L(x)(3) (x)(D(x)l(x)Skolem標(biāo)準(zhǔn)化D(A)I(A)H-域即得：D(A)1(A)目標(biāo)求反：(x)(l(x)R(x)彳#(-x)(I(x)R(x)彳#(-x)(-I(x)R(x)彳#l(x)R(x)換名后

30、的子句集：R(X1)L(X1)-D(X2)L(X2)D(A)1(A)1(X5)R(X5)H-基局部搜索算法：每次運(yùn)行不能保證最優(yōu)解，但多次運(yùn)行后，可以找到滿意解。放棄找到最佳解，換取降低時(shí)間復(fù)雜度組合優(yōu)化問題：設(shè)x是決策變量，D是x的定義域，f(x)是指標(biāo)函數(shù)，g(x)是約束條件集合。則優(yōu)化問題可以表示為，求解滿足g(x)的f(x)最小值問題。如果在定義域D上，滿足條件g(x)的解是有限的，則優(yōu)化問題稱為組合優(yōu)化問題鄰域:是一個(gè)點(diǎn)附近的其他點(diǎn)的集合注：G)在一個(gè)鄰域內(nèi)的最優(yōu)解稱為局部最優(yōu)解。2在整個(gè)定義域上的最優(yōu)解稱為全局最優(yōu)解局部搜索算法：局部搜索算法(LocalSearch)隨機(jī)的選擇一個(gè)初始的可能X0CD,如果f(Xn)<f(Xb)，則Xb=Xn,P=N(X),Xb=Xo,P=N（Xb）；求Xb的鄰域如果不滿足結(jié)束條件，則Begin選才IP的一個(gè)子集PXn為P'中的最優(yōu)解求更新后的Xb鄰域轉(zhuǎn)（2）;f（X）為指標(biāo)函數(shù)。否貝UP=P-P轉(zhuǎn)（2）。End輸出計(jì)算結(jié)果結(jié)束注：按照局部搜索