1. 概述

Rete 算法是卡內(nèi)基梅隆大學(xué)的 Charles L.Forgy 博士在 1974 年發(fā)表的論文中所闡述的算法。該算法提供了專家系統(tǒng)的一個(gè)高效實(shí)現(xiàn)。

Rete 在拉丁語(yǔ)中譯為”net”（即網(wǎng)絡(luò)）。Rete 是一種進(jìn)行大量模式集合和大量對(duì)象集合間比較的高效方法，通過(guò)網(wǎng)絡(luò)篩選的方法找出所有匹配各個(gè)模式的對(duì)象和規(guī)則。

其核心思想是用分離的匹配項(xiàng)構(gòu)造匹配網(wǎng)絡(luò)，同時(shí)緩存中間結(jié)果。以空間換時(shí)間。規(guī)則編譯（rule compilation）和運(yùn)行時(shí)執(zhí)行（runtime execution）。

2. 規(guī)則編譯（rule compilation）

規(guī)則編譯是指根據(jù)規(guī)則集生成高效推理網(wǎng)絡(luò)的過(guò)程

2.1. 相關(guān)概念：

Fact（事實(shí)）:對(duì)象之間及對(duì)象屬性之間的關(guān)系
Rule（規(guī)則）:是由條件和結(jié)論構(gòu)成的推理語(yǔ)句，一般表示為if…Then。一個(gè)規(guī)則的if部分稱為L(zhǎng)HS（left-hand-side），then部分稱為RHS（right hand side）。
Module（模式）：就是指IF語(yǔ)句的條件。這里IF條件可能是有幾個(gè)更小的條件組成的大條件。模式就是指的不能在繼續(xù)分割下去的最小的原子條件。

2.2. RETE網(wǎng)絡(luò)節(jié)點(diǎn)類型

RETE網(wǎng)絡(luò)示意圖

image.png

Root Node：所有對(duì)象進(jìn)入網(wǎng)絡(luò)的入口，在一個(gè)網(wǎng)絡(luò)中只有一個(gè)根節(jié)點(diǎn)。借用Rete算法經(jīng)典的示例：
1-input node：可分為ObjectTypeNode, AlphaNode, LeftInputAdapterNode等。

Object Type Node：事實(shí)從根節(jié)點(diǎn)進(jìn)入Rete網(wǎng)絡(luò)后，會(huì)立即進(jìn)入Object Type Node節(jié)點(diǎn)。Object Type Node提供了按對(duì)象類型過(guò)濾對(duì)象的能力，通過(guò)此類節(jié)點(diǎn)可使規(guī)則引擎不做額外的工作。Cheese類型的事實(shí)進(jìn)入網(wǎng)絡(luò)后，只需經(jīng)過(guò)類型為Cheese的Object Type Node之后的節(jié)點(diǎn)。如下圖

RootNode.png

Alpha Node：Alpha 節(jié)點(diǎn)是規(guī)則的條件部分的一個(gè)模式。通常用于評(píng)估字面的條件。如下圖，兩個(gè)Alpha Node 分別評(píng)估了Cheese事實(shí)的name和strength屬性。

image.png

Left Input Adapter Node：作用是輸入一個(gè)對(duì)象，傳播為一個(gè)單對(duì)象列表（元組）。這塊有疑問(wèn)。后續(xù)會(huì)考究。

2-input node（Beta Node）: 擁有兩個(gè)輸入的節(jié)點(diǎn)。Beta Node 節(jié)點(diǎn)用于比較兩個(gè)對(duì)象。兩個(gè)對(duì)象可能是相同或不同的類型。Beta Node主要包含Join Node 和 Not Node兩種類型。
Join Node：用作連接（join）操作的節(jié)點(diǎn)，相當(dāng)于數(shù)據(jù)庫(kù)的表連接操作。
NotNode：根據(jù)右邊輸入對(duì)左邊輸入的對(duì)象數(shù)組進(jìn)行過(guò)濾，兩個(gè) NotNode 可以完成‘ exists ’檢查。
Terminal Node：到達(dá)一個(gè)終端節(jié)點(diǎn)，表示單條規(guī)則匹配了所有的條件，網(wǎng)絡(luò)中有多個(gè)終端節(jié)點(diǎn)。當(dāng)單條規(guī)則中有or時(shí)，也會(huì)產(chǎn)生多個(gè)終端節(jié)點(diǎn)。

