...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>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 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号