...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Constraints >Arc-B-consistency of the Inter-distance Constraint
【24h】

Arc-B-consistency of the Inter-distance Constraint

机译：距离约束的Arc-B一致性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study the "inter-distance constraint," also known as the global minimum distance constraint, that ensures that the distance between any pair of variables is at least equal to a given value. When this value is 1, the inter-distance constraint reduces to the all-different constraint. We introduce an algorithm to propagate this constraint and we show that, when variables domains are intervals, our algorithm achieves arc-B-consistency. It provides tighter bounds than generic scheduling constraint propagation algorithms (like edge-finding) that could be used to capture this constraint. The worst case complexity of the algorithm is cubic but it behaves well in practice and it drastically reduces the search space. Experiments on special Job-Shop problems and on an Air-Traffic problem known as the "Runway Sequencing" problem.
机译：我们研究“距离间约束”，也称为全局最小距离约束，它可以确保任何一对变量之间的距离至少等于给定值。当该值为1时，距离间距约束减小为全差异约束。我们介绍了一种传播此约束的算法，并证明了当变量域为区间时，我们的算法实现了弧B一致性。与可用于捕获此约束的通用调度约束传播算法（如边缘查找）相比，它提供了更严格的边界。该算法的最坏情况复杂度是三次的，但是在实践中表现良好，并且极大地减少了搜索空间。针对特殊的“车间作业”问题和称为“跑道排序”问题的空中交通问题进行实验。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号