ナップザック問題のF木, P木, K木の構成法とその計算実験
スポンサーリンク
概要
- 論文の詳細を見る
等号制約を持つナップザック問題の実行可能性問題、周期性問題、そしてすべての右辺の数に対して問題を解くための理論的にも実用的にも高速なアルゴリズムを示している。等号制約を持つナップザック問題は、通常の不等号(≦)制約付きのナップザック問題と違って、その実行可能性すら自明ではない。F木は、実行可能性に関する必要十分な情報を含んだ木で、或るグラフの最短路木として定義される。この論文で示すF木を構成するためのアルゴリズムは、その本質的な部分の計算複雑度が変数の個数に直接依存しないという特徴を持っている。一方、不等号制約(≦)を持つ通常のナップザック問題が持つ周期的性質は、等号制約を持つナップザック問題にも成立することが容易に示すことができる(厳密な周期的性質の説明は本論文第3節を参照)。P木は周期性に関する必要十分な情報を含んだ木で、F木と同様に定義され、同様に求めることができる。F木及びP木の情報を利用することにより、その主要部分の計算複雑度が変数の個数に直接依存しないようなナップザック問題の解法を示唆することができる。F木及びP木をそれぞれ求めた段階で、有限個の右辺の数に対してだけナップザック問題が未解決であることがわかる、またすべての右辺の数についてナップザック問題を解く際に必要のない変数(最適解で0の値をとる変数)の一部を見つけることができる。この二つの変数切り捨てテストに、単純な数の性質から導けるもう一つの計算節約法を加え、ナップザック問題をすべての右辺の数に対して解いている。変数の個数に直接依存しない有限個の右辺の数(K数)の間にうまく木構造(K木)を定義してやることにより、すべての右辺の数に対する解を表現している。