论文标题
RBF-HS：递归最佳首次击球套装搜索
RBF-HS: Recursive Best-First Hitting Set Search
论文作者
论文摘要
各种基于模型的诊断方案需要计算最优选的故障解释。但是，现有的算法是声音（即仅输出实际故障说明）并完成（即可以返回所有说明），但是，需要指数空间才能完成此任务。作为一种补救措施，我们提出了两种新型的诊断搜索算法，称为RBF-HS（递归最佳优先击球设置搜索）和HBF-HS（Hybrid最佳优先击球套件搜索），这些搜索基于启发式搜索域的尝试和测试的技术。 RBF-HS可以在线性空间范围内以最佳阶段的方式列举任意预定义的有限数量的故障解释，而无需牺牲理想的声音或完整性属性。 HBF-HS的想法是在运行时优化和不超过可用内存的限制空间消耗之间取舍。 在有关现实世界诊断病例的广泛实验中，我们将我们的方法与Reiter的HS-Tree进行了比较，Reiter的HS-Tree是一种最新的方法，提供了相同的理论保证，并且与建议的算法一样一般（适用）。 For the computation of minimum-cardinality fault explanations, we find that (1) RBF-HS reduces memory requirements substantially in most cases by up to several orders of magnitude, (2) in more than a third of the cases, both memory savings and runtime savings are achieved, and (3) given the runtime overhead is significant, using HBF-HS instead of RBF-HS reduces the runtime to values comparable with HS-Tree while keeping the used内存合理地界定。当计算最可能的故障解释时，我们观察到RBF-HS倾向于在运行时开销或多或少地交易内存。同样，HBF-HS被证明是一种合理的补救措施，可以降低运行时，同时遵守可行的内存界限。
Various model-based diagnosis scenarios require the computation of most preferred fault explanations. Existing algorithms that are sound (i.e., output only actual fault explanations) and complete (i.e., can return all explanations), however, require exponential space to achieve this task. As a remedy, we propose two novel diagnostic search algorithms, called RBF-HS (Recursive Best-First Hitting Set Search) and HBF-HS (Hybrid Best-First Hitting Set Search), which build upon tried and tested techniques from the heuristic search domain. RBF-HS can enumerate an arbitrary predefined finite number of fault explanations in best-first order within linear space bounds, without sacrificing the desirable soundness or completeness properties. The idea of HBF-HS is to find a trade-off between runtime optimization and a restricted space consumption that does not exceed the available memory. In extensive experiments on real-world diagnosis cases we compared our approaches to Reiter's HS-Tree, a state-of-the-art method that gives the same theoretical guarantees and is as general(ly applicable) as the suggested algorithms. For the computation of minimum-cardinality fault explanations, we find that (1) RBF-HS reduces memory requirements substantially in most cases by up to several orders of magnitude, (2) in more than a third of the cases, both memory savings and runtime savings are achieved, and (3) given the runtime overhead is significant, using HBF-HS instead of RBF-HS reduces the runtime to values comparable with HS-Tree while keeping the used memory reasonably bounded. When computing most probable fault explanations, we observe that RBF-HS tends to trade memory savings more or less one-to-one for runtime overheads. Again, HBF-HS proves to be a reasonable remedy to cut down the runtime while complying with practicable memory bounds.
