動的計画法の並列計算 : 並列計算性とアルゴリズム

概要

論文の詳細を見る
動的計画法はすぐれた最適化手法の一つであるが, その計算時間は問題の規模とともに急速に増大する. そこで本研究では, 近年注目をあつめている並列計算方式を採用することで, 動的計画法計算の高速化をはかるための基礎として, その並列計算可能性とアルゴリズムについて考察した. まず標準的直列型問題の表解法について検討し, 状態および決定変数についての繰返し計算が, 完全に並列計算可能であり, 段についての繰返し計算も部分利得関数の同期をとることで並列性を得ることが可能であることがわかった. また, この問題の多段決定過程への分解過程に注目し, 小規模な動的計画問題を並列的に処理した後に, 原問題の解を求めうることから, 表解法とは異なる視点からの並列計算可能性を示した. さらに, 非直列型問題を反復的に解く発見的手法の一つについて考察し, 状態変換過程を制限する方法と組合せることで, 高い並列計算性を有する構造が得られ, そのアルゴリズムを示すことができた. 提案した表解法ならびに反復的解法の並列アルゴリズムを簡単な配分問題および一次方程式の数値計算に適用し, 放送型メモリ結合型並列計算機上で実行した結果, プロセッサ台数にほぼ比例した直線的な処理速度の向上が確認された. 以上の考察により, 動的計画法の高い並列計算性と, 示した並列計算アルゴリズムの有効性が確かめられた.
一般社団法人情報処理学会の論文
1985-09-15

動的計画法の並列計算 : 並列計算性とアルゴリズム

スポンサーリンク

概要

著者

関連論文

スポンサーリンク