3次元箱詰め問題に対する構築型解法の効率的実現法

HANDLE Web Site Open Access

Bibliographic Information

Other Title
  • 3ジゲン ハコズメ モンダイ ニ タイスル コウチクガタカイホウ ノ コウリツテキ ジツゲンホウ

Search this article

Abstract

3次元箱詰め問題に対する代表的な構築型解法として,deepest-bottom-left(DBL)法と3次元におけるbest-fit(3BF)法と呼ばれる2つの手法がある.本研究では,これらの構築型解法に対して,既存の手法と比べて理論計算量の少ない効率的な実現法を提案する.また,アルゴリズムの不要な探索を省略することで実計算時間を減らす工夫を加える.とくに,3BF法では,この目的を実現するために分枝限定法を活用する.このような工夫を加えた結果,大規模な問題例においても実用的な時間で解を得られることを計算実験により確認した.

情報処理学会研究報告Vol.2013-AL-144 No.16

Journal

Details

Report a problem

Back to top