コストのついたグラフの探索 - VRL

コストのついたグラフの探索
分枝限定法
A*アルゴリズム
組み合わせ最適化問題
• 目的関数: f(x)
• 制約条件: x ∈ S
S: 有限個,または,可算無限個の要素を持
つ離散集合
このf(x) を最小化する問題(最大化でもかま
わないが,以降は最小化問題を扱う)
例1:ナップザック問題
• 容量 C のナップサックが
一つと、n 個の品物(各々、
価値 pi, 容積 ci)が与えら
れたとき、ナップサックの
容量 C を超えない範囲で
いくつかの品物をナップ
サックに詰め、ナップサッ
クに入れた品物の価値の
和を最大化するにはどの
品物を選べばよいか
例2:巡回セールスマン問題
• 都市の集合と各2都市間の移
動コストが与えられたとき、全て
の都市をちょうど一度ずつ巡り
出発地に戻る巡回路のコストす
なわち総移動距離が最小のも
のを求める(セールスマンが所
定の数の都市を1回だけ巡回す
る場合の最短経路を求める)組
合せ最適化問題
例3:オープンスペースでの経路計画
• 障害物が少ない迷路での経路
探索問題
• Dijkstraのアルゴリズムは出発
点から等距離にある球面に最も
近い点を取りこみながら膨張す
るアルゴリズム
S
• ゴールによるガイドを受けない
ため効率が悪い
G
その他ほとんどの組み合わせ最適化
問題で使える.
• 最小全域木
• 8パズルなどのパズル
• ゲーム
• 最近傍探索
• 他,諸々
分枝と限定=分枝限定法
• 分枝:与えられた問題 P0 を,それらを解くこと
で等価的に P0 が解かれるような部分問題Pi(i
= 1,2,・・・) に分解する操作
f(P0) = min
f(P
)
f(P
):
問題P
の最適値
i
i
i
i
となるような部分問題 Pi(i = 1,2,・・・)に分
解する操作
• 限定:部分問題 Pi を終端させる操作
分枝操作
• 最適化問題 Pi は,以下に示す問題とする.
目的関数: f(x)
制約条件: x ∈ Si
• 例:2次元の経路探索問題で
は,S=(x0,y0)から, G=
(xN,yN)までの経路を求める
問題になる.これを, Mi=
(xi,yi)を経由してゴールに至
る問題Piに分解する.
S
Mi
G
限定操作の方法
• 部分問題 Pi よりも制約条件が緩く,解きやす
い問題を考えて P’i と表す.このような問題を
緩和問題と呼び,問題 Pi の緩和問題 P’i は,
以下のように定義されます.
目的関数: g(x)
制約条件: x ∈ S’i, Si ⊂ S’i
• 制約条件が緩いため,一般に,x ∈ Si となる x
に対しては,g(x) ≦ f(x)が成り立つ.
緩和問題の例
• g(P’i):Miまでの実距離と,
MiからGまでの障害物を度
外視したユークリッド距離
• f(Pi): Mi経由の実距離
S
Mi
G
暫定値とそれを用いた限定操作
• g(P’i)を緩和問題P’iの最適値(下界値) と呼ぶ.
• ある時点で,部分問題Piへの分解によって元の
問題 P0 の許容解とその値f(Pi)が複数求められ
ているとする.また,これらf(Pi) の中の最小値を
暫定値と呼び,z で表わす.
• g(P’i) ≧ z なる関係があるとき,部分問題 Pi,及
び,それから生成される部分問題に対する許容
解は 最適解とはならない.
限定操作の実際
• これまでの探索で求められた,
ゴールまで到達可能な許容解
(実経路)のうちで最短のもの
(図中緑線)の長さをzとする.
• 現在探索中の経路の緩和解
での長さg(P’i) (図中赤線)が z
の長さを超えると,点Mi を経
由した経路は調べなくて良い
ことになる.
Mi
S
G
分枝限定法アルゴリズム
1. 初期設定: A := {P0}, z := ∞
2. A = φ ならば終了.
 z = ∞: 問題 P0 は解を持たない
 z < ∞: f(P0) = z
3. 集合 A の中から,部分問題 Pi を選択
4. もし,緩和問題 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 へ戻る.
部分問題への分解の方法
• 横型探索
• 縦型探索
• 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通り,これらを対象に展開を
行う.
結局コスト付きグラフの探索問題
• グラフの各辺にはコストが
付けられている.
• この状態で出発点Sから
ゴールGへの最短路を求め
る問題になっている.
S
G