動的計画法に基づく資源配分並列アルゴリズム

程 翔  相原 玲二  山下 雅史  阿江 忠  

誌名
電子情報通信学会論文誌 D   Vol.J71-D   No.4   pp.615-625
発行日: 1988/04/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 


本文: PDF(790.7KB)>>
論文を購入




あらまし: 
資源配分問題は動的計画法が適用できる代表的な最適化問題であり,多くの実用的な最適化問題をこの問題に帰着することができる.しかし,動的計画法を利用して単一プロセッサ上でこの問題を解決するのに通常Omn2)の時間がかかる(但し,整数値上の資源配分問題とし,mを活動の個数,nを資源の総量とする)ことが知られているので,問題の規模が大きくなると共に,多項式時間とはいえ計算時間は増大する.従って,動的計画法を利用して,大規模な資源配分問題を解くために更に高速なアルゴリズムの開発が望まれる.本論文では,n+1台のプロセッサから構成される1次元プロセッサアレー上においてOmn)時間でこの問題を解決するアルゴリズムと(n+1)(n+2)/2台のプロセッサから構成される2次元三角格子結合のプロセッサアレー上においてこの問題をOmn log m)時間で解くアルゴリズムをそれぞれ提案する.また,1次元プロセッサアレー上での実験結果も示す.