人工智能深度优先搜索
时间: 2024-05-06 13:12:07 浏览: 20
深度优先搜索是一种常用的人工智能搜索算法,它通过遍历搜索树的深度方向来寻找解决问题的路径。下面是一个演示深度优先搜索的例子:
假设我们要在一个迷宫中找到从起点到终点的路径。迷宫可以表示为一个二维矩阵,其中0表示可通行的路径,1表示墙壁。我们可以使用深度优先搜索算法来找到一条路径。
```python
def dfs(maze, start, end, path):
if start == end:
return True
x, y = start
if maze[x][y] == 1:
return False
maze[x][y] = 1
path.append(start)
# 向上搜索
if x > 0 and dfs(maze, (x-1, y), end, path):
return True
# 向下搜索
if x < len(maze)-1 and dfs(maze, (x+1, y), end, path):
return True
# 向左搜索
if y > 0 and dfs(maze, (x, y-1), end, path):
return True
# 向右搜索
if y < len(maze[0])-1 and dfs(maze, (x, y+1), end, path):
return True
# 如果四个方向都没有找到路径,回溯
path.pop()
return False
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0]
]
start = (0, 0)
end = (4, 4)
path = []
if dfs(maze, start, end, path):
print("找到路径:", path)
else:
print("没有找到路径")
```
在上面的例子中,我们使用深度优先搜索算法来在迷宫中找到从起点到终点的路径。我们从起点开始,依次向上、向下、向左、向右搜索,直到找到终点或者无法继续搜索为止。如果找到路径,我们将路径打印出来;如果没有找到路径,我们输出没有找到路径的提示。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)