完整的示例：

規(guī)則文件

rule1
when
Cheese($cheddar : name == "cheddar" )
$person : Person( favouriteCheese == $cheddar )
then
System.out.println($person.getName() + " likes cheddar" );
end

rule2
when
Cheese( $cheddar : name == "cheddar" )
$person : Person( favouriteCheese != $cheddar )
then
System.out.println($person.getName() + " does not like cheddar" );
end

Rete網(wǎng)絡(luò)：

image.png

從圖上可以看到，編譯后的RETE網(wǎng)絡(luò)中，AlphaNode是共享的，而B(niǎo)etaNode不是共享的。兩條規(guī)則的BetaNode的不同。然后這兩條規(guī)則有各自的Terminal Node。

2.3. 創(chuàng)建Rete網(wǎng)絡(luò)

RETE算法通過(guò)構(gòu)建一個(gè)網(wǎng)絡(luò)進(jìn)行匹配，具體過(guò)程如下：

創(chuàng)建root節(jié)點(diǎn)（根節(jié)點(diǎn)），推理網(wǎng)絡(luò)的入口。
拿到規(guī)則1，從規(guī)則1中取出模式1（模式就是最小的原子條件）。

a) 檢查模式1中的參數(shù)類型，如果是新類型，添加一個(gè)類型節(jié)點(diǎn)。
b) 檢查模式1對(duì)應(yīng)的Alpha節(jié)點(diǎn)是否存在，如果存在記錄下節(jié)點(diǎn)的位置；如果沒(méi)有，將模式1作為一個(gè)Alpha節(jié)點(diǎn)加入到網(wǎng)絡(luò)中。同時(shí)根據(jù)Alpha節(jié)點(diǎn)建立Alpah內(nèi)存表。
c) 重復(fù)b，直到處理完所有模式。
d) 組合Beta節(jié)點(diǎn)：Beta(2)左輸入節(jié)點(diǎn)為Alpha(1)，右輸入節(jié)點(diǎn)為Alpha(2)；Beta(i)左輸入節(jié)點(diǎn)是Beta(i-1),右輸入節(jié)點(diǎn)為Alpha(i)，并將兩個(gè)父節(jié)點(diǎn)的內(nèi)存表內(nèi)聯(lián)成為自己的內(nèi)存表
e) 重復(fù)d，直到所有Beta節(jié)點(diǎn)處理完畢
f) 將動(dòng)作Then部分封裝成最后節(jié)點(diǎn)做為Beta（n）

重復(fù)2，直到所有規(guī)則處理完畢

3. 運(yùn)行時(shí)執(zhí)行（runtime execution）

