提出最优决策图算法，低成本高效评估带概率的布尔公式。
Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation
- 用分支定界法结合启发式变量选择，精确求解带成本的布尔函数评估
- 在随机实例上验证可扩展性，贪心束搜索变体实现效率与质量平衡
- 首次解决通用情形下的精确算法问题，适合高成本信息决策场景
在许多决策场景中，获取信息具有不同成本。本文研究如何构建确定性评估策略，在变量成本和真值赋值概率分布下最小化命题公式的期望成本。提出一种带有变量选择启发式、剪枝和缓存的分支定界算法，据我们所知，这是该通用性水平下的首个实用精确算法。在随机实例上的实验展示了可扩展性，并量化了贪心束搜索变体的效率-质量权衡。此外还评估了一个结构化的心脏病诊断实例。最后，证明该问题是#P-难的，且属于PSPACE类。
原文摘要 · Abstract (English)
In many decision-making scenarios, acquiring information incurs different costs. We consider the problem of constructing a deterministic evaluation strategy that minimizes the expected cost of evaluating a propositional formula under variable costs and a probability distribution over truth assignments. We present a branch-and-bound algorithm with variable-selection heuristics, pruning, and caching. To the best of our knowledge, it is the first practical exact algorithm for this level of generality. Experiments on random instances demonstrate scalability and quantify the efficiency-quality trade-off of a greedy beam-search variant. We additionally evaluate a structured heart-disease diagnosis instance. Finally, we prove that the problem is $\#P$-hard and contained in $\mathrm{PSPACE}$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。