コストのついたグラフの探索 分枝限定法 A*アルゴリズム.

Presentation on theme: "コストのついたグラフの探索 分枝限定法 A*アルゴリズム."— Presentation transcript:

1 コストのついたグラフの探索 分枝限定法 A*アルゴリズム

2 組み合わせ最適化問題 目的関数： f(x) 制約条件： x ∈ S S： 有限個，または，可算無限個の要素を持つ離散集合

3 例1：ナップザック問題 容量 C のナップサックが一つと、n 個の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか

4 例2：巡回セールスマン問題 都市の集合と各2都市間の移動コストが与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のコストすなわち総移動距離が最小のものを求める（セールスマンが所定の数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題

5 例３：オープンスペースでの経路計画 障害物が少ない迷路での経路探索問題
Dijkstraのアルゴリズムは出発点から等距離にある球面に最も近い点を取りこみながら膨張するアルゴリズム ゴールによるガイドを受けないため効率が悪い S G

6 その他ほとんどの組み合わせ最適化問題で使える．
最小全域木 8パズルなどのパズル ゲーム 最近傍探索 他，諸々

7 分枝と限定＝分枝限定法 分枝：与えられた問題 P0 を，それらを解くことで等価的に P0 が解かれるような部分問題Pi（i = 1，2，･･･） に分解する操作 　　　f(P0) = min f(Pi) 　　f(Pi)： 問題Pi の最適値 　　　　　　　　i 　　となるような部分問題 Pi（i = 1，2，･･･）に分解する操作 限定：部分問題 Pi を終端させる操作

8 分枝操作 最適化問題 Pi は，以下に示す問題とする． 目的関数： f(x) 制約条件： x ∈ Si
例：2次元の経路探索問題では，S=（x0,y0）から， G=（xN,yN）までの経路を求める問題になる．これを， Mi= （xi,yi）を経由してゴールに至る問題Piに分解する． S Mi G

9 限定操作の方法 部分問題 Pi よりも制約条件が緩く，解きやすい問題を考えて P’i と表す．このような問題を緩和問題と呼び，問題 Pi の緩和問題 P’i は，以下のように定義されます． 　　　目的関数： g(x) 　　　制約条件： x ∈ S’i，　Si ⊂ S’i 制約条件が緩いため，一般に，x ∈ Si となる x に対しては，g(x) ≦ f(x)が成り立つ．

10 緩和問題の例 g(P’i):Miまでの実距離と， MiからGまでの障害物を度外視したユークリッド距離 ｆ(Pi): Mi経由の実距離 S

11 暫定値とそれを用いた限定操作 g(P’i)を緩和問題P’iの最適値（下界値） と呼ぶ．
ある時点で，部分問題Piへの分解によって元の問題 P0 の許容解とその値f(Pi)が複数求められているとする．また，これらf(Pi) の中の最小値を 暫定値と呼び，z で表わす． g(P’i) ≧ z なる関係があるとき，部分問題 Pi，及び，それから生成される部分問題に対する許容解は 最適解とはならない．

12 限定操作の実際 これまでの探索で求められた，ゴールまで到達可能な許容解（実経路）のうちで最短のもの（図中緑線）の長さをｚとする．
現在探索中の経路の緩和解での長さg(P’i) （図中赤線）が zの長さを超えると，点Mi を経由した経路は調べなくて良いことになる． Mi S G

13 分枝限定法アルゴリズム 初期設定： A := {P0}, z := ∞ A = φ ならば終了． 集合 A の中から，部分問題 Pi を選択
z = ∞： 問題 P0 は解を持たない z < ∞： f(P0) = z 集合 A の中から，部分問題 Pi を選択 もし，緩和問題 P’i が解を持たなければ， A := A - {Pi} として，2 へ戻る 　　そうでなけでば， もし，Pi のf(Pi)が得られたら， z := min {z, f(Pi)}， A := A - {Pi} として，2 へ戻る． そうでない場合 もし，g(P’i) ≧ z ならば A = A - {Pi} として，2 へ戻る． そうでなければ 問題 Pi を，部分問題 Pi1，･･･，Pik に分解し， A = (A - {Pi}) ∪ {Pi1，･･･，Pik} として，2 へ戻る．

14 部分問題への分解の方法 横型探索 縦型探索 Best first Search: g(P’i)の値が最も小さいものから優先的に展開する．
　迷路の問題では，最初の中継点 M0 を出発点Sとすれば，P’0=P0となる． 　次に可能な展開は， M0 +(0,1), M0 +(1,1) ， M0 +(1,0), M0 +(1,-1), M0 +(0,-1) , M0 +(-1,-1) , M0 +(-1,0) , M0 +(-1,1)の8通り，これらを対象に展開を行う．

15 結局コスト付きグラフの探索問題 グラフの各辺にはコストが付けられている． この状態で出発点SからゴールGへの最短路を求める問題になっている．