Rete算法的简化与实现

维普资讯 http://www.cqvip.com 科技信息　ｏ　ＩＴ技术论￣２０　ＳＣＩＥＮＣＥ＆ＴＥＣＨＮＯＬＯＧＹ　ＩＮＦＯＲＭＡＴＩＯＮ　２００８年第ｌ６期　Ｒｅｔｅ算法的简化与实现　关启学’王健波　ｆ１．沈阳理工大学信息科学与工程学院ｋＺ－７沈阳１１０１６８；２．沈阳运星自动化技术有限公司　Ｅ．－７－，￣ｌＩＢ　１１００１６）　【摘　要】提出了一种基于简化的Ｒｅｔｅ推理算法的ｊａｖａ实现，２，ｋ　ｒ￣有效地降低了专家系统中推理机的实现难度。　【关键词】Ｒｅｔｅ；ｊａｖａ；专家系统　Ｒｅｔｅ算法是・个用来实现产￡　式规则系统的高效模式匹配算法。　记的规则开始执行匹配操作，直至规则库中的所有的规则都进行过匹　该算法足由　内基美隆大学的Ｃｈａｒｌｅｓ　Ｌ．Ｆｏｒｇｙ在１９７４年发表的论文　配操作。　中所阐述的算法。Ｒｅｔｅ算法提供ｒ专家系统的一个高效实现。规则推　理引擎做为产牛式系统的・部分，当进行事实的断言时，包含三个阶　段：匹配、选择和执行，称做ｍａｔｃｈ—ｓｅｌｅｃｔ—ａｃｔ　ｃｙｃｌｅ。Ｒｅｔｅ算法可以对匹　配阶段进行商效实现。　３．实现　其简化后的Ｒｅｔｅ算法的ｉａｖａ［２￣言描述如下：　ＡｒｒａｙＬｉｓｔ＜Ｓｔｒｉｎｇ＞ｔｅｍｐＦａｃｔｓ＝ａｒｒａｙＴｏＬｉｓｔ（ｖＦａｃｔｓ）；　ＡｒｒａｙＬｉｓｔ＜Ｒｕｌｅ＞ｔｅｍｐＲｕｌｅｓ＝ｎｅｗ　ＡｒｒａｙＬｉｓｔ＜Ｒｕｌｅ＞０；　ｔｅｍｐＲｕｌｅｓ．ａｄｄＡｌｌ（ｒｕｌｅｓ）；　ｉｎｔ　ｉ＝Ｏ：　ＡｒｒａｙＬｉｓｔ＜Ｓｔｒｉｎｇ＞ｆｏｒｅＷａｒｅｓ＝ｎｕｌｌ；　１．Ｒｅｔｅ算法　Ｒｅｔｅ算法思想足利用了基于规则的专家系统所具有的时间冗余　性和规则中结构相似性…。Ｒｅｔｅ算法的实现是通过存储不断循环中匹　配过程的状态，并且，只重新汁剪在事实列表中发生了变化，又反映到　本次状态巾的变化。也就足说，如果在一次执行周期中，一组模式找到　三个所需事实中的两个．那么存下一周期中，就无需对已经找到的这　两个事实进行检查．只有第二个事实才是需要关注的。仅当添加或删　除事实的时候，匹配过程的状态才被更新。如果添加，删除事实的数量　与事实和模式的总数相比很小，那么匹配过程会很快进行。最坏的情　况是　如果所有的事实都改变了。那么所有的事实将与所有的模式进　行匹配。如果仅是事实列表进行更新，那么每条规则必须记住已与之　匹配的事实。也就是说，如果一个新的事实与规则的第三个模式相匹　配．那么头两个模式匹配信息必须存在以完成匹配过程。这种状态信　息指出了与某一规则巾前面的模式相匹配的事实。它以规则的第一个　模式为开始，以任一模式为结束。凶此，一条有三个模式的规则对第一　个模式，第一和第二个模式及第一，第二，第三模式都有部分匹配。一　条规则的所有模式的部分匹配也是一个激活。另一种存储的状态信息　称为模式　配。当一个事实满足了侄一规则中的单个模式而不需考虑　在其他模式巾可能会限制　配过程的变量时．则出现的就是模式匹　配。　ｗｈｉｌｅ（ｉ＜ｔｅｍｐＲｕｌｅｓ．ｓｉｚｅ（））｛　ｆｏｒｅＷａｒｅｓ＝ｔｅｍｐＲｕｌｅｓ．ｇｅｔ（ｉ）．ｇｅｔＦｏｒｅＷａｒｅ０；　ｉｆ（ｔｅｍｐＦａｃｔｓ．ｃｏｎｔａｉｎｓＡｌｌ（ｆｏｒｅＷａｒｅｓ））｛　ｔｅｍｐＦａｃｔｓ．ａｄｄ（ｔｅｍｐＲｕｌｅｓ．ｇｅｔ（ｉ）．ｇｅｔＨｉｎｄＷａｒｅ０）；　ｔｅｍｐＲｕｌｅｓ．ｒｅｍｏｖｅ（ｉ）；　ｉ＝Ｏ：　】　ｅｌｓｅ｛　＋＋ｉ：　】　】　ｔｅｍｐＦａｃｔｓ．ｔｒｉｍＴｏＳｉｚｅ０；　ｔｅｍｐＦａｃｔｓ．ｒｅｔａｉｎＡｌｌ（ｒｅｓｕｈＦａｃｔｓ）；　ｒｅｔｕｒｎ　ｔｅｍｐＦａｃｔｓ；　参数说明：　ｔｅｍｐＦａｃｔｓ：全局数据库中的事实集合；　ｔｅｍｐＲｕｌｅｓ：待匹配的规则集合。　２．简化原理　由于Ｒｅｔｅ算法的一般实现原则是通过记录推理过程中的事实列　４．结束语　本文从专家系统推理机的实现角度提出了一种基于Ｒｅｔｅ的简化算　表变化和规则模式的变化提高推理效率，但占用了大量的内存空间，　法，从而有效地降低了推理机的实现难度，同时也提高了推理速度。　而且算法设计与实现都很复杂．不利于推理算法的教学。所以有必要　对Ｒｅｔｅ算法加以简化．即只需记录事实列表的状态变化，而不记录规　【参考文献】　［１］Ｆｏｒｇ，Ｃ．Ｌ．１９８２．Ｒｅｔｅ：ａ　ｆａｓｔ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　ｍａｎｙ　ｐａｔｔｅｒｎ／ｍａｎｙ　ｏｂｊｅｃｔ　ｐ￣ｔｅｍ　则前件中模式ｐＥ配的情况，从而降低了实现和设计难度。　ｔｃｈ　ｐｒｏｂｌｅｍ．Ａｒｉｔｉｉｅａｆｌ　ｉｎｔｅｌｌｉｇｅｎｃｅ，１９８２，１９（１）：１７—３７．　经简化的Ｒｅｔｅ算法的基本思想是：从规则库中的第一条规则开　ｍａ所有规则都进行＿『　配操作后结束推理。在逐条规则匹配中。如果某　条规则匹配成功则标记该规则（避免再次被执行匹配操作），将该匹配　成功规则的结论事实加入到全局数据库中。再从规则库的第一条未标　Ｉ：基础知识［Ｍ］，北京：机械工业出版社，２００６．５．　　Ｓ．Ｈｏｍｔｍａｎｎ，Ｇａｒｙ　Ｃｏｍｅｌｌ著，叶乃文，邝劲筠等译．ＪＡＶＡ２核心技术卷　始匹配操作．直至规则库的最后一条规则结束推理过程，即规则库中　［２］Ｃａｙ［责任编辑：张新雷］　（上接第４５页）④对块状或颗粒状的物料，则取其浸出液进行测　到国家指定的废物库堆存。再封洞。并不时通过环境监测的方办法确　定。　定其对洞周围是否有污染。粉煤灰用于地基回填，路基及高路堤工程　⑧将样　或标准缓冲溶液分别倒人干燥、清洁的烧杯中，放人搅　应用和用作混凝土掺合料等。煤渣用于制砖和以渣代煤再燃烧。化工　拌棒．置于电磁撑拌器ｌ　，插入电极，启动电磁搅拌器。以适当的搅拌速　渣中硫铁矿渣制砖。电石渣用于筑路和中和酸性废水。化工渣中铬渣　度搅拌溶液　待读数稳定后．读取并记录ｐＨ值。　３．５数据处理　报告　位，取算数平均值报告数据结果。　（２）当标准差超过规定范围时，必须分析并报告原因。　（属危险废物）毒性较大，除一部分用于玻璃着色剂外，大部分堆存在　些人迹罕至的山乡谷地或废物厂矿院内。通过综合利用，使工业固　一（１）每个样品至少做　次平行试验，其标准差不得超过－＋０．１５ｐＨ单　体废物资源化、减量化，避免对环境造成危害是我们国家大力推广的　环保措施。但是，加强对固体废物的腐蚀性的监测鉴别仍是我们长期　不能松懈的工作，只有搞好监测，才能防患于未然，确保我们了孙后代　四　结论　这几年来．随着科学研究的发展．对有色金属固体废物的综合利　用进入了全新时代。如冶炼淤经水淬后用作水泥掺合料，生产水泥，其　破碎粉渣用于筑路。冶炼渣巾铍渣（属危险废物）毒性较大，大部分送　有一个良好的生活环境。ｌ　［责任编辑：汤静］