In several applications of automatic diagnosis and active learning a central
problem is the evaluation of a discrete function by adaptively querying the
values of its variables until the values read uniquely determine the value of
the function. In general, the process of reading the value of a variable might
involve some cost, computational or even a fee to be paid for the experiment
required for obtaining the value. This cost should be taken into account when
deciding the next variable to read. The goal is to design a strategy for
evaluating the function incurring little cost (in the worst case or in
expectation according to a prior distribution on the possible variables'
assignments). Our algorithm builds a strategy (decision tree) which attains a
logarithmic approxima- tion simultaneously for the expected and worst cost
spent. This is best possible under the assumption that $P \neq NP.$

通过自适应查询变量值评估离散函数的策略的设计，该算法可以同时实现预期和最坏情况下的对数逼近，即使在计算费用较高的情况下，该算法也可以作为一种自动诊断和主动学习的解决方案。