用戶:Alex G Yang/Rete算法 (2)

Rete算法是一個模式匹配算法，用於實現一個處理系統。 (英語的發音/ˈriːtiː/ REE-tee or /ˈreɪtiː/ RAY-tee, rarely /ˈriːt/ REET or /rɛˈteɪ/ re-TAY)  他決定哪些系統規則被觸發，觸發的條件基於這個系統存儲的數據。

『Rete’來自拉丁語文的「網」一詞

概述

一個簡裝的專家系統通過檢查知識庫里的已知實例(facts)，觸發哪些對應的規則，然後移到下一個規則(然後循環返回到第一個規則)。 但是這樣的簡單實現，即使規則和實例的數據量不大，執行速度也很慢。

Rete算法可以更高效的實現一個專家系統。基於Rete算法的專家系統建立一個節點網絡，每一個網絡節點(除了根節點)對應一個模式，其由左手側(LHS Left-Hand-Side)規則產生。從根節點到葉節點的路徑就是完整的左手規則。

每個節點都在內存保存了與模式匹配的實例。這個結構是一個基本的字典樹應用。當一個新實例被插入，或被修改，他們就會沿着這個網絡傳播，並與節點進行比配。當路徑上的節點條件都被滿足，他就到達了一個葉節點，對應的規則就會被觸發。

卡內基梅隆大學的Charles L. Forgy設計了這套Rete算法，最遲發表於1974的一篇論文，並在他1979的博士論文和1982的另一篇論文中進行了完善(參閱參考文獻)。 paper (see References). Rete算法最初被運用在OPS5的核心引擎上。現在已經被廣泛的應用在各種專家系統中。（如： Tibco Business Events,Newgen OmniRules, CLIPS, Jess, Drools, IBM Operational Decision Management, OPSJ, Blaze Advisor, BizTalk Rules Engine, Soar, and Sparkling Logic SMARTS.)

Rete算法是一種用空間(內存)換時間(處理速度)的設計思想。多數情況下，與簡裝的系統比速度會成幾何級數增長(速度的Rete算法的性能理論上依存於系統中規則的數量)。但是在大型的專家系統中，容易產生內存枯竭的問題。為了減少內存的使用，衍生出了Rete算法的改良版。(如:Rete2[2],收集導向匹配[3]).

描述

Illustrates the basic Rete.

另見

• Action selection mechanism
• Inference engine

參考文獻

[[Category:决策论]] [[Category:专家系统]]