大域バス結合モデルを用いた動的計画法の計算(2) : 最長共通部分系列と0-1ナップザック問題
スポンサーリンク
概要
- 論文の詳細を見る
並列的で高速な処理を実現する方式が多くの分野で強く求められている.多数の処理要素を相互に関連付け,並列的に動作させることによって高速な処理を実現しようとする方式は,高速で並列的な処理に対する重要な方式のひとつである.処理要素の相互関係を処理要素間の通信のための相互結合とみなすとき,処理要素とこれらを結合する配線より成る構成をそれぞれノードと結合線(辺)より成る相互結合モデルで表現することができる.これまで結合モデルとして格子,木,超立方体結合などの局所結合,バス結合を含む大域結合などが提案されてきた.また,線形結合や格子結合に大域バスを付加した結合モデルについては,線形または格子結合のみの構成よりも高速に解ける問題があることが示されてきた.大域バス結合または超立方体結合モデルを用いて問題を解くとき,大域バス結合の方が超立方体結合よりも速い場合,その逆の場合,計算時間のオーダーが等しい場合があり,2次元直交大域バス結合の方が高速に解くことのできる問題には動的計画法,データ転送操作などがある.本報告では,2次元直交大域パス結合モデル上で,動的計画法を用いて2系列の最長共通部分系列と0-1ナップザック問題を解く方法を導き,他の結合モデルと比較している.
- 一般社団法人情報処理学会の論文
- 1992-02-24
著者
関連論文
- 分散視覚化プログラム言語におけるインタラクティブ操作について
- 相互接続された異種計算機環境における並列計算のための負荷分散について
- 大域バス結合モデルを用いた動的計画法の計算(2) : 最長共通部分系列と0-1ナップザック問題
- 超立方体型結合モデルCubemat上での並列データ転送について
- 並列計真モデルCubematの二、三の特徴について
- 並列処理向きシステムCubematについて
- ブロック化法を用いたセル・システムの再構成について
- パーソナルコンピュータを用いた情報工学分野の文献検索システム