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

スポンサーリンク

概要

• 論文の詳細を見る

• 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)評価するだけで最適解が求まるアルゴリズムを提案した.

• 一般社団法人情報処理学会の論文
• 1985-01-15

著者

• 佐藤 文孝

  (株)東芝青梅工場

• 岩根 雅彦

  豊田工業大学制御情報工学科

関連論文

• 高速2値イメージ圧縮伸張LSIの開発 : ファクシミリと画像一般 : 画像通信システム
• 低速小規模マイクロプロセッサを内蔵したサービスプロセッサ
• ある分割問題の動的計画法による高速アルゴリズム
• ある種の割当て問題における解法について
• マイクロ命令の実行時間分布に基づく最適マシンサイクル時間の決定法
• 大形計算機における保全性設計

スポンサーリンク