一种基于桶树的自动推理问题求解算法  

Bucket-Tree Based Algorithm for Automated Reasoning

作　　者：袁暋[1] 胡春玲[1] 胡学钢[2] 姚宏亮[2] 

机构地区：[1]合肥学院网络与智能信息处理重点实验室,合肥230602 [2]合肥工业大学计算机与信息学院,合肥230009

出　　处：《计算机科学》2013年第1期211-217,共7页Computer Science

基　　金：国家自然科学基金(60975034);安徽省教育厅自然科学一般项目(KJ2010B177);合肥学院人才科研基金(13RC01)资助

摘　　要：桶消元和连接树推理算法是处理自动推理问题的两种常用的推理算法。针对连接树推理算法中消息传播效率问题,提出了一种能有效进行消息传播的连接树推理算法JTR。针对桶消元推理算法BE处理多任务的自动推理问题效率低下的问题,采用连接树结构和连接树推理算法JTR的消息传播方式对桶消元算法BE进行改进和扩展,提出了一种桶树推理算法BJTR。通过对算法BE、BTE和BJTR的时空性能分析发现:与同类算法BTE相比,算法BJTR在空间略有下降的情况下提高了时间性能;针对多任务的自动推理问题,与桶消元推理算法BE相比,BJTR算法的空间略有下降,时间性能得到明显提高;并通过实例和实验进一步验证了算法BJTR针对多任务的自动推理任务具有良好的时间性能。The bucket elimination algorithm and the join-tree reasoning algorithm are popularly used for automated reasoning.To improve the efficiency of message propagation in the join-tree reasoning algorithm,a new join-tree reasoning algorithm（called JTR） was proposed.Meanwhile,to handle the inefficiency of multi-task automated reasoning of the bucket elimination algorithm BE,a bucket-tree reasoning algorithm（named as BJTR）,based on the join-tree structure and message propagation mode in JTR,was further developed from BE.Our study shows that in comparison with the BTE algorithm,the proposed algorithm BJTR improves the time performance while space performance decreases a little.Furthermore,as compared with BE,BJTR effectively reduces the demand on time-overhead while maintaining a slightly low space performance in the handling of multi-task automated reasoning.Meanwhile,both examples and experi-ments demonstrate that BJTR algorithm has an obvious advantage in the time performance for multi-task reasoning.

关 键 词：自动推理 多任务 桶消元 连接树 桶-树 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]