Abstract: It always produces redundant computation when applying Belief Propagation(BP) algorithm to MEU problem. To improve such a situation, an optimization to BP is proposed that reuse last influent result instead of recomputing the marginal probability if the node is not significantly affected by the change of condition, and prove is given to confirm that the optimization does not significantly affect the influence result. A simulation by applying the optimized algorithm to combinatorial auctions gives the result that compare to the standard BP algorism, optimized algorism efficiently improve the efficiency of inference without significantly affect the quality of the solutions.

Key words: repeated inference, Belief Propagation(BP) algorithm, message propagation, efficient inference, combinatorial auctions

摘要： 使用BP算法求解效用最大化问题时，容易产生大量冗余计算。为此，对标准BP算法进行优化，在推理过程中，对一些受限定条件影响较小的结点，直接利用前次推理结果，无需重新计算其边缘概率，并证明这种优化不会显著影响推理结果。将该算法应用于组合竞拍模型进行测试。仿真结果表明，相对于标准BP算法，该优化算法能提升求解效用最大化问题时的收敛效率。

关键词: 多次推理, BP算法, 消息传播, 有效推理, 组合竞拍

CLC Number: 

• TP311.52