轉(zhuǎn)自:http://www.keyusoft.cn/Contentview.aspx?year=2005&month=$10&day=$6&postid=123
通過(guò)一周左右的研究，對(duì)規(guī)則引擎有了一定的了解。現(xiàn)在寫(xiě)點(diǎn)東西跟大家一起交流，本文主要針對(duì)RETE算法進(jìn)行描述。我的文筆不太好，如果有什么沒(méi)講明白的或是說(shuō)錯(cuò)的地方，請(qǐng)給我留言。
首先申明，我的帖子借鑒了網(wǎng)上很流行的一篇帖子，好像是來(lái)自CSDN；還有一點(diǎn)，我不想做太多的名詞解釋，因?yàn)槲乙膊皇莻€(gè)研究很深的人，定義的不好怕被笑話。
好現(xiàn)在我們開(kāi)始。
首先介紹一些網(wǎng)上對(duì)于規(guī)則引擎比較好的帖子。
1、 來(lái)自JAVA視頻網(wǎng)
2、? RETE算法的最原始的描述，我不知道在哪里找到的，想要的人可以留下E-mail
?
接著統(tǒng)一一下術(shù)語(yǔ)，很多資料里的術(shù)語(yǔ)都非常混亂。
1、? facts 事實(shí)，我們實(shí)現(xiàn)的時(shí)候，會(huì)有一個(gè)事實(shí)庫(kù)。用F表示。
2、? patterns 模板，事實(shí)的一個(gè)模型，所有事實(shí)庫(kù)中的事實(shí)都必須滿足模板中的一個(gè)。用P表示。
3、
? conditions
條件,規(guī)則的組成部分。也必須滿足模板庫(kù)中的一條模板。用C表示。我們可以這樣理解facts、patterns、conditions之間的關(guān)系。
Patterns是一個(gè)接口，conditions則是實(shí)現(xiàn)這個(gè)接口的類，而facts是這個(gè)類的實(shí)例。
4、? rules 規(guī)則，由一到多個(gè)條件構(gòu)成。一般用and或or連接conditions。用R表示。
5、? actions 動(dòng)作，激活一條rule執(zhí)行的動(dòng)作。我們這里不作討論。
6、? 還有一些術(shù)語(yǔ)，如：working-memory、production-memory，跟這里的概念大同小異。
7、? 還有一些，如：alpha-network、beta-network、join-node，我們下面會(huì)用到，先放一下，一會(huì)討論。
?
引用一下網(wǎng)上很流行的例子，我覺(jué)得沒(méi)講明白，我在用我的想法解釋一下。
?
假設(shè)在規(guī)則記憶中有下列三條規(guī)則
?
if A(x) and B(x) and C(y) then add D(x)
if A(x) and B(y) and D(x) then add E(x)
if A(x) and B(x) and E(x) then delete A(x)
?
RETE算法會(huì)先將規(guī)則編譯成下列的樹(shù)狀架構(gòu)排序網(wǎng)絡(luò)
而工作記憶內(nèi)容及順序?yàn)閧A(1)，A(2)，B(2)，B(3)，B(4)，C(5)}，當(dāng)工作記憶依序進(jìn)入網(wǎng)絡(luò)后，會(huì)依序儲(chǔ)存在符合條件的節(jié)點(diǎn)中，直到完全符合條件的推論規(guī)則推出推論。以上述例子而言， 最后推得D(2)。
?
讓我們來(lái)分析這個(gè)例子。
?
模板庫(kù)：（這個(gè)例子中只有一個(gè)模板，算法原描述中有不同的例子, 一般我們會(huì)用tuple,元組的形式來(lái)定義facts,patterns,condition）
P: (?A , ?x)? 其中的A可能代表一定的操作，如例子中的A,B,C,D,E ; x代表操作的參數(shù)。看看這個(gè)模板是不是已經(jīng)可以描述所有的事實(shí)。
?
條件庫(kù)：(這里元組的第一項(xiàng)代表實(shí)際的操作，第二項(xiàng)代表形參)
C1: (A , <x>)
C2: (B , <x>)
C3: (C , <y>)
C4: (D , <x>)
C5: (E , <x>)
C6: (B , <y>)
?
事實(shí)庫(kù)：（第二項(xiàng)代表實(shí)參）
F1: (A,1)
F2: (A,2)
F3: (B,2)
F4: (B,3)
F5: (B,4)
F6: (C,5)
?
?????? 規(guī)則庫(kù)：
?????? ? R1: c1^c2^c3
?????? ? R2: c1^c2^c4
?????? ? R3: c1^c2^c5
?
??????
?????? 有人可能會(huì)質(zhì)疑R1: c1^c2^c3，沒(méi)有描述出，原式中：
if A(x) and B(x) and C(y) then add D(x)，A=B的關(guān)系。但請(qǐng)仔細(xì)看一下，這一點(diǎn)已經(jīng)在條件庫(kù)中定義出來(lái)了。
?
?????? 下面我來(lái)描述一下，規(guī)則引擎中RETE算法的實(shí)現(xiàn)。
?????? 首先，我們要定一些規(guī)則，根據(jù)這些規(guī)則，我們的引擎可以編譯出一個(gè)樹(shù)狀結(jié)構(gòu)，上面的那張圖中是一種簡(jiǎn)易的表現(xiàn)，其實(shí)在實(shí)現(xiàn)的時(shí)候不是這個(gè)樣子的。
?????? 這就是beta-network出場(chǎng)的時(shí)候了，根據(jù)rules我們就可以確定beta-network，下面，我就畫(huà)出本例中的beta-network，為了描述方便，我把a(bǔ)lpha-network也畫(huà)出來(lái)了。
??????
?
上圖中，左邊的部分就是beta-network,右邊是alpha-network,圓圈是join-node.
從上圖中，我們可以驗(yàn)證，在beta-network中，表現(xiàn)出了rules的內(nèi)容，其中r1,r2,r3共享了許多BM和join-node,這是由于這些規(guī)則中有共同的部分，這樣能加快match的速度。
右
邊的alpha-network是根據(jù)事實(shí)庫(kù)構(gòu)建的，其中除alpha-network節(jié)點(diǎn)的節(jié)點(diǎn)都是根據(jù)每一條condition,從事實(shí)庫(kù)中
match過(guò)來(lái)的，這一過(guò)程是靜態(tài)的，即在編譯構(gòu)建網(wǎng)絡(luò)的過(guò)程中已經(jīng)建立的。只要事實(shí)庫(kù)是穩(wěn)定的，即沒(méi)有大幅度的變化，RETE算法的執(zhí)行效率應(yīng)該是非常
高的，其原因就是已經(jīng)通過(guò)靜態(tài)的編譯，構(gòu)建了alpha-network。我們可以驗(yàn)證一下，滿足c1的事實(shí)確實(shí)是w1,w2。
下
面我們就看一下，這個(gè)算法是怎么來(lái)運(yùn)行的，即怎么來(lái)確定被激活的rules的。從top-node往下遍歷，到一個(gè)join-node,與AM for
c1的節(jié)點(diǎn)匯合，運(yùn)行到match c1節(jié)點(diǎn)。此時(shí)，match c1節(jié)點(diǎn)的內(nèi)容就是：w1,w2。繼續(xù)往下，與AM for
c2匯合（所有可能的組合應(yīng)該是w1^w3,w1^w4,w1^w5,w2^w3,w2^w4,w2^w5），因?yàn)閏1^c2要求參數(shù)相同，因此，
match
c1^c2的內(nèi)容是：w2^w3。再繼續(xù)，這里有一個(gè)扇出（fan-out），其中只有一個(gè)join-node可以被激活，因?yàn)榕赃叺腁M只有一個(gè)非空。
因此，也只有R1被激活了。
解決扇出帶來(lái)的效率降低的問(wèn)題，我們可以使用hashtable來(lái)解決這個(gè)問(wèn)題。
RETE算法還有一些問(wèn)題，如：facts庫(kù)變化，我們?cè)趺床拍芨咝У闹亟╝lpha-network，同理包括rules的變化對(duì)beta-network的影響。這一部分我還沒(méi)細(xì)看，到時(shí)候再貼出來(lái)吧。
posted on 2006-05-30 15:30
混沌中立 閱讀(1050)
評(píng)論(2) 編輯 收藏 所屬分類:
非技術(shù)