




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
歸結(jié)策略歸結(jié)算法:::用歸結(jié)原理來證明定理,我們最終倒出空子句。怎么樣最快的得到空子句是我們考慮的最主要問題。如果人用歸結(jié)的方法,得到空子句通常是根據(jù)人們對(duì)子句集中子句的認(rèn)識(shí),可以最快的得到空子句。然而,歸結(jié)原理的主要思想是用機(jī)械的方法使計(jì)算機(jī)能夠快速得到空子句。這需要我們考慮高效的計(jì)算算法來提高得到空子句的效率。本節(jié)主要目的是給出各種得到空子的算法,這些算法都從不同角度提高了得到空子句的歸結(jié)效率。這些算法又稱作為歸結(jié)策略。寬度優(yōu)先寬度優(yōu)先是歸結(jié)策略中最簡(jiǎn)單的算法。下圖說明了,寬度優(yōu)先策略的主要思想:S將S重所有能歸結(jié)的子句間都?xì)w結(jié)S1 歸結(jié)產(chǎn)生的子句集S∨S1 將歸結(jié)產(chǎn)生的子句集與原子句集析取將S∨S1與S1上能歸結(jié)的子句間都?xì)w結(jié)S2歸結(jié)產(chǎn)生的子句集┆ 重復(fù)以上過程□ 這樣的歸結(jié)過程中,有大量的冗余存在。因?yàn)?,在每個(gè)歸結(jié)步驟中,將有所能夠歸結(jié)的子句之間都?xì)w結(jié),從而避免不了產(chǎn)生大量多余的歸結(jié)步驟。 例如:對(duì)于子句集{,,,},寬度優(yōu)先歸結(jié)策略將產(chǎn)生以下步驟完成: {Q,~Q,~P,P}對(duì)子句集中,能夠歸結(jié)的子句之間進(jìn)行歸結(jié)。歸結(jié)產(chǎn)生的子句集為:{,,,,}將歸結(jié)得到的子句集與原子句集合并得到{,,,,,,,,},與{,,,}子句進(jìn)行歸結(jié)。在進(jìn)行歸結(jié)得到{□,…}.這個(gè)歸結(jié)過程中存在了,兩個(gè)多余的歸結(jié)步驟。 雖然,這種歸結(jié)的方法存在了大量的冗余歸結(jié)步驟,但是這個(gè)歸結(jié)能夠保持歸結(jié)的完備性。既對(duì)于不能滿足的子句集,一定能夠得到空子句。刪除策略為了提高歸結(jié)的效率,我們首先考慮的是按著寬度優(yōu)先方法得到各個(gè)歸結(jié)集合之間的關(guān)系。也就是考慮那些歸結(jié)步驟是沒有用的。首先,任何子句與重言式都不可能歸結(jié)出空子句。因此,對(duì)于重言式?jīng)]有必要考慮其與其他子句之間的歸結(jié)。其次,設(shè)子句,,對(duì)于子句能夠與得到邏輯結(jié)果c4,A{c1^c2}如果賦值映射f,使得f(C2)=f(C3)=1,則f(C4)=1。如果賦值映射f,使得f(C1)=f(C3)=1,f(C4)=1則一定是和歸結(jié)結(jié)果;并且與歸結(jié)序列的長(zhǎng)度一定小于與歸結(jié)序列的長(zhǎng)度。{,}用數(shù)學(xué)的方法來表述以上的觀點(diǎn):設(shè)子句集不可滿足,若為重言式,為不可滿足,反之成立;{C1,..Cn-1,Cn=1}=C1&C2,…&Cn-1={C1,..Cn-1}設(shè)子句集不可滿足,若中,(稱嵌入到中),則為不可滿足的,反之成立;C1<=C2{C1,C2,…Cn}=C1^C3…^Cn=0;;;;C1&C3…&Cn=0S是不可滿足的充分必要條件S-Ci是不可滿足。根據(jù)這兩點(diǎn),我們可以從寬度優(yōu)先歸結(jié)策略中刪除一些沒有必要的步驟,從而提高歸結(jié)的效率。這種方法,我們稱之為刪除策略。對(duì)于給定的子句集,刪除策略我們可以表述如下:在S中將可被嵌入的子句刪除得到子句集;對(duì)中可以歸結(jié)的子句之間進(jìn)行歸結(jié)得到;將中的重言式和可被嵌入的子句刪除得到;上的子句進(jìn)行歸結(jié);重復(fù)以上過程,最終得到空子句。刪除策略同樣是完備的,主要是因?yàn)閯h除后的子句集與原子句集是同不可滿足的。下面例子說明了刪除策略的過程:例子:對(duì)于子句集,(1)(2)(3)(4)(5)step1:刪除(1),因?yàn)椋?)可被(4)嵌入;得到S1={2,3,4,5};step2:在S1上歸結(jié),得到 (2,3) (7)~P(a)vQ(a) (8)(4,5) step3:在S1∨S中刪除(3)可被(6)嵌入,刪除(5)可被(7)嵌入;step4:在S2中,(6),(8)歸結(jié){□};S是不可滿足的,用刪除策略是否一定能找到空子句?支持集策略我們知道人們?cè)谶M(jìn)行子句的歸結(jié)時(shí)候,主要是通過感覺上,那些子句之間有可能產(chǎn)生空子句來歸結(jié),從而效率非常高。支持集策略從人們?cè)跉w結(jié)時(shí)的一些想法出發(fā),首先把子句集進(jìn)行劃分。劃分成支持集和非支持集兩個(gè)部分??兆泳湟欢ㄊ怯芍С旨械淖泳鋮⑴c得到的。定義:設(shè)子句集S為不可滿足的,如果,且集合是可滿足,則稱子句集T為子句集S的支持集。支撐集策略:在S中求導(dǎo)出空子句的歸結(jié)序列時(shí),在每一歸結(jié)母式中至少有一個(gè)子句不在中。意味著,可以在T中或者歸結(jié)結(jié)果中。支持集策略,也是一種完備的歸結(jié)策略。即對(duì)于不可滿足的子句集S,利用支持集策略一定能夠得到空子句。下面通過一個(gè)例子來說明支持集策略的使用。例子:對(duì)于以下給定的子句集,利用支持集策略進(jìn)行歸結(jié)。(1)(2)(3)(4)我們可以看出(4),(2),(3)是可以滿足的,因此(1)為支持集。根據(jù)支持集粗略,得到:(5)在(4)(3)中利用和,并歸結(jié)得到。對(duì)(5)進(jìn)行得到;(6),對(duì)(2)進(jìn)行后;對(duì)(5)進(jìn)行后得到;歸結(jié)后得到的。(7)通過合一得到(1)和(6)歸結(jié)的空子句。線性策略線性歸結(jié)是指除第一次歸結(jié)外,其它各次歸結(jié)中,至少有一個(gè)母式是上次的歸結(jié)結(jié)果。線性歸結(jié)是完備的,即對(duì)于不可滿足的子句集S,用線性歸結(jié)的方法一定可以得到空子句。練習(xí),利用歸結(jié)原理證明,以下的子句集是不可滿足的。 以上的四種歸結(jié)策略都是完備的歸結(jié)策略。實(shí)際上,為了提高歸結(jié)的效率,還有其他不完備的歸結(jié)策略,如:鎖歸結(jié)、輸入歸結(jié)、單位歸結(jié)等。在此并不詳細(xì)敘述,感興趣的同學(xué)參見王元元的書。歸結(jié)原理應(yīng)用歸結(jié)原理在計(jì)算機(jī)科學(xué)中,有著非常廣泛的應(yīng)用。目前來說歸結(jié)原理主要有四個(gè)方面的主要應(yīng)用:定理證明:對(duì)于給定的公理系統(tǒng)證明一個(gè)公式是否為定理。是一個(gè)是非性的答案。例如,幾何定理的機(jī)器證明等。問題解決:?jiǎn)栴}解決(ProblemSolving)是人工智能中的一個(gè)主要問題。這時(shí)待證的定理通常是是否成立。給出答案通常為:“是,x=”或者為“否”;程序分析驗(yàn)證:分析和驗(yàn)證程序是否能夠給出預(yù)定的結(jié)果。主要的應(yīng)用方面是航天航空等,而非商業(yè)程序。規(guī)劃生成:根據(jù)給出的目標(biāo),規(guī)劃出一系列步驟。實(shí)際上,是對(duì)于給定的定理,找到他的歸結(jié)序列的過程。目前被應(yīng)用到智能主體的行為規(guī)劃上。目前在(2)和(4)中更多地采用基于數(shù)據(jù)處理的方法;或者稱為機(jī)器學(xué)習(xí)的方法來解決。產(chǎn)生這樣轉(zhuǎn)變得原因主要有兩個(gè):信息時(shí)代的突出特點(diǎn)是數(shù)據(jù)多,這些數(shù)據(jù)中有成功的,也有失敗的。對(duì)于同樣的方法,即可能對(duì)于某些案例是成功的,而對(duì)于另外一些反而是失敗。因此,人們更愿意從大量數(shù)據(jù)中蘊(yùn)涵的道理來確定解決方案。邏輯的方法總是非常嚴(yán)格,給出了非常具體的答案(非白即黑)。因此,很難讓人接受。例如,天氣預(yù)報(bào)說下雨是非常肯定的答案,但是沒有下的話就使大家陷入的尷尬的境地。因此,人們更喜歡概率和數(shù)據(jù)挖掘的方法。這樣給出的答案總是帶有一定的不確定性。對(duì)于這類方法中,目前主要熱門的LearningBayesNetwork,例如微軟的WindowsXP中就重點(diǎn)使用了這種技術(shù),也就是說,以后對(duì)WindowsXP出現(xiàn)的任何問題,人們都得不到的確切的回答。得到只是,某種情況的可能性最大,某種方法的有效性最高等。目前數(shù)據(jù)處理的方法,比邏輯分析的方法來說,占有極大的優(yōu)勢(shì)。不單個(gè)大公司都在推崇數(shù)據(jù)處理分析方法-例如Intel中國(guó)研究院的一個(gè)重點(diǎn)任務(wù)就是研究LearningBayesNetwork,而且這種方法也越來越多地被人們接受-主要的原因是比邏輯分析方法更容易掌握。也許不久能夠出現(xiàn)一種,將邏輯分析與數(shù)據(jù)分析結(jié)合起來的方法;但這種方法絕對(duì)不是目前的模糊邏輯和模糊系統(tǒng)等方法。A(X)B(x)B(Y)(XXXXX)RETE規(guī)則引擎IlogDroolsHORN子句程序設(shè)計(jì)子句集是一種標(biāo)準(zhǔn)的形式,利用計(jì)算機(jī)可以在這樣的子句集上進(jìn)行推理。要形成計(jì)算機(jī)程序來進(jìn)行邏輯推理,重要的一條就是讓人們?cè)诶斫夂褪褂玫臅r(shí)候,非常方便,也就是高級(jí)程序設(shè)計(jì)語(yǔ)言的基本要求。人類在推理時(shí),總是分成條件結(jié)論等。而子句集淡化這些概念,從而使人難于理解。HORN子句正是解決這樣的問題。HORN子句是一種邏輯程序設(shè)計(jì)語(yǔ)言。HORN子句定義:子句中,如果至多只含有一個(gè)正文字,那么稱該子句為HORN子句。AB=~A1v~A2vB=(A1^A2)B~P1,~P2,…PnHORN子句通常表示為:(Q1&Q2…&Qn)P。 HORN子句通常有以下四種形式之一: (P1^P2)(P3Vp4) (P4)(P1^P2) (P3)(P1^P2) ~(P1vP2vP3….) (1) ()(稱為一個(gè)過程,為過程名,為過程體,為過程調(diào)用) (2) ()(事實(shí)) (3) ()(目標(biāo)) (4)□ (停機(jī)語(yǔ)句) ~(A^A2^A3)HORN子句程序定義:HORN子句程序是指事實(shí)、過程和目標(biāo)的集合。HORN程序的執(zhí)行過程:首先有目標(biāo)集合出發(fā),對(duì)于每一個(gè)由以下遞歸過程完成:目標(biāo)Q1,Q2目標(biāo)Q1,Q2 匹配(合一) 是匹配 NO是匹配 YES是事實(shí)匹配是事實(shí)匹配新目標(biāo) NO 新目標(biāo) YES 整個(gè)程序終止程序終止程序終止對(duì)于每個(gè)首先進(jìn)行匹配,如果匹配不成功整個(gè)程序終止,且命題不成立。如果存在匹配,如果與事實(shí)匹配,程序成功結(jié)束。如果與過程匹配,則規(guī)劃新的目標(biāo),從新進(jìn)行匹配。我們知道匹配的過程實(shí)際上是合一代換過程。HORN子句例子已知:張三在那里,他的狗就在那里。 張三在火車上。詢問:張三的狗是否在火車上?HORN子句程序:;//過程;//事實(shí) 執(zhí)行過程: (1)與過程名相匹配(合一為) (2)產(chǎn)生新目標(biāo) (3)新目標(biāo)與事實(shí)匹配 (4)輸出為是HORN子句性質(zhì)有關(guān)HORN子句的主要性質(zhì)有:描述能力:HORN子句是一種特殊的子句集,因此,他的描述能力是一階謂詞邏輯的子集;例如,不能描述兩個(gè)正文字的情況。從另一個(gè)角度來看,HORN子句可以使用一階的元語(yǔ)言,因此,其描述能力不比一階語(yǔ)言差。線性歸結(jié):HORN子句采用的歸結(jié)方法是線性歸結(jié),在沒有控制執(zhí)行順序的情況下,HORN子句是完備的;HORN程序控制:通常對(duì)目標(biāo)采用順序執(zhí)行方式,從左邊開始一直到右邊的最后一個(gè)單元;對(duì)于過程調(diào)用同樣從左到右執(zhí)行。這樣的執(zhí)行方式,使HORN子句程序的執(zhí)行有了確定性。但是帶來的是HORN子句程序的不完備性,即對(duì)于一個(gè)不可滿足的HORN程序,未必能夠得到空子句。例:(1)P(x)←P(f(x))P(f(a))(2)P(f(y))←(3)←P(a) P(a)P(f(a))P(f(a))P(ff(a))(4) ←P((f(a))P(f(a))P(f(f(a)))(5)←P((f(f(a)))…多解性:對(duì)于同一個(gè)HORN程序,經(jīng)過對(duì)程序的執(zhí)行過程控制的修改,在同樣的輸入條件下,可以得到不同的結(jié)果。可逆性:HORN子句可以用來計(jì)算對(duì)于給定輸入,求輸出和對(duì)于給定輸出,求輸入的過程。PROLOG程序設(shè)計(jì)Prolog語(yǔ)言簡(jiǎn)介1、Prolog語(yǔ)言的組成1972年由法國(guó)馬賽大學(xué)的AlainColmerauer提出的,1975年被用于問題求解系統(tǒng)。Prolog語(yǔ)言HORN子句程序類似是由三個(gè)部分構(gòu)成的:事實(shí):關(guān)于個(gè)體性質(zhì)和關(guān)系的事實(shí)語(yǔ)句;例如student(john) (約翰是學(xué)生)不在用箭頭表示,必須使用小寫字母;大寫字母用來表示變量。規(guī)則:定義個(gè)體關(guān)系與性質(zhì)的規(guī)則語(yǔ)句;例如:bird(X):--animal(X,has(X,feather));(有羽毛的動(dòng)物是鳥):--左邊的(bird(X))稱為規(guī)則頭,:--右邊的稱為規(guī)則體。問題:對(duì)個(gè)體關(guān)系和性質(zhì)的詢問;例如:?—student(john); (約翰是學(xué)生嗎?) 2、Prolog語(yǔ)言執(zhí)行過程Prolog語(yǔ)言的三個(gè)部分對(duì)應(yīng)了HORN子句中的三個(gè)部分。Prolog語(yǔ)言的執(zhí)行于HORN子句也完全相同。主要操作有:搜索、匹配與回溯。具體過程請(qǐng)參考HORN子句程序。3、Prolog語(yǔ)言基本文法Prolog語(yǔ)言的最基本語(yǔ)言構(gòu)成是項(xiàng),項(xiàng)或者為常量、或者為變量或者為結(jié)構(gòu)。常量:用來表示個(gè)體或者個(gè)體關(guān)系的名稱。主要有整數(shù)和謂詞兩種。例如:1234,student等。變量:用來表示個(gè)體,用開頭為大寫字母或者下畫線等方式來定義變量名稱。例如:X,Y,Answer,_jj等。結(jié)構(gòu):是常量和變量的序列,由一個(gè)函子和該函子的自變量組成。例如:likes(john,X)等。四則運(yùn)算符等。4、Prolog語(yǔ)言的控制部分主要有三類控制語(yǔ)句:輸入輸出控制、程序動(dòng)態(tài)修改和執(zhí)行進(jìn)程控制等。輸入輸出:read(x),write(x),consult(f),reconsult(f)等程序動(dòng)態(tài)修改:asserta(x),assertz(x),retract(x),r
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 信息化技術(shù)在農(nóng)業(yè)生產(chǎn)中的合作協(xié)議
- 農(nóng)民工在崗培訓(xùn)與勞務(wù)派遣合同
- 購(gòu)買物業(yè)管理服務(wù)協(xié)議書
- 農(nóng)業(yè)生產(chǎn)經(jīng)營(yíng)資金互助保障協(xié)議
- 智慧寓言伊索寓言故事解讀
- 高考語(yǔ)文復(fù)習(xí):專題六、七
- 體育培訓(xùn)中心學(xué)員意外事故的免責(zé)及保障協(xié)議
- 高考文言文斷句100題專項(xiàng)練習(xí)(附答案及翻譯最方便)
- 小馬過河自我成長(zhǎng)的故事解讀
- 農(nóng)業(yè)旅游開發(fā)手冊(cè)
- 2024年福建省廈門市翔安區(qū)殘疾人聯(lián)合會(huì)招聘殘疾人工作聯(lián)絡(luò)員29人歷年重點(diǎn)基礎(chǔ)提升難、易點(diǎn)模擬試題(共500題)附帶答案詳解
- 幼兒園家長(zhǎng)會(huì)疾病預(yù)防
- 《儲(chǔ)糧害蟲防治技術(shù)》課件-第六章 儲(chǔ)糧保護(hù)劑及其應(yīng)用
- 排水管道施工組織設(shè)計(jì)排水管道施工組織設(shè)計(jì)排水施工排水管道施工施工設(shè)計(jì)
- 人工智能科普教育活動(dòng)方案設(shè)計(jì)
- 2024未來會(huì)議:AI與協(xié)作前沿趨勢(shì)白皮書
- 2024年廣東普通專升本《公共英語(yǔ)》完整版真題
- 國(guó)家中長(zhǎng)期科技發(fā)展規(guī)劃(2021-2035)
- 中國(guó)民族音樂的宮庭音樂
- 單原子催化劑的合成與應(yīng)用
- 水利工程施工驗(yàn)收規(guī)范對(duì)工程監(jiān)理單位的要求
評(píng)論
0/150
提交評(píng)論