推理引擎在進(jìn)行模式匹配時(shí)，先對(duì)事實(shí)進(jìn)行斷言，為每一個(gè)事實(shí)建立WME(Working Memory Element)，然后將WME從RETE鑒別網(wǎng)絡(luò)的根結(jié)點(diǎn)開(kāi)始匹配，因?yàn)閃ME傳遞到的結(jié)點(diǎn)類型不同采取的算法也不同，所以需要對(duì)alpha結(jié)點(diǎn)和beta結(jié)點(diǎn)處理WME的不同情況而分開(kāi)討論。

   1)如果WME的類型和根節(jié)點(diǎn)的后繼結(jié)點(diǎn)TypeNode(alpha結(jié)點(diǎn)的一種)所指定的類型相同，則會(huì)將該事實(shí)保存在該TypeNode結(jié)點(diǎn)對(duì)應(yīng)的alpha存儲(chǔ)區(qū)中，該WME被傳到后繼結(jié)點(diǎn)繼續(xù)匹配，否則會(huì)放棄該WME的后續(xù)匹配；
   2)如果WME被傳遞到alpha結(jié)點(diǎn)，則會(huì)檢測(cè)WME是否和該結(jié)點(diǎn)對(duì)應(yīng)的模式相匹配，若匹配，則會(huì)將該事實(shí)保存在該alpha結(jié)點(diǎn)對(duì)應(yīng)的存儲(chǔ)區(qū)中，該WME被傳遞到后繼結(jié)點(diǎn)繼續(xù)匹配，否則會(huì)放棄該WME的后續(xù)匹配：
   3)如果WME被傳遞到beta結(jié)點(diǎn)的右端，則會(huì)加入到該beta結(jié)點(diǎn)的right存儲(chǔ)區(qū)，并和left存儲(chǔ)區(qū)中的Token進(jìn)行匹配(匹配動(dòng)作根據(jù)beta結(jié)點(diǎn)的類型進(jìn)行，例如：join，projection，selection)，匹配成功，則會(huì)將該WME加入到Token中，然后將Token傳遞到下一個(gè)結(jié)點(diǎn)，否則會(huì)放棄該WME的后續(xù)匹配：
   4)如果Token被傳遞到beta結(jié)點(diǎn)的左端，則會(huì)加入到該beta結(jié)點(diǎn)的left存儲(chǔ)區(qū)，并和right存儲(chǔ)區(qū)中的WME進(jìn)行匹配(匹配動(dòng)作根據(jù)beta結(jié)點(diǎn)的類型進(jìn)行，例如：join，projection，selection)，匹配成功，則該Token會(huì)封裝匹配到的WME形成新的Token，傳遞到下一個(gè)結(jié)點(diǎn)，否則會(huì)放棄該Token的后續(xù)匹配；
   5)如果WME被傳遞到beta結(jié)點(diǎn)的左端，將WME封裝成僅有一個(gè)WME元素的WME列表做為Token，然后按照 4) 所示的方法進(jìn)行匹配：
   6)如果Token傳遞到終結(jié)點(diǎn)，則和該根結(jié)點(diǎn)對(duì)應(yīng)的規(guī)則被激活，建立相應(yīng)的Activation，并存儲(chǔ)到Agenda當(dāng)中，等待激發(fā)。

   7)如果WME被傳遞到終結(jié)點(diǎn)，將WME封裝成僅有一個(gè)WME元素的WME列表做為Token，然后按照 6) 所示的方法進(jìn)行匹配；

4. 一些實(shí)踐

由于從事運(yùn)輸行業(yè)，故以業(yè)內(nèi)的典型場(chǎng)景作為實(shí)踐示例。
例如：我們需要將提供“機(jī)票+酒店”、“機(jī)票+酒店+貴賓休息室”兩種類型的產(chǎn)品給旅客。
機(jī)票、酒店、貴賓休息室需要滿足一些基本的限制條件。并且：
“機(jī)票+酒店”產(chǎn)品要保障：酒店位于目的地且到達(dá)當(dāng)天可以入住。
“機(jī)票+酒店+貴賓休息室”產(chǎn)品要保障：酒店位于目的地且到達(dá)當(dāng)天可以入住。貴賓休息室位于出發(fā)城市。

下圖展示了打包規(guī)則所構(gòu)成的RETE網(wǎng)絡(luò)。

機(jī)加酒，機(jī)加酒加貴賓休息室.png

基于Drools實(shí)現(xiàn)相關(guān)規(guī)則：

數(shù)據(jù)模型

package com.myspace.packagedproduct;
public class Location implements java.io.Serializable {
    static final long serialVersionUID = 1L;
    @org.kie.api.definition.type.Label(value = "\u56FD\u5BB6")
    private java.lang.String country;
    @org.kie.api.definition.type.Label(value = "\u7701\u4EFD")
    private java.lang.String province;
    @org.kie.api.definition.type.Label(value = "\u57CE\u5E02")
    private java.lang.String city;
   ...Getter、Setter方法...
}

