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