長方形配置問題に対するbest-fit法の効率的な実現

• Item type: SIG Technical Reports(1)
• 公開日: 2007-09-21
• タイトル: 長方形配置問題に対するbest-fit法の効率的な実現
• タイトル / 言語: en
• タイトル: The best-fit heuristic for the rectangular strip packing problem: an efficient implementation
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属: 名古屋大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): University of Tokyo
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者名: 今堀, 慎治; 柳浦睦憲
• 著者名(英): Shinji, Imahori; Mutsunori, Yagiura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 長方形配置問題は 与えられた長方形を重なりなく できる限り密に配置することを目的とする問題である.本問題に対する発見的解法の一つとして Burkeらによって提案されたbest-fit 法[Operations Research 52 (2004) 655--671]があり その性能が広く注目されている.本研究では best-fit法の効率的な実現法を提案し 計算量の観点での最適性を示す.我々の実現法は 長方形数をnとすると O(n)の領域と O(n log n)の計算量を必要とする.また 数値実験を通して best-fit 法の実用性について論じる.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We investigate the best-fit heuristic algorithm by Burke et al. [Operations Research 52 (2004) 655--671] for the rectangular strip packing problem. For its simplicity and good performance, the best-fit heuristic has become one of the most significant algorithms for the rectangular strip packing. In this paper, we propose an efficient implementation of the best-fit heuristic that requires linear space and O(n log n) time, where n is the number of rectangles. We prove that this time complexity is optimal, and show practical usefulness of our implementation via computational experiments.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2007, 号 92(2007-AL-114), p. 65-72, 発行日 2007-09-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会