arXiv ID:
2606.24672
arXiv 提交日期: 2026-06-23
随机布尔函数评估的最优成本决策图 / Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation
1️⃣ 一句话总结
本文研究在不确定性条件下如何用最低期望成本评估一个布尔逻辑公式,提出了一种首个实用的精确求解算法,通过分支定界、启发式搜索和缓存技术,在随机测试和心脏诊断实例中验证了其有效性,并证明了该问题的计算复杂度属于#P-hard到PSPACE之间。