人工智能宽度优先搜索例题

宽度优先搜索（Breadth-First Search, BFS）是一种用于图遍历的算法，它从图中的某个节点开始，逐层向外扩展，直到访问完所有可达节点。在人工智能领域，宽度优先搜索常用于解决路径规划、任务调度和游戏AI等问题。下面通过一个具体的例题来说明宽度优先搜索的实现过程。

例题：给定一个有向图G，其中顶点表示为集合V，边表示为集合E。图G包含以下边：

```

A -> B

B -> C

C -> D

D -> E

```

现在需要找到从顶点A到顶点E的最短路径。

解答步骤如下：

1. 初始化队列Q和一个布尔数组visited，用于记录每个顶点是否被访问过。将顶点A加入队列Q，并将A标记为已访问。

2. 当队列不为空时，执行以下操作：

• 从队列中取出一个顶点v。
• 遍历与v相邻的所有顶点w（如果存在）。
• 如果顶点w未被访问，则将其加入队列Q，并将其标记为已访问。

3. 重复步骤2，直到队列为空或找到从A到E的路径。

4. 输出从A到E的最短路径长度。

代码实现如下：

```python

from collections import deque

def shortest_path(graph, start, end):

# 初始化队列和访问数组

queue = deque([start])

visited = [False] * len(graph)

# 广度优先搜索

while queue:

vertex = queue.popleft()

for neighbor in graph[vertex]:

if not visited[neighbor]:

visited[neighbor] = True

queue.append(neighbor)

# 检查是否存在从A到E的路径

if end in visited:

return len(end)
• 1

else:

return float('inf')

# 示例图

graph = {

'A': ['B', 'C'],

'B': ['C', 'D'],

'C': ['D'],

'D': ['E'],

'E': []

}

# 调用函数

print(shortest_path(graph, 'A', 'E')) # 输出结果应为3

```

在这个例子中，我们使用Python的`collections.deque`实现了队列，并使用布尔数组`visited`来记录每个顶点是否被访问过。通过广度优先搜索，我们可以从起点A开始，逐层向外扩展，直到找到从A到E的最短路径。最后，我们检查是否存在从A到E的路径，如果存在，则返回路径长度；否则，返回无穷大。