public class Segment implements java.io.Serializable {
    static final long serialVersionUID = 1L;
    @org.kie.api.definition.type.Label("產(chǎn)品編碼")
    private java.lang.String proCode;
    @org.kie.api.definition.type.Label("產(chǎn)品名稱")
    private java.lang.String proName;
    @org.kie.api.definition.type.Label("出發(fā)城市")
    private java.lang.String startCity;
    @org.kie.api.definition.type.Label("到達(dá)城市")
    private java.lang.String arriveCity;
    @org.kie.api.definition.type.Label("艙位")
    private java.lang.String cabin;
    @org.kie.api.definition.type.Label("航班日期")
    private java.util.Date flightDate;
        ...Getter、Setter方法...
}

public class Hotel implements java.io.Serializable {
    static final long serialVersionUID = 1L;
    @org.kie.api.definition.type.Label("產(chǎn)品編碼")
    private java.lang.String proCode;
    @org.kie.api.definition.type.Label("產(chǎn)品名稱")
    private java.lang.String proName;
    @org.kie.api.definition.type.Label("房型")
    private java.lang.String roomType;
    @org.kie.api.definition.type.Label("入住日期")
    private java.util.Date checkInDate;
    @org.kie.api.definition.type.Label("位置")
    private com.myspace.packagedproduct.Location location;
    @org.kie.api.definition.type.Label(value = "\u662F\u5426\u53EF\u6253\u5305\u9500\u552E")
    private java.lang.Boolean ifCanPackageSale;
        ...Getter、Setter方法...
}

public class ReservedLounge implements java.io.Serializable {
    static final long serialVersionUID = 1L;
    @org.kie.api.definition.type.Label("產(chǎn)品編碼")
    private java.lang.String proCode;
    @org.kie.api.definition.type.Label("產(chǎn)品名稱")
    private java.lang.String proName;
    @org.kie.api.definition.type.Label("位置")
    private com.myspace.packagedproduct.Location location;
    @org.kie.api.definition.type.Label("是否自營(yíng)")
    private boolean selfSupport;
        ...Getter、Setter方法...
}

public class PackagedProduct implements java.io.Serializable {
    static final long serialVersionUID = 1L;
    @org.kie.api.definition.type.Label(value = "\u6210\u5458\u4EA7\u54C1ID\u5217\u8868")
    private java.util.List<java.lang.String> itemProductCodes;
      ...Getter、Setter方法...
}

規(guī)則

 import java.util.Date;
 import java.text.SimpleDateFormat;
 import java.math.BigDecimal;
 import java.util.List;
 import com.alibaba.fastjson.JSON;
 import com.alibaba.fastjson.JSONObject;
 import com.alibaba.fastjson.JSONArray;
 import com.myspace.packagedproduct.*;
 import com.myspace.packagedproduct.PackagedProduct
 import java.util.ArrayList;
 global java.util.Date now;
 global java.text.SimpleDateFormat dateFormat;

rule "segment_hotel"
    when
        seg : Segment( startCity in ( "XMN", "PEK", "FOC", "HGH", "TSN", "JJN" ) , cabin == "Y" )
        hotel : Hotel( ifCanPackageSale == true , location != null , location.city == seg.arriveCity )
    then

        System.out.println("【機(jī)+酒產(chǎn)品】"+seg.getProCode()+" + "+hotel.getProCode());

end

rule "segment_hotel_lounge"
    dialect "java"
    when
        seg : Segment( startCity in ( "XMN", "PEK", "FOC", "HGH", "TSN", "JJN" ) , cabin == "Y" )
        hotel : Hotel( ifCanPackageSale == true , location != null , location.city == seg.arriveCity )
        lounge:ReservedLounge(selfSupport==true,location.city == seg.startCity)
    then
    System.out.println("【機(jī)+酒+休息室產(chǎn)品】"+seg.getProCode()+" + "+hotel.getProCode()+" + "+lounge.getProCode());
