• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Automated Planning and Scheduling(ICAPS 2006); 2006; >Optimal Rectangle Packing: A Meta-CSP Approach
【24h】

Optimal Rectangle Packing: A Meta-CSP Approach

机译：最佳矩形包装：Meta-CSP方法

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

摘要

We present a new approach to optimal rectangle packing, an NP-complete problem that can be used to model many simple scheduling tasks. Recent attempts at incorporating artificial intelligence search techniques to the problem of rectangle packing have focused on a CSP formulation, in which partial assignments are defined to be the fixed placement of a subset of rectangles. Our technique takes a significant departure from this search space, as we instead view partial assignments as subsets of relative pairwise relationships between rectangles. This approach recalls the meta-CSP commonly constructed in constraint-based temporal reasoning, and is thus a candidate for several pruning techniques that have been developed in that field. We apply these to the domain of rectangle packing, and develop a suite of new techniques that exploit both the symmetry and geometry present in this particular domain. We then provide experimental results demonstrating that our approach performs competitively compared to the previous state-of-the-art on a series of benchmarks, matching or surpassing it in speed on nearly all instances. Finally, we conjecture that our technique is particularly appropriate for problems containing large rectangles, which are difficult for the fixed-placement formulation to handle effi-ciendy.
机译：我们提出了一种新的方法来优化矩形包装，这是一个NP完全问题，可以用来对许多简单的调度任务进行建模。最近将人工智能搜索技术结合到矩形包装问题中的尝试集中在CSP公式上，其中将部分分配定义为矩形子集的固定位置。我们的技术与该搜索空间大相径庭，因为我们将部分分配视为矩形之间相对成对关系的子集。这种方法可以回忆起通常在基于约束的时间推理中构建的meta-CSP，因此是该领域已开发的几种修剪技术的候选方法。我们将它们应用于矩形填充的领域，并开发出一套利用这一特定领域中存在的对称性和几何形状的新技术。然后，我们提供实验结果，证明我们的方法在一系列基准上与以前的最新技术相比具有竞争优势，并且在几乎所有情况下其速度都达到或超过了它。最后，我们推测我们的技术特别适用于包含大矩形的问题，而这些问题对于固定放置的公式难以处理有效的问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号