グラフとネットワーク（5）今日の講義で学ぶことグラフの探索（search

今日の講義で学ぶこと
グラフとネットワーク（5）
• グラフの探索
～グラフの探索～
グラフの探索（search）
– 深さ優先探索（DFS, Depth-First Search ）
– 幅優先探索（BFS, Breadth-First Search ）
3/18
【定義】与えられたグラフの全ての点と辺
を、組織的に訪問することをグラフの探索
という。
代表的な探索手法としては、大別すると、次
の 2 つのアルゴリズムがある
• 深さ優先探索（DFS, Depth-First Search ）
• 幅優先探索（BFS, Breadth-First Search ）
【注】与えられたグラフ G = (V,E) の全域木が得られる。
また、O(|V|+|E|) で動作するように実装できる。
アルゴリズムの記述
2/18
5/18
探索アルゴリズムの枠組み
4/18
• 連結無向グラフ G = (V,E) を想定する
• 探索中、各点は、未訪問 (unvisited) の状態から、訪問済
(visited) を経て、最後に走査済 (scanned) の状態へ変化する
• 各辺は、未操作の状態から走査済へ変化する
• 捜索は任意の 1 点 s を選び、その点を訪問済とすることか
ら始まる
• 各反復では、訪問済である点を 1 つ選びその点に接続する
未走査の辺を 1 つ選び走査する。走査した辺は走査済とし、
他方の端点は（未訪問なら）訪問済とする
• ある点に接続する全ての辺が走査済になると、その点は走
査済となる
• 全ての点と辺が走査済になった時点で探索は終了する
アルゴリズム GraphSearch
入力：無向連結グラフ G = (V,E), 始点 s∈V
出力：訪問順序 V → Z+ , 探索木 T ⊆E
6/18
• NUM(v) は、点 v の訪問順序を与える番号
1. k:=1, NUM(s):=1, 全ての点と辺は未走査である。
また、s 以外の点は未訪問である。T:=φ
• 訪問済の点 v に接続する 1 つの辺 (v,w) が
選ばれ、w が未訪問であった場合、辺 (v,w)
を集合 T に記憶しておく
2. 訪問済の点が存在する限り、次の手順を反復する
（存在しなければ、ステップ 3 へ進む）
訪問済の点 v を 1 つ選ぶ。v から接続する未走査の辺
の1つ {v,w} を選び、その状態を走査済とする。このとき、
点 w が未訪問であれば、
k:=k+1, NUM(w):=k, T:=T∪{{v,w}}
とし、さらに w を訪問済とする。点 v について、接続す
る辺が全て走査済であれば走査済とする。点 w について
も同様
• 計算終了時、辺集合 T は G の全域木の一つ
になっているので、これを s を根とする有
向木とみなす。この木を探索木（search
tree）と呼ぶ。
3. NUM と T を出力したのち計算終了
7/18
深さ優先探索（Depth-First Search）
• アルゴリズム GraphSearch のステップ 2 に
おいて、訪問済みの点 v を選ぶ基準を「もっと
も新しく訪問済になった点」としたもの
• 縦型探索、線形探索 (linear search) 、後入れ先
出探索 (last-in-first-out search, LIFO 探索) とも
呼ばれる
• ある点 v を訪問したとき、まだ未走査の辺が v
に接続していればそちらへ探索を進め、未走査
の辺がない場合は、v へ最初に到達した辺を逆
戻りする、という挙動を繰り返すもの
8/18
アルゴリズム DFS
入力：無向連結グラフ G = (V,E), 始点 s∈V
出力：訪問順序 V → Z+ , 探索木 T ⊆E
1. v:=s, k:=1, NUM(s):=1, 全ての点と辺は未走査である。
また、s 以外の点は未訪問である。T:=φ
2. 訪問済の点 v を 1 つ選ぶ。
(a) v に接続する未走査の辺があれば 1 つ {v,w} を選び走査し、
その状態を走査済とする。このとき、点 w が未訪問であれば、
k:=k+1, NUM(w):=k, T := T∪{{v,w}}
とし、さらに w を訪問済とし、 v :=w として 2 へ戻る。
点 w が訪問済であれば、そのまま 2 へ戻る。
(b) v から接続する辺が全て走査済ならば、点 v を走査済とした
後 v へ最初に訪問した点 (y,v)∈T を v から y へ後戻りする。
このとき、y = s ならばステップ 3 へ進む。
3. NUM と T を出力したのち計算終了。
【練習問題】次のグラフを、頂点 s を始点として
深さ優先探索（DFS）しなさい。
9/18
DFSの計算量
10/18
無向連結グラフ G = (V,E) を深さ優先探索
するとき
・時間計算量 O(|V| + |E|)
・空間計算量 O(|V|)
【注】大規模なグラフでは探索木のパスが長すぎ
て探索が終わらないことがある。
⇒ 深さ制限探索など
11/18
幅優先探索（Breadth-First Search）
• アルゴリズム GraphSearch のステップ 2 に
おいて、訪問済みの点 v を選ぶ基準を「もっと
も過去に訪問済になった点」としたもの
• 横型探索、先入れ先出し探索 (first-in-first-out
search, FIFO 探索) とも呼ばれる
• 訪問済の点を、いったん集合 Q に格納するが、
Q は先に入った順に取り出すという性質を持つ。
このようなデータ構造は、待ち行列 (queue)
あるいは、先入れ先出しリスト (first-in-first-out
list) と呼ぶことが命名の由来
12/18
アルゴリズム BFS
入力：無向連結グラフ G = (V,E), 始点 s∈V
出力：訪問順序 V → Z+ , 探索木 T ⊆E
1. v:=s, Q:=φ, k:=1, NUM(s):=1, 全ての点と辺は未走査。
また、s 以外の点は未訪問である。T:=φ
2. 現在の訪問点 v に対して次の手順を実行する。
(a) v に接続する未走査の辺があれば 1 つ {v,w} を選び走査し、
その状態を走査済とする。このとき、点 w が未訪問であれば、
k:=k+1, NUM(w):=k, T := T∪{{v,w}}
とし、さらに w を訪問済とし、w を Q の最後尾へ格納して
2 へ戻る。点 w が訪問済であれば、そのまま 2 へ戻る。
(b) v から接続する辺が全て走査済のときは、Q:=φ ならば
ステップ 3 へ進む。そうでなければ、Q の先頭の y を Q から
取り除き点 v :=y として 2 へ戻る。
3. NUM と T を出力したのち計算終了。
13/18
【練習問題】次のグラフを、頂点 s を始点として
幅優先探索（BFS）しなさい。
14/18
BFSの計算量
無向連結グラフ G = (V,E) を幅優先探索
するとき
・時間計算量 O(|V| + |E|)
・空間計算量 O(|V| + |E|)
【注】一般に、深さ優先探索の空間計算量の方が
幅優先探索の空間計算量よりもずっと小さい
深さ優先探索の空間計算量 O(|V|)
15/18
ナップサック問題（Knapsack problem）
n = 2 の場合の探索木
ナップサックに、荷物を入れていく。
荷物は、n 個あり、それぞれの重さは
a1, a2, …, an
であるとする。ナップサックの容量を C と
するとき、出来るだけ沢山の荷物を入れる
にはどの品物を入れれば良いか？
【注1】ここでは、重さの意味で「沢山」
【注2】設定を変えた多くのバーションがある
【注3】クラスNPに属す典型的な問題
【例題】a1=5, a2=4, a3=3, C=8 の探索木を
幅優先探索しなさい。
a1 を入れる
w=5
a2 を入れる
w=9 3
1
w=5 4
w=4 5
2
17/18
w=0
a2 を入れない
w=0 6
w>C
探索不要
（枝刈り）
○
○
a1 を入れるか？
×
×
a2 を入れるか？ ○
×
a1 だけをナップサックに入れる
a1 を入れない
a2 を入れる
a2 を入れない
16/18
【練習問題】探索を最後まで実行し、
最適解を求めなさい。
【解答例】
18/18

Download Report