ある分割問題の動的計画法による高速アルゴリズム

• Item type: Journal(1)
• 公開日: 1985-01-15
• タイトル: ある分割問題の動的計画法による高速アルゴリズム
• タイトル / 言語: en
• タイトル: A Fast Algorithm for a Partition Problem Using Dynamic Programming
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 豊田工業大学制御情報工学科
• 著者所属: （株）東芝青梅工場
• 著者所属(英): en
• 著者所属(英): Department of Information and Control Engineering, Toyota Technological Institute
• 著者所属(英): en
• 著者所属(英): Ome Works, Toshiba Corporation
• 著者名: 岩根, 雅彦; 佐藤, 文孝
• 著者名(英): Masahiko, Iwane; Fumitaka, Sato
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: n個の要素からなる集合Aの各要素α(i)に二つの自然数s(a(i)) q(a(i))が与えられ またmは与えられた定数とする.そして集合Aのm個の部分集合A(1) A(m)を取り出したとき 部分集合A(j)のなかのs(a(i))の最大のものをs(j) A(j)のなかのq(a(i))の和をq(j)とする.目的関数u=s(1)q(1)+s(2)q(2)+…+s(m)q(m)を最小にし A=A(1)∪A(2)∪…∪A(m)となるようなm個の部分集合を求める問題を考える.この問題の最適解の性質を調べて定理としてまとめ これらの定理から (1)目的関数の評価回数がC(n-1 m-1)なる問題に変換できること (2)この変換問題に対して順方向の最適性の原理が成り立つこと (3)最適解の範囲が限定できることを示した.この変換問題に動的計画法を適用し さらに最適解の縄囲の限定による層別化により 目的関数を多くとも(m-2)*n**2/2-m*(m-4)*n/2+m*(m**2-6*m十5)/6回(m⩾2)評価するだけで最適解が求まるアルゴリズムを提案した.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 26, 号 1, p. 189-194, 発行日 1985-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764