探索アルゴリズム#
リストの探索#
リスト・配列の探索について
線形探索#
全要素を順に見て比較していき、見つかれば終了する
data = [1, 5, 3, 2, 4]
query = 3
for i in range(len(data)):
if data[i] == query:
print(f"index={i}, value={data[i]}")
break
index=2, value=3
二分探索（binary search）#
ソート済みのリストや配列のデータにおける検索で、検索したい値が中央の値より大きいかどうかで検索範囲を半分ずつに絞り込んでいく
グラフや木構造の探索について#
幅優先探索（breadth first search）#
まず、根ノードに隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。
幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。
最良優先探索とは異なり、ノード探索にヒューリスティクスを使わずに、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。
最良優先探索（best-first search）#
幅優先探索を拡張し、最も望ましいノードを選択するようにしたもの
from typing import List
from queue import Queue
def get_adjacent_nodes(edges: List[list]) -> List[list]:
"""各nodeと隣接したnodeのリストを作る"""
nodes = set(sum(edges, []))
adjacent_nodes = []
for node in nodes:
adjacent_node = []
for edge in edges:
if node in edge:
e = [e for e in edge if e != node][0]
adjacent_node.append(e)
adjacent_nodes.append(adjacent_node)
return adjacent_nodes
def bfs(edges: List[list]):
"""幅優先探索（breadth first search）"""
adjacent_nodes = get_adjacent_nodes(edges)
n_edge: int = len(set(sum(edges,[])))
# その頂点を検知済みかどうかを表す配列
searched: List[bool] = [False] * n_edge
# 検知したがまだ訪問済みでない頂点の集合 (保留中の頂点の集合)
todo = Queue()
# root nodeをtodoに入れる
searched[0] = True
todo.put(0)
while not todo.empty():
target_node: int = todo.get()
print(f"searching a node '{target_node}'")
for adj_node in adjacent_nodes[target_node]:
if not searched[adj_node]:
print(f"{adj_node} is found and enqueued to todo")
todo.put(adj_node)
searched[adj_node] = True
# 隣接リスト表現 (adjacency-list representation)したグラフ
edges: List[list] = [
[0, 1], # 0 - 1 の辺
[0, 2],
[1, 3]
]
bfs(edges)
searching a node '0'
1 is found and enqueued to todo
2 is found and enqueued to todo
searching a node '1'
3 is found and enqueued to todo
searching a node '2'
searching a node '3'
深さ優先探索（depth-first search）#
根ノードから子ノードへとどんどん深く探索していき、行き着いたらバックトラック（一歩逆戻り）して別のノードを探索する
from typing import List
def get_adjacent_nodes(edges: List[list]) -> List[list]:
"""各nodeと隣接したnodeのリストを作る"""
nodes = set(sum(edges, []))
adjacent_nodes = []
for node in nodes:
adjacent_node = []
for edge in edges:
if node in edge:
e = [e for e in edge if e != node][0]
adjacent_node.append(e)
adjacent_nodes.append(adjacent_node)
return adjacent_nodes
def dfs(edges: List[list]):
"""深さ優先探索（depth-first search）"""
adjacent_nodes = get_adjacent_nodes(edges)
n_edge: int = len(set(sum(edges,[])))
# その頂点を検知済みかどうかを表す配列
searched: List[bool] = [False] * n_edge
# 検知したがまだ訪問済みでない頂点の集合 (保留中の頂点の集合)
todo: List[int] = []
# root nodeをtodoに入れる
searched[0] = True
todo.append(0)
while len(todo) > 0:
target_node: int = todo.pop()
print(f"searching a node '{target_node}'")
for adj_node in adjacent_nodes[target_node]:
if not searched[adj_node]:
print(f"{adj_node} is found and enqueued to todo")
todo.append(adj_node)
searched[adj_node] = True
# 隣接リスト表現 (adjacency-list representation)したグラフ
edges: List[list] = [
[0, 1], # 0 - 1 の辺
[0, 2],
[1, 3]
]
dfs(edges)
searching a node '0'
1 is found and enqueued to todo
2 is found and enqueued to todo
searching a node '2'
searching a node '1'
3 is found and enqueued to todo
searching a node '3'