演習問題 11
平成 27 年 6 月 29 日
探索問題（→「補足」）A においては，一つの入力（個例）x に対して解 y ∈ A[x] が一般
に複数ある．これらの解の間に何らかの意味で優劣があり，中でもなるべく良い解を得た
い場合がある．そのような問題を
称して最大化問題という．すなわち最大化問題では，
探索問題と同じく各個例 x に対して適格
（feasible）
な解の集合 A[x] が決っているが，加え
て各解 y ∈ A[x] の「良さ」の度合を表す非負実数 c(x, y) が定まっており，これをなるべ
く大きくしたい．c を目的函数
（objective function）と呼ぶ．
例えば最大化問題 max-knapsack では，各品物 i = 1，…，n の重量 si ∈ N と価値
vi ∈ N と正整数 B ∈ N とが与えられる．これに対し重量の和が B を超えないような品物
の取り方のうち価値の和のなるべく大きいものを求めたい．判定問題 knapsack は NP
完全であった（→問 7.4）から，P = NP でない限り，最大化問題 max-knapsack におい
て常に目的函数を最大にする解を出力する多項式時間算法は存在しない（→問 11.1）．
そこで厳密な最大化は諦め，なるべく最大に近い値を達成する近似を目指すことにし
よう．算法 M が探索問題 A を正しく解く，すなわち各個例 x に対して M は適格な解
M (x) ∈ A[x] を出力するとする．非負実数 r について，M が r 近似であるとは，任意の
x と任意の y ∈ A[x] とについて，この解 M (x) の良さ c(x, M (x)) が
!
"
c x, M (x) ≥ r · c(x, y)
を満すことをいう．かかる最大の r を M の近似率（approximation ratio）という．これ
は 1 以下の非負値であって 1 に近いほど良い（これの逆数を近似率と呼ぶ
献もある）．
目的函数 c が「良さ」でなく「悪さ」を表しており，これをなるべく小さくしたいとい
う最小化問題についても，同様に（
「≥」
「最大」の代りに「≤」
「最小」として）定義する．
近似率は存在すれば 1 以上の値となり，1 に近いほど良い．最大化，最小化を合せて最適
化（optimization）問題と呼ぶ．
問 11.1
7
次の三つの命題が同値であることを示せ．
（1）判定問題 knapsack は P に属する．
（2）探索問題 exact-max-knapsack は FP に属する．
（3）最大化問題 max-knapsack に近似率 1 の多項式時間算法が存在する．
但し exact-max-knapsack は，max-knapsack と同じ入力を受取り，重量の和が B
を超えないような品物の選び方のうち価値の和が最大となるもの（の一つ）を求める探索
問題である．
11-1
問 11.2
3
max-knapsack に対する次の算法は正定数近似（或る r > 0 に対し r 近似）か．
T = ∅ から始める．品物 i を一つづつ，価値 vi の降順に見て，これを T に加えて
も重量の和が B を超えないならば加える．終ったら T を出力する．
問 11.3
3
max-knapsack に対する次の算法は正定数近似か．
vi
の降順に見て，これ
si
を T に加えても重量の和が B を超えないならば加える．終ったら T を出力する．
T = ∅ から始める．品物 i を一つづつ，重量あたりの価値
問 11.4
1＋6
与えられた無向グラフ G = (V, E) の点被覆のうち頂点数のなるべく小さいもの
を求める問題に対し，次の近似算法を考える．
G における極大な取組*1 を一つ求め，その各辺の両端点すべてを出力する．
（1）この算法が正しいこと，つまり得られる解が確かに G の点被覆であることを示せ．
（2）この算法の近似率を求めよ．
（2）についての注意 近似率がその値以上であることと以下であることの両方を示すこと．
問 11.5
8＋6
（1）判定問題 knapsack′ は knapsack と同じだが，各品物 i ∈ {1, . . . , n}
の価値 vi が
字列 0vi として与えられる（重量 si は二進法で書かれる）．次のよう
に動的計画法を
った算法を与えることにより knapsack′ ∈ P を示そう*2 ．
（a）非負整数 k ≤ n と v ≤ v1 + · · · + vk とについて，品物 1，
…，k から価値 v 以上
になるように選ぶときの重量の和の最小値を Sk,v で表す．k が正のとき Sk,v
を Sk−1,v′ の形の項（v ′ は v1 + · · · + vk−1 以下の非負整数）を用いて表せ．
（b）これを用いて knapsack′ を解く多項式時間限定の手順を述べよ．
（2）ε を正の定数とする．max-knapsack に対する多項式時間限定の 1 − ε 近似算法
を与えよ．
問 11.6
5
P ̸= NP ならば次の最小化問題 min-tsp に対する定数近似の多項式時間算法が
存在しないことを，hc（→問 7.5）の NP 完全性から示せ．
min-tsp の個例は，相異なる町 i，j ∈ {1, . . . , m} 間の旅費 d(i, j) = d(j, i) ∈ N\{0} で
与えられる*3 ．町を一度づつ訪れて帰る旅程すなわち (1, . . . , m) の並べ替え (i1 , . . . , im )
のうち，
費用 d(i1 , i2 ) + d(i2 , i3 ) + · · · + d(im−1 , im ) + d(im , i1 ) のなるべく小さいも
のを求めたい．
無向グラフ G = (V, E) における取組（matching）とは辺集合 M ⊆ E であって端点に重複なきものを
いう．それが極大であるとは，M を含む取組が M 以外に存在しないことをいう．
*2 このことを以て knapsack は擬多項式時間で解けると言うことがある．
*3 距離の 理（三角不等式）を満すとは限らない．満す場合は近似率 3/2 の多項式時間算法が知られる．
*1
11-2
© Copyright 2024 ExpyDoc
