アルゴリズムクイックリファレンス 第2版

364

■

11

章 新たな分類のアルゴリズム

確率的アルゴリズム

問題インスタンスに対して同じ結果を計算して出す代わりに、乱択計算

を使って解を計算する。複数回実行すれば、解の平均値が真の解に収束

することが多い。

11.2

 近似アルゴリズム

近似アルゴリズム（

Approximation Algorithms

）は、正確さとより効率的な計算

との間でトレードオフを行う。「十分によい」答えであれば受け入れられる例として、

さまざまな計算分野で起こるナップサック問題（

Knapsack Problem

）を考えよう。

目標は、ナップサックに入れる品物を、ある最大重量

W

を超えないようにして、ナッ

プサック全体の価値が最大になるように決めることだ。この問題は、

0-1

ナップサッ

ク

（

Knapsack 0/1

）として知られており、動的計画法によって解ける。

0-1

ナップ

サック

問題においては、

1

つの品物につき

1

つのインスタンスしか詰め込めない。無

制限整数ナップサック（

Knapsack Unbounded

）という変形版では、同じ品物をい

くつでも詰め込める。どちらの場合もアルゴリズムはスペースの制約下で品物の価

値の合計の最大価値を返す。

4

つの品物

{4, 8, 9, 10}

の集合を考える。各品物のドル建てのコストとポンド単

位の重量が等しいとしよう。第

1

要素は、重量

4

ポンド、コスト

4

ドルだ。詰め込

める最大重量は

W

＝

33

ポンドと仮定する。

動的計画法では、下位問題の結果を記録して再計算を防ぎ、下位計算の解を組

み合わせて問題を解 ...