많은 의사결정 시나리오에서 정보를 획득하는 데에는 서로 다른 비용이 발생합니다. 우리는 변수 비용 (variable costs)과 진릿값 할당 (truth assignments)에 대한 확률 분포 하에서 명제 공식 (propositional formula)을 평가하는 데 드는 기대 비용을 최소화하는 결정론적 평가 전략 (deterministic evaluation strategy)을 구축하는 문제를 고려합니다. 우리는 변수 선택 휴리스틱 (variable-selection heuristics), 가지치기 (pruning), 그리고 캐싱 (caching)을 포함하는 분기 한정 알고리즘 (branch-and-bound algorithm)을 제시합니다. 우리가 아는 바로는, 이 알고리즘은 이 정도의 일반성을 가진 문제에 대한 최초의 실용적인 정확한 알고리즘 (exact algorithm)입니다. 무작위 인스턴스 (random instances)에 대한 실험은 확장성 (scalability)을 입증하며, 탐욕적 빔 서치 (greedy beam-search) 변형의 효율성-품질 트레이드오프 (efficiency-quality trade-off)를 정량화합니다. 추가적으로, 구조화된 심장병 진단 인스턴스를 평가합니다. 마지막으로, 우리는 이 문제가 #P-hard이며 $\mathrm{PSPACE}$에 포함됨을 증명합니다.