基于代价模型的RETE优化算法  

Improved RETE Optimized Algorithm Based on Cost Model

作　　者：陈帅均 蒋平[1] 吴钦章[1] 

机构地区：[1]中国科学院光电技术研究所,成都610209 [2]中国科学院大学,北京100049

出　　处：《光电工程》2014年第7期44-49,共6页Opto-Electronic Engineering

基　　金：国家高新技术研究发展863计划资助项目

摘　　要：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＆#39;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.

关 键 词：RETE匹配算法 代价模型 基于规则推理 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] TP391[自动化与计算机技术—计算机科学与技术]