AIの幅優先探索アルゴリズムの実装方法

幅優先探索 (Breadth-First Search, BFS) アルゴリズムは次のステップで実装できます。1. 訪問するノードを格納するキューを作成します。2. 開始ノードをキューに入れ、訪問済みとしてマークします。3. キューが空でない場合は、次の手順を実行します。
a. キューからノードを取り出します。
b. ノードが探索対象のノードであるかどうかをチェックします。そうであれば探索を終了し、結果を返します。
c. そうでない場合は、このノードのすべての近隣のノード（未訪問のノード）をキューに入れ、訪問済みとしてマークします。4. キューが空で、探索対象のノードが見つからなければ、探索は失敗します。以下は、Python によるシンプルな実装例です。

def bfs(graph, start, target):

visited = set()  # 存储已访问的节点

queue = []  # 存储待访问的节点

queue.append(start)

visited.add(start)

while queue:

node = queue.pop(0)

if node == target:

return True  # 找到目标节点

for neighbor in graph[node]:

if neighbor not in visited:

queue.append(neighbor)

visited.add(neighbor)

return False  # 没有找到目标节点 # 示例图的邻接表表示 graph = {

‘A’: [‘B’, ‘C’],

‘B’: [‘A’, ‘D’, ‘E’],

‘C’: [‘A’, ‘F’],

‘D’: [‘B’],

‘E’: [‘B’, ‘F’],

‘F’: [‘C’, ‘E’] } start_node = ‘A’ target_node = ‘F’ result = bfs(graph, start_node, target_node) print(result)

上記の例では、グラフの隣接リスト表現を作成し、BFS関数で幅優先探索を実施しました。結果はTrueとなり、与えられたグラフにおいて、開始ノードAから目的ノードFに到達できることを示しています。