光电工程
光電工程
광전공정
OPTO-ELECTRONIC ENGINEERING
2014年
7期
44-49
,共6页
RETE匹配算法%代价模型%基于规则推理
RETE匹配算法%代價模型%基于規則推理
RETE필배산법%대개모형%기우규칙추리
RETE match algorithm%cost model%rule-based reasoning
RETE 匹配算法是基于规则推理系统中的经典高效算法,但是在飞行器评估这种规则和事实数量较多的系统,推理效率并不高,因为在模式匹配中,join 操作的开销与事实的平方成正比。事实和规则数量较多时,产生的中间匹配信息大大增加,增加了时间复杂度和空间复杂度,严重降低了推理效率。针对飞行器评估系统的特点,本文分析了优化RETE拓扑结构是提高推理效率的关键,然后提出了基于代价模型的RETE优化算法,该算法可以自动寻找最优的RETE拓扑结构,减少了join中间结点的数据,大大降低RETE算法的时间复杂度和空间复杂度。经实验测试,基于代价模型的RETE算法在飞行器评估系统中的运行效率较高,满足飞行器评估的需求。
RETE 匹配算法是基于規則推理繫統中的經典高效算法,但是在飛行器評估這種規則和事實數量較多的繫統,推理效率併不高,因為在模式匹配中,join 操作的開銷與事實的平方成正比。事實和規則數量較多時,產生的中間匹配信息大大增加,增加瞭時間複雜度和空間複雜度,嚴重降低瞭推理效率。針對飛行器評估繫統的特點,本文分析瞭優化RETE拓撲結構是提高推理效率的關鍵,然後提齣瞭基于代價模型的RETE優化算法,該算法可以自動尋找最優的RETE拓撲結構,減少瞭join中間結點的數據,大大降低RETE算法的時間複雜度和空間複雜度。經實驗測試,基于代價模型的RETE算法在飛行器評估繫統中的運行效率較高,滿足飛行器評估的需求。
RETE 필배산법시기우규칙추리계통중적경전고효산법,단시재비행기평고저충규칙화사실수량교다적계통,추리효솔병불고,인위재모식필배중,join 조작적개소여사실적평방성정비。사실화규칙수량교다시,산생적중간필배신식대대증가,증가료시간복잡도화공간복잡도,엄중강저료추리효솔。침대비행기평고계통적특점,본문분석료우화RETE탁복결구시제고추리효솔적관건,연후제출료기우대개모형적RETE우화산법,해산법가이자동심조최우적RETE탁복결구,감소료join중간결점적수거,대대강저RETE산법적시간복잡도화공간복잡도。경실험측시,기우대개모형적RETE산법재비행기평고계통중적운행효솔교고,만족비행기평고적수구。
The RETE matching algorithm was a classical algorithm in the rule-based reasoning system, but when the number of rules and facts increased in the knowledge base, the generated intermediate match information greatly increased too, resulting to the large time complexity and space complexity, severely reduced the reasoning efficiency. To address this issue, this paper compared several improvement strategies of RETE algorithm, and optimization algorithm was proposed based on RETE cost model. The algorithm can automatically find the optimal RETE topology, reduce intermediate nodes, and greatly reduce RETE algorithm's time complexity and space complexity. The experiment shows that the running cost of optimized RETE algorithm is only about half the time than before optimization, and the reasoning efficiency is improved.