搜索算法python
时间: 2023-06-21 17:14:41 浏览: 44
Python 中常用的搜索算法有深度优先搜索(DFS)、广度优先搜索(BFS)、A*搜索等。
下面以迷宫问题为例,介绍如何实现 DFS 和 BFS 算法。
首先,我们需要定义迷宫的数据结构和图的遍历方法。假设迷宫是一个二维数组,其中 0 表示可通行的路,1 表示障碍物,我们可以使用 DFS 和 BFS 算法来搜索从起点到终点的路径。其中 DFS 搜索算法使用栈来实现,BFS 使用队列来实现。
```python
# 定义迷宫数据结构
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0]
]
# DFS 搜索算法
def dfs(maze, start, end):
stack = [start]
visited = set()
while stack:
node = stack.pop()
if node == end:
return True
visited.add(node)
neighbors = get_neighbors(maze, node)
unvisited_neighbors = [n for n in neighbors if n not in visited]
stack.extend(unvisited_neighbors)
return False
# BFS 搜索算法
def bfs(maze, start, end):
queue = [start]
visited = set()
while queue:
node = queue.pop(0)
if node == end:
return True
visited.add(node)
neighbors = get_neighbors(maze, node)
unvisited_neighbors = [n for n in neighbors if n not in visited]
queue.extend(unvisited_neighbors)
return False
# 获取邻居节点
def get_neighbors(maze, node):
row, col = node
neighbors = []
if row > 0 and maze[row-1][col] == 0:
neighbors.append((row-1, col))
if row < len(maze)-1 and maze[row+1][col] == 0:
neighbors.append((row+1, col))
if col > 0 and maze[row][col-1] == 0:
neighbors.append((row, col-1))
if col < len(maze[0])-1 and maze[row][col+1] == 0:
neighbors.append((row, col+1))
return neighbors
# 测试
start = (0, 0)
end = (4, 4)
print(dfs(maze, start, end)) # True
print(bfs(maze, start, end)) # True
```
以上代码演示了如何实现 DFS 和 BFS 搜索算法。其中 get_neighbors 方法用于获取当前节点的邻居节点,遍历过程中使用 visited 集合来记录已经访问过的节点,防止重复访问。