WEKO3
アイテム
最適木取りアルゴリズムに関する研究
http://hdl.handle.net/10076/12948
http://hdl.handle.net/10076/12948cce070f8-66dd-4bfb-9751-95f04f390b93
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
2011M267.pdf (142.2 kB)
|
|
| Item type | 学位論文 / Thesis or Dissertation(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-06-11 | |||||||
| タイトル | ||||||||
| タイトル | 最適木取りアルゴリズムに関する研究 | |||||||
| 言語 | ja | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_46ec | |||||||
| 資源タイプ | thesis | |||||||
| 著者 |
柳島, 弘章
× 柳島, 弘章
|
|||||||
| 抄録 | ||||||||
| 内容記述タイプ | Abstract | |||||||
| 内容記述 | 住宅等を建築する際に使用する数十から数百本の柱（建築パーツ）は前もって材木から一括して切り出され，このときに木材の不用な余りが発生する．この余りを最小にする柱の組み合わせを求めるアルゴリズムは建築パーツ切り出し問題と呼ばれ，高速で最適解を求める手法が実際の現場で求められている．建築パーツ切り出し問題は組み合わせ最適化問題の可変サイズビンパッキング問題と等価であり，NP 完全問題として知られている[FL86]．従って，この問題は入力サイズが大きくなると現実的な時間で最適解を計算することが難しくなる．しかし，建築パーツ切り出し問題のような実際の問題への適用では現実的な時間で計算できる場合が多くあり，最適化アルゴリズムを高速化して，より多くの入力例に対して最適解が得られるように改善することは，有益である．先行研究として野呂の研究[野呂10] がある．野呂はパターンクラスの概念の導入やハッシュ表を利用した分枝限定法を用いた高速最適化アルゴリズム，及び，近似アルゴリズムとして，可変サイズビンパッキング問題に対する漸近的多項式時間近似スキームの考え方を応用した高精度近似アルゴリズムを与えた．ここで，パターンとは，材木とそこから切り出される柱のリストのペアであり，それぞれのアルゴリズムはパターンのリスト（即ち，柱の切り出し方）を出力する．本研究ではまず野呂の高速最適化アルゴリズムにおいて提案されたパターンクラスの概念をより一般化することによりパターンクラス数を減らすことに成功し，分枝限定法における探索節点数が削減できることを実証した．次に，分枝限定法で求めた部分最適解をハッュ表に保存して再利用する動的ハッシュ法を適用した．また，部分最適解が得られなかった場合にはハッシュ表に枝刈り可能な情報を格納し，以後，その値を利用して枝刈りを行うようにアルゴリズムを改善した．さらに，入力から生成されるパターンに対して分割可能なパターンという概念を導入して，パターンの総数及びその探索範囲を大幅に削減した．これらの新しい手法を導入することにより野呂らの高速最適化アルゴリズムを高速化すると共に，現実的な時間で最適解を計算可能な入力のサイズを広げた新しいアルゴリズムを提案した．本研究では提案した手法の有効性を確認するために，本アルゴリズムを実装して実際の現場で使われているデータ（49 例）を用いて先行研究のアルゴリズムと計算時間と探索接点数を比較する実験を行った． 49 例中13 例に改善が見られた．そのなかで表.1 で示す3 例については大幅な改善を確認することができ，本手法の有効性を実証した． | |||||||
| 内容記述 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 三重大学大学院工学研究科博士前期課程情報工学専攻 | |||||||
| 内容記述 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 1, 23 | |||||||
| 書誌情報 |
発行日 2011-01-01 |
|||||||
| フォーマット | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | application/pdf | |||||||
| 著者版フラグ | ||||||||
| 出版タイプ | VoR | |||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||
| 出版者 | ||||||||
| 出版者 | 三重大学 | |||||||
| 修士論文指導教員 | ||||||||
| 寄与者識別子Scheme | WEKO | |||||||
| 寄与者識別子 | 23037 | |||||||
| 姓名 | 大山口, 通夫 | |||||||
| 言語 | ja | |||||||
| ノート | ||||||||
| 資源タイプ（三重大） | ||||||||
| Master's Thesis / 修士論文 | ||||||||