end

規(guī)則調(diào)用語(yǔ)句

   @Test
    public void testPackagedProduct() throws ParseException {
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
        Date date1 = sdf.parse("2018-09-30");
        Date date2 = sdf.parse("2018-09-31");
        KieSession kieSession = this.getKieSessionBySessionName("mapAndList-rules");
        Segment seg = new Segment();
        seg.setArriveCity("PEK");
        seg.setStartCity("XMN");
        seg.setFlightDate(date1);
        seg.setCabin("Y");
        seg.setProCode("seg1");
        Segment seg2 = new Segment();
        seg2.setArriveCity("PEK");
        seg2.setStartCity("XMN");
        seg2.setFlightDate(date1);
        seg2.setCabin("T");
        seg2.setProCode("seg2");
        Segment seg3 = new Segment();
        seg3.setArriveCity("XMN");
        seg3.setStartCity("TSN");
        seg3.setFlightDate(date1);
        seg3.setCabin("Y");
        seg3.setProCode("seg3");
        Hotel hotel = new Hotel();
        hotel.setCheckInDate(date1);
        hotel.setIfCanPackageSale(true);
        hotel.setLocation(new Location("", "", "XMN"));
        hotel.setProCode("hotel1");
        Hotel hotel2 = new Hotel();
        hotel2.setCheckInDate(date2);
        hotel2.setIfCanPackageSale(true);
        hotel2.setLocation(new Location("", "", "XMN"));
        hotel2.setProCode("hotel2");
        Hotel hotel3 = new Hotel();
        hotel3.setCheckInDate(date1);
        hotel3.setIfCanPackageSale(true);
        hotel3.setLocation(new Location("", "", "NRT"));
        hotel3.setProCode("hotel3");
        Hotel hotel4 = new Hotel();
        hotel4.setCheckInDate(date1);
        hotel4.setIfCanPackageSale(true);
        hotel4.setLocation(new Location("", "", "PEK"));
        hotel4.setProCode("hotel4");

        ReservedLounge lounge = new ReservedLounge();
        lounge.setLocation(new Location("", "", "XMN"));
        lounge.setSelfSupport(true);
        lounge.setProCode("lounge1");
        ReservedLounge lounge2 = new ReservedLounge();
        lounge2.setLocation(new Location("", "", "PEK"));
        lounge2.setSelfSupport(true);
        lounge2.setProCode("lounge2");
        ReservedLounge lounge3 = new ReservedLounge();
        lounge3.setLocation(new Location("", "", "XMN"));
        lounge3.setSelfSupport(false);
        lounge3.setProCode("lounge3");
        kieSession.insert(seg);
        kieSession.insert(seg2);
        kieSession.insert(seg3);
        kieSession.insert(hotel);
        kieSession.insert(hotel2);
        kieSession.insert(hotel3);
        kieSession.insert(hotel4);
        kieSession.insert(lounge);
        kieSession.insert(lounge2);
        kieSession.insert(lounge3);
        kieSession.fireAllRules();
        kieSession.dispose();
    }

執(zhí)行結(jié)果

【機(jī)+酒產(chǎn)品】seg1 + hotel4
【機(jī)+酒產(chǎn)品】seg3 + hotel1
【機(jī)+酒產(chǎn)品】seg3 + hotel2
【機(jī)+酒+休息室產(chǎn)品】seg1 + hotel4 + lounge1

5. 為何RETE算法效率高

5.1. RETE算法優(yōu)于普通代碼邏輯

借用上面的示例，如：Segment，Hotel，ReservedLounge類型的產(chǎn)品分別有10個(gè)。按照一般的程序處理邏輯，我們要寫三個(gè)For循環(huán)去處理三類產(chǎn)品的打包操作，計(jì)算次數(shù)為三類產(chǎn)品數(shù)目的笛卡爾積級(jí)別的，即：10*10*10 =1000。

