Bucket-Tree Based Algorithm for Automated Reasoning
Yuan Min, Chunling Hu, Xuegang Hu, Hongliang Yao · 2013
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.