(ミーハーアルゴリズム)優先探索
概要
二分探索をまとめたので次は優先探索をまとめたい。
説明
定義
幅優先探索：
Breadth First Search(以下BFS)
一連の基準を満たすノードのグラフデータ構造に対して、始点となるノードから探索を始め、次の深さのノードに探索する前に同じ深さのノードを全て探索しながら、目的のノードを探すアルゴリズム。
深さ優先探索：
Deapth First Search(以下DFS)
一連の基準を満たすノードのグラフデータ構造に対して、始点となるノードから探索を始め、同じ深さの次のノードに行く前に次の深さのノードを探索しながら、目的のノードを探すアルゴリズム。
フロー
BFS:
以下の様にして探索対象ノードを探索する。
- 初期化: 探索を始める前の定義、値追加
a.キュー（Queue）：空のキューQを定義
b.訪問済みリスト:訪問済みノードを記録するための空リストVを定義(V = [])
c.開始ノードsをQに追加、sを訪問済みリストに追加 - 探索：キューが空でない限り以下のステップを繰り返す
a.キューからノードを取り出す(v = Q.pop())
b.そのノードが訪問済みでない場合、訪問済みセットに追加(V.append(v))
c.そのノードに隣接する未訪問のノードwをキューに追加(Q.append(w))
DFS:
- 初期化: 探索を始める前の定義、値追加
a.スタック（Stack）：空のスタックSを定義
b.訪問済みリスト:訪問済みノードを記録するための空リストVを定義(V = [])
c.開始ノードsをSに追加, sを訪問済みリストに追加 - 探索：スタックが空でない限り以下のステップを繰り返す
a.スタックからノードを取り出す(v = S.pop())
b.そのノードが訪問済みでない場合、訪問済みセットに追加(V.append(v))
c.そのノードの次の深さのノードに行き、未訪問のノードwをスタックに追加(S.push(w))
計算量
基本的な認識としてはBFSもDFSも計算量は同じ。
O(V+E)
V：グラフ内のエッジの数
E；グラフ内のノードの数
ただ、以下の様な記事などで、
計算量理論的には全く別の特徴があることが説明してくれてます。
＊以下の記事は計算量クラスや、有向性、無向性などの計算量理論をご存知である方の方がスムーズに理解できると書かれています。
前提知識
DFSとBFSの一般的なアルゴリズムについては知っているものとします。DFSとBFSを知っていれば読み進められるようにしたつもりですが、「計算量クラス」「帰着（還元）」「困難性・完全性」などの計算複雑性理論（計算量理論）の基本的な部分を知っているとスムーズに理解できると思います。
メリット・デメリット
BFS
- メリット
- 最短経路を見つけたい時に適している：最短経路を見つけたい際は、ひとつ経路が見つかればそれ以上深いノードを探す必要がないため。
- デメリット
- メモリを多く消費する：特定の深さのノードを探した後に、そのまま次の深さにいかず、同じ深さの次のノードを探す際に同じ深さのノードの子ノードの情報も保持する必要があるため。
使い分け
以下はBFS
- 検索対象ノードがルートノードから近くの深さにあることが予測できる場合： 深くまで探索する必要がないから
- 検索木が深く、検索対象が希少だった場合：深くまで探索するのに適していないから。
- 最短経路を見つけたい：最短を見つけたいなら一つ経路が見つかればその経路の深さ以上は探索する必要がないから
以下はDFS
- ツリー一つ一つがとても広い：同じ深さのノードを隈無く探すことを避けたいから
- 検索対象が頻繁だが、ツリーの深さは遠い深さにあることが予測できる場合：BFSだと深くまで探索するのに不必要なメモリを消費してしまうから
- 二つのノードの間に経路があるかを確認する：BFSだと次の深さを探索して経路があるか確認する前に隣接する同じ深さのノードを探し切ろうとするので向かない
例
説明のフローをコードに落とし込むと以下の様になる。
BFS
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self, root):
# 初期化
self.root = Node(root)
def BreadthFirstSearch(self, target_node: int):
visited_list = []
queue = [self.root]
# キューが空でない限り繰り返し
while queue:
# キューからノードを取り出す
current = queue.pop(0)
visited_list.append(current.value)
# 対象ノードであればreturn
if current.value == target_node:
return print(f"Target node in this graph {visited_list}")
# そのノードが訪問済みでない場合、訪問済みセットに追加
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return print(f"No Target node in this graph {visited_list}")
# 二分木の作成
tree = BinaryTree(9)
tree.root.left = Node(4)
tree.root.right = Node(20)
tree.root.left.left = Node(1)
tree.root.left.right = Node(6)
tree.root.right.left = Node(15)
tree.root.right.right = Node(10)
# BFSの実行
tree.BreadthFirstSearch(6)
DFS
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self, root):
# 初期化
self.root = Node(root)
def DepthFirstSearch(self, target_node: int):
visited_list = []
stack = [self.root]
# スタックが空でない限り繰り返し
while stack:
# スタックからノードを取り出す
current = stack.pop()
visited_list.append(current.value)
# 対象ノードであればreturn
if current.value == target_node:
return print(f"Target node in this graph {visited_list}")
# そのノードが訪問済みでない場合、訪問済みセットに追加
if current.right:
stack.append(current.right)
if current.left:
stack.append(current.left)
return print(f"No Target node in this graph {visited_list}")
# 二分木の作成
tree = BinaryTree(9)
tree.root.left = Node(4)
tree.root.right = Node(20)
tree.root.left.left = Node(1)
tree.root.left.right = Node(6)
tree.root.right.left = Node(15)
tree.root.right.right = Node(10)
# DFSの実行
tree.DepthFirstSearch(6)
同じコードを実行しても探索経路が違うので結果までの経路が異なる。
この例で言えば、深さが一番深いノードかつ、探索対象がひとつなのでDFSが向いているということである。
# BFS
Target node in this graph [9, 4, 20, 1, 6]
# DFS
Target node in this graph [9, 4, 1, 6]
実例
bfsはweb検索のクローリングなどに用いることができる。
逆にdfsは特性的にパズルゲームなどの探索に向いています。
チェックリスト
- DFS、BFSの定義
- フローがパッと湧くか
- それぞれの使い分けの基準
備考
二分探索の時からかなり空いてしまいましたが優先探索についてまとめました。
こういう記事は継続的に整理しながら精度を上げていきたい。
（今が雑なだけ）
参考文献
Discussion