而RETE算法采用空間換時(shí)間的策略，將中間的計(jì)算結(jié)果緩存下來(lái)（Alpha Memory，Beta Memory）。計(jì)算次數(shù)為10+10+10（Alpha節(jié)點(diǎn)計(jì)算次數(shù)）加上2次join/projection操作（Beta節(jié)點(diǎn)計(jì)算次數(shù)）?；趦?nèi)存中的數(shù)據(jù)做join/projection/selection操作效率很高。

5.2. Rete算法優(yōu)于傳統(tǒng)的模式匹配算法。

a． Rete 算法是一種啟發(fā)式算法，不同規(guī)則之間往往含有相同的模式，因此在 beta-network 中可以共享 BetaMemory 和 betanode。如果某個(gè) betanode 被 N 條規(guī)則共享，則算法在此節(jié)點(diǎn)上效率會(huì)提高 N 倍。

b. Rete 算法由于采用 AlphaMemory 和 BetaMemory 來(lái)存儲(chǔ)事實(shí)，當(dāng)事實(shí)集合變化不大時(shí)，保存在 alpha 和 beta 節(jié)點(diǎn)中的狀態(tài)不需要太多變化，避免了大量的重復(fù)計(jì)算，提高了匹配效率。

c. 從 Rete 網(wǎng)絡(luò)可以看出，Rete 匹配速度與規(guī)則數(shù)目無(wú)直接關(guān)系，這是因?yàn)槭聦?shí)只有滿足本節(jié)點(diǎn)才會(huì)繼續(xù)向下沿網(wǎng)絡(luò)傳遞。

6.RETE算法的缺點(diǎn)

RETE算法使用了存儲(chǔ)區(qū)存儲(chǔ)已計(jì)算的中間結(jié)果，以空間換取時(shí)間，從而加快系統(tǒng)的速度。然而存儲(chǔ)區(qū)根據(jù)規(guī)則的條件于事實(shí)的數(shù)目成指數(shù)級(jí)增長(zhǎng)，極端情況下會(huì)耗盡系統(tǒng)資源。

7. RETE算法的衍生

KIE團(tuán)隊(duì)改良了原生的Rete算法：ReteOO ...

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

RETE算法簡(jiǎn)述 & 實(shí)踐

RETE算法簡(jiǎn)述 & 實(shí)踐

1. 概述

2. 規(guī)則編譯（rule compilation）

2.1. 相關(guān)概念：

2.2. RETE網(wǎng)絡(luò)節(jié)點(diǎn)類型

2.3. 創(chuàng)建Rete網(wǎng)絡(luò)

3. 運(yùn)行時(shí)執(zhí)行（runtime execution）

4. 一些實(shí)踐

5. 為何RETE算法效率高

5.1. RETE算法優(yōu)于普通代碼邏輯

5.2. Rete算法優(yōu)于傳統(tǒng)的模式匹配算法。

6.RETE算法的缺點(diǎn)

7. RETE算法的衍生

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

RETE算法簡(jiǎn)述 & 實(shí)踐

1. 概述

2. 規(guī)則編譯（rule compilation）

2.1. 相關(guān)概念：

2.2. RETE網(wǎng)絡(luò)節(jié)點(diǎn)類型

2.3. 創(chuàng)建Rete網(wǎng)絡(luò)

3. 運(yùn)行時(shí)執(zhí)行（runtime execution）

4. 一些實(shí)踐

5. 為何RETE算法效率高

5.1. RETE算法優(yōu)于普通代碼邏輯

5.2. Rete算法優(yōu)于傳統(tǒng)的模式匹配算法。

6.RETE算法的缺點(diǎn)

7. RETE算法的衍生

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

5.2. Rete算法優(yōu)于傳統(tǒng)的模式匹配算法。