並列ソフトウェアコンテストPSC'97入賞アルゴリズムの紹介

山村周史，奥村晃生，下村武，布目淳

1997年5月29日

問題

m個のナップサック問題を解き，各問題i (0 ≦ i ≦ m) で与えられるナップサックに詰め込んだ荷物の価値と総実行時間を競う．

得点規則

ある制限時間内にm個の問題をすべて解き， m+1種類の持ち点の合計が多い順に順位をつける．

問題の解について，価値の大きい順に10点〜1点
実行時間について，いずれかの問題に関して1点以上の得点を得た作品に関して，時間の短い順に10点〜1点

問題に関する条件

問題数は最大10
制限時間は1分以上

使用アルゴリズム

問題の規模に応じて2つのアルゴリズムのどちらかを選択

動的計画法
- 利点
  - 確実に最適解を求めることが可能．
  - ナップサックの制限重量や荷物数をもとに計算時間を予測できる．
- 欠点
  - 使用メモリ量や制限時間のために大規模な問題への適用が困難．
DDD(Dynamic Decision Diagram)法

DDD法

荷物を1つずつ添加しながら2分木構造を動的に成長させていく手法
完成した2分木を末端ノードから辿ることで最適解を求めることが可能

利点
- 末端ノード数を制限することで大規模な問題にも対応可能．
- 使用メモリ量が少ない．
欠点
- 最適解を求めるための末端ノード数の設定が困難．

上図は，表のように与えられた3つの品物の最適解を求める場合の DDD生成手順を示している(ただし，制限重量w=4)．

初期状態では，rootノード(節)と末端ノードの2ノードから成る．末端ノードは，品物の合計重量と合計価値の2種類の数値情報を持つ．図の末端ノードの上半分が合計重量，下半分が合計価値である．

まず，品物x₁を追加した場合のDDDを生成する．ノードx₁を rootノードと末端ノードの間(リンク)に割り込ませるようにして追加する．このとき図のように新たに2つノードが生成される．新たに生成された2個のノードのうち，左側が「品物x₁を 入れない場合の末端ノード」であり，右側が「品物x₁を入れた場合の末端ノード」の意味を持つ．

同様にして，末端ノードと品物ノードとの間に順に品物を追加し新たなノードを次々に生成していく．

このとき，品物x₁，x₂を追加した場合のように合計重量がナップサックの制限重量を越えた場合にはそのリンクはNULLとなり新たな末端ノードは生成されない．

このようにして，すべての品物を追加すると下図のようになる．

最後に，最適解を求める場合は末端ノードの中で最も価値の大きいノードを探し，そのノードからrootノードに向かってリンクを辿れば良い．

このアルゴリズムを用いれば末端となるノードの数は高々 ナップサックの制限重量+1となり，通常の2分木構造を作成した場合のようにノード数が爆発的に増加するようなことはない．また，1つの品物を追加するときの新たに処理するノード数は(その時点で生成されている末端ノードの個数)回で済む．この点で，通常の動的計画法よりも優れている．

最大価値選択

上で示した方法でDDDを作成すると，荷物数が非常に多い場合にノードの数が多くなりすぎる．本アルゴリズムでは，DDDの作成時に幾つかのノードを 最大価値選択によってグループ化を行うことでノード数の爆発を回避する．

下図では，ナップサックの制限重量が11の場合の末端ノードの状態を示している．ここでは最大価値選択を行うことにより，最大グループ数を2個に制限する．まず，重量0〜5までの各ノードに対し，(Value/Weight)の値を計算し，この値が最も大きいノード(この図ではWeight=2のノード)をそのグループの代表ノードとする．同様に，重量6〜11までのグループについても計算を行い， Weight=10のノードを代表ノードに設定する．

最大価値選択を行うことにより，最大ノード数(グループ数)を制限できるが， DDD作成時にノード情報を破棄するために，グループ数を制限しすぎると，解の質が低下する． DDD法では，グループ数の設定が重要である．

問題の荷物数とグループ数

我々のチームでは，与えられた予選問題についてグループ数を変化させ，得られる解の質と実行時間の関係を調査した．この結果，問題で与えられる荷物数に対して使用するグループ数を下図のように決定することにした．

問題番号	1	2	3	4	5	6	7	8	9
荷物数	200	200	200	300	300	42	100	100	500
ナップサックの大きさ	227800	121700	52400	334200	181050	14320	28084	28205	700544
本選で用いたグループ数	38386	38386	38386	25281	25281	191555	78386	78386	14938
最適なグループ数	832	1255	4764	9033	6706	754	28085	3526	4766
実行時間(sec)	0.53	0.79	3.26	8.99	6.60	0.09	7.40	0.91	6.68

Sun Ultra1(167MHz),Memory 128MB

問題6〜8を動的計画法で解いた場合，

問題番号	6	7	8
実行時間(sec)	0.91	3.59	3.56

問題点

近似解の精度とグループ数の関連性
単一の問題の並列化

yamamu2salia.dj.kit.ac.jp
okumur2aalia.dj.kit.ac.jp
shimom2talia.dj.kit.ac.jp
nunome2aalia.dj.kit.ac.jp

Back to ARK