...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>The Journal of Artificial Intelligence Research >From Support Propagation to Belief Propagation in Constraint Programming
【24h】

From Support Propagation to Belief Propagation in Constraint Programming

机译：从支持传播到约束编程中的信仰传播

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The distinctive driving force of constraint programming to solve combinatorial problems has been a privileged access to problem structure through the high-level models it uses. From that exposed structure in the form of so-called global constraints, powerful inference algorithms have shared information between constraints by propagating it through shared variables’ domains, traditionally by removing unsupported values. This paper investigates a richer propagation medium made possible by recent work on counting solutions inside constraints. Beliefs about individual variable-value assignments are exchanged between contraints and iteratively adjusted. It generalizes standard support propagation and aims to converge to the true marginal distributions of the solutions over individual variables. Its advantage over standard belief propagation is that the higher-level models featuring large-arity (global) constraints do not tend to create as many cycles, which are known to be problematic for convergence. The necessary architectural changes to a constraint programming solver are described and an empirical study of the proposal is conducted on its implementation. We find that it provides close approximations to the true marginals and that it significantly improves search guidance.
机译：限制规划以解决组合问题的独特驱动力一直是通过它使用的高级模型来解决问题结构的特权访问。从所谓的全局约束形式的那种暴露的结构中，通过传统上通过删除不支持的值来传播，强大的推理算法通过传输通过共享变量的域来在约束之间共享信息。本文调查了最近在限制内解决方案的最新作品所获得的更丰富的传播介质。关于个体可变价值分配的信念在凝视和迭代调整之间交换。它概括了标准的支持传播，并旨在收敛到各个变量对解决方案的真实边缘分布。它的优势与标准信念传播的优势在于，具有大而大的级别模型（全局）约束的更高级模型不会倾向于创建多个周期，这已知已知对收敛有问题。描述了对约束编程求解器的必要架构改变，并对该提案进行了实证研究。我们发现它为真正的边际提供了密切的近似，并且它显着提高了搜索指导。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号