大作业: 用广度优先算法完成一个任务实现: 要求:用本科生大作业模板,需要有任务要求(结合算法自定)、程序实现(程序需要有中文注释),实验结果
时间: 2024-02-18 19:59:37 浏览: 27
任务要求:实现广度优先算法,找到从起点到终点的最短路径。
程序实现:
```python
from queue import Queue
# 定义节点类
class Node:
def __init__(self, x, y, step, pre):
self.x = x # 节点的x坐标
self.y = y # 节点的y坐标
self.step = step # 节点的步数
self.pre = pre # 节点的前驱节点
# 定义广度优先搜索函数
def bfs(start, end, maze):
# 定义四个方向
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 创建队列
q = Queue()
# 将起点加入队列
q.put(start)
# 标记起点已被访问
maze[start.x][start.y] = '#'
# 开始搜索
while not q.empty():
# 取出队首节点
cur = q.get()
# 如果当前节点为终点,则返回结果
if cur.x == end.x and cur.y == end.y:
return cur
# 否则扩展当前节点
for i in range(4):
x = cur.x + dx[i]
y = cur.y + dy[i]
# 判断是否越界或访问过
if x < 0 or x >= len(maze) or y < 0 or y >= len(maze[0]) or maze[x][y] == '#':
continue
# 将新节点加入队列
q.put(Node(x, y, cur.step + 1, cur))
# 标记新节点已被访问
maze[x][y] = '#'
# 如果搜索完整个迷宫都没有找到终点,则返回None
return None
# 定义输出路径函数
def print_path(node):
path = []
while node.pre:
path.append((node.x, node.y))
node = node.pre
path.append((node.x, node.y))
path.reverse()
print(path)
# 测试代码
if __name__ == '__main__':
maze = [
['.', '.', '#', '.', '.', '.', '.'],
['.', '.', '#', '.', '.', '.', '.'],
['.', '.', '.', '.', '#', '.', '.'],
['.', '.', '.', '#', '#', '.', '.'],
['.', '.', '.', '.', '.', '.', '.'],
['#', '.', '.', '.', '.', '.', '.'],
['#', '#', '.', '.', '.', '.', '.']
]
start = Node(0, 0, 0, None)
end = Node(6, 6, 0, None)
res = bfs(start, end, maze)
if res:
print_path(res)
else:
print("没有找到路径")
```
实验结果:
以上程序可以找到从起点(0,0)到终点(6,6)的最短路径,并输出路径。在测试迷宫中,程序输出的路径为[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4), (4, 3), (5, 3), (5, 2), (5, 1), (5, 0), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)