NP完全やNP困難な問題の最適解を得るのは困難 ↓ 近似解法

アルゴリズム論
第14回
---ＮＰ完全やＮＰ困難な
問題の最適解を
得るのは困難
↓
近似解法
---欲張り法
(greedy algorithm)
問題の要素を
独立に評価し
評価の高い順に
できるだけ取り込んで
解を得る手法
---問題を
複数ステージに
分割し
各ステージで
局所最適解を
選択する
---欲張り法による
ナップサック問題の解法
費用対効果が最良の
xiを入れられれば1
そうでなければ0とする
残りについて同様の
作業を繰り返す
---欲張り法による
巡回セールスマン問題の解法
いまいる街から
もっとも近い街へ行く
↓
現ノードから
最小コストで移動できる
ノードへ移動する
ことを繰り返す
---けちけち法
(stingy method)
問題の要素を
独立に評価し
評価の低い順に
外すことで
解を得る手法
---けちけち法による
ナップサック問題の解法
すべてのxi=1とする
条件が満たされるまで
費用対効果が最悪の
ものを外していく
---モンテカルロ法
乱数を用いて
シミュレーションや
数値計算を行う
例
πの近似値を求める
---[[PRE:
(require (lib "graphics"))
(open-graphics)
(define calc-pi
(lambda (n)
(define size 600)
(define window (open-viewport "calc-pi" size size))
(define plot
(lambda (x y color)
((draw-pixel window) (make-posn (round (* size x )) (- size (round (* size y))))
color)))
(define loop
(lambda (i c n)
(if (>= i n)
(exact->inexact (* 4 (/ c n)))
(let* ((x (random))
(y (random))
(in (<= (+ (* x x) (* y y)) 1)))
(plot x y (if in "red" "black"))
(if in
(loop (+ i 1) (+ c 1) n)
(loop (+ i 1) c n))))))
(loop 0 0 n)))
(calc-pi 10)
]]
---モンテカルロ法による
ナップサック問題の解法
（１）
各xiを乱数で生成
（２）
ｎ回施行して
条件を満たしつつ
評価関数が最良のものを
解とする
---[[PRE:
(require srfi/1)
(define knapsack
(lambda (n)
(if (= n 0)
'()
(let ((x (knapsack (- n 1)))
(y (list (random 2) (random 2) (random 2) (random 2))))
(if (and (feasible? y) (> (value y) (value x)))
y
x)))))
(define feasible?
(lambda (x)
(<= (inner-product x (list 2 3 5 6)) 9)))
(define value
(lambda (x)
(inner-product x (list 4 5 12 14))))
(define inner-product
(lambda (x y)
(fold + 0 (map * x y))))
(knapsack 100)
]]
---分枝限定法
近似解が得られるが
最適解を得ることも可能
---元問題の緩和問題
（条件を緩めた問題）
Ｒを作る
---緩和問題Ｒを解き
解Ｘを得る
---Ｘが元問題の条件を
満たせば暫定解とする
---そうでなければ
Ｘが出ないように
緩和問題の条件を強める
このとき、緩和問題Ｒが
同形の緩和問題いくつかに
分解される（[[EM:分枝]]）
---分枝を繰り返しながら
[[EM:深さ優先探索で]]
暫定解をとにかく
１つ見つける
---その後の探索は
すでに見つかっている
最良の近似解によって
枝刈りする（[[EM:限定]]）
---探索を途中で打ち切った場合
暫定解が近似解となる
探索が完了した場合
暫定解が最適解となる
---例題（１）
ナップサック問題
目的関数
V=Σci・xi → max
条件
Σai・xi ＜＝ C
ただし
ai,ci,Cは正
Σai ＞ C
xiは整数
---一般性を失わず
xi=0 or 1
とできる
↓
0-1ナップサック問題
(NP困難)
---例
[[PRE:
item a b c d
Price 4 5 12 14
Weight 2 3 5 6 ＜＝ 9
]]
---緩和問題
xiを0 or 1ではなく
0以上1以下の
有理数でよいとする
緩和問題の解に
有理数が含まれたら
xiを0か1と決めることで
分枝する
---例題（２）
巡回セールスマン問題
目的関数
Σc(vi,vj)xij→min
条件
xij=0 or 1
xij=1の辺を集めると
ハミルトン閉路になる
ただし
c(vi,vj)は辺{vi,vj}の
非負のコスト
---緩和問題
目的関数
Σc(vi,vj)xij→min
条件
xij=0 or 1
Σxij=n
---例
クリックして図を表示
---緩和問題の解き方
頂点がｎ個なら
ハミルトン閉路の
辺数は必ずｎ本
↓
コストの小さい辺を
ｎ本選ぶ
---緩和問題の解が
ハミルトン閉路
ではない
↓
ループを禁止して
分枝

Download Report