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

• Item type: Journal(1)
• 公開日: 1985-09-15
• タイトル: 動的計画法の並列計算 －並列計算性とアルゴリズム－
• タイトル / 言語: en
• タイトル: Parallel Computation Algorithms of Dynamic Programming
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 神戸大学工学部システム工学科／現在 アイビーエム
• 著者所属: 神戸大学工学部システム工学科
• 著者所属: 日本電気（株）基本ソフトウェア開発本部／研究当時 神戸大学工学部システム工学科
• 著者所属: 神戸大学工学部システム工学科
• 著者所属: 岡山理科大学／研究当時 神戸大学大学院
• 著者所属: 日本アイビーエム（株）藤沢研究所／研究当時 神戸大学大学院
• 著者所属(英): en
• 著者所属(英): Department of Systems Engineering, Faculty of Engineering, Kobe University
• 著者所属(英): en
• 著者所属(英): Department of Systems Engineering, Faculty of Engineering, Kobe University
• 著者所属(英): en
• 著者所属(英): Fundamental Software Division, NEC Corporation
• 著者所属(英): en
• 著者所属(英): Department of System Engineering, Faculty of Engineering, Kobe University
• 著者所属(英): en
• 著者所属(英): Okayama University of Science
• 著者所属(英): en
• 著者所属(英): Fujisawa Research Institute, IBM Japan Ltd
• 著者名: 瀬口, 靖幸; 田中, 正夫; 中島, 利朗; 金田, 悠紀夫; 小畑, 正貴; 西野, 佐登史
• 著者名(英): Yasuyuki, Seguchi; Masao, Tanaka; Toshiroh, Nakajima; Yukio, Kaneda; Masaki, Kohata; Satoshi, Nishino
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 動的計画法はすぐれた最適化手法の一つであるが その計算時間は問題の規模とともに急速に増大する.そこで本研究では 近年注目をあつめている並列計算方式を採用することで 動的計画法計算の高速化をはかるための基礎として その並列計算可能性とアルゴリズムについて考察した.まず標準的直列型問題の表解法について検討し 状態および決定変数についての繰返し計算が 完全に並列計算可能であり 段についての繰返し計算も部分利得関数の同期をとることで並列性を得ることが可能であることがわかった.また この問題の多段決定過程への分解過程に注目し 小規模な動的計画問題を並列的に処理した後に 原問題の解を求めうることから 表解法とは異なる視点からの並列計算可能性を示した.さらに 非直列型問題を反復的に解く発見的手法の一つについて考察し 状態変換過程を制限する方法と組合せることで 高い並列計算性を有する構造が得られ そのアルゴリズムを示すことができた.提案した表解法ならびに反復的解法の並列アルゴリズムを簡単な配分問題および一次方程式の数値計算に適用し 放送型メモリ結合型並列計算機上で実行した結果 プロセッサ台数にほぼ比例した直線的な処理速度の向上が確認された.以上の考察により 動的計画法の高い並列計算性と 示した並列計算アルゴリズムの有効性が確かめられた.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 26, 号 5, p. 824-830, 発行日 1985-09-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764