Искусственный интеллект. Основные понятия. Джейд Картер
Python и библиотеку matplotlib для визуализации лабиринта и найденного пути. Рассмотрим пример кода:
```python
import matplotlib.pyplot as plt
import numpy as np
# Функция для отображения лабиринта и найденного пути
def visualize_maze(maze, path):
maze = np.array(maze)
path = np.array(path)
nrows, ncols = maze.shape
fig, ax = plt.subplots()
ax.imshow(maze, cmap=plt.cm.binary)
ax.plot(path[:, 1], path[:, 0], color='red', marker='o') # Отображение пути
ax.plot(path[0][1], path[0][0], color='green', marker='o') # Стартовая точка
ax.plot(path[-1][1], path[-1][0], color='blue', marker='o') # Конечная точка
ax.axis('image')
ax.set_xticks([])
ax.set_yticks([])
plt.show()
# Функция для рекурсивного поиска пути в лабиринте с использованием DFS
def dfs(maze, start, end, path=[]):
path = path + [start]
if start == end:
return path
if maze[start[0]][start[1]] == 1:
return None
for direction in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
new_row, new_col = start[0] + direction[0], start[1] + direction[1]
if 0 <= new_row < len(maze) and 0 <= new_col < len(maze[0]):
if (new_row, new_col) not in path:
new_path = dfs(maze, (new_row, new_col), end, path)
if new_path:
return new_path
return None
# Пример лабиринта (0 – путь, 1 – преграда)
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0]
]
start = (0, 0)
end = (4, 4)
# Поиск пути в лабиринте
path = dfs(maze, start, end)
# Визуализация результата
visualize_maze(maze, path)
```
Этот код создает лабиринт, используя матрицу, где 0 представляет путь, а 1 – стену. Алгоритм DFS используется для поиска пути от начальной до конечной точки в лабиринте. Результат визуализируется с помощью библиотеки matplotlib, где красным цветом обозначен найденный путь, а зеленым и синим – начальная и конечная точки.
2. Поиск в ширину (BFS):
Пример задачи: Найти кратчайший путь от стартовой точки к конечной точке в графе дорожной сети.
Решение: Алгоритм BFS начнет с начальной точки и исследует все смежные вершины, затем все смежные вершины этих вершин и так далее. Когда будет найдена конечная точка, алгоритм вернет кратчайший путь к этой точке, так как он исследует вершины на одном уровне графа, прежде чем переходить к следующему уровню.
Для реализации алгоритма BFS в поиске кратчайшего пути в графе дорожной сети мы также можем использовать язык Python. Для визуализации результата кратчайшего пути в графе дорожной сети мы можем использовать библиотеку `networkx` для создания и отображения графа. Рассмотрим пример кода:
```python
import networkx as nx
import matplotlib.pyplot as plt
from collections import deque
# Функция для поиска кратчайшего пути методом BFS
def bfs(graph, start, end):
visited = set()
queue = deque([(start, [start])]) # Очередь для обхода графа
while queue:
current, path = queue.popleft()
if current == end:
return path
if current not in visited:
visited.add(current)
for neighbor in graph[current]:
if neighbor not in visited:
queue.append((neighbor, path + [neighbor]))
return None
# Пример графа дорожной сети (представлен в виде словаря смежности)
road_network = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E', 'G'],
'G': ['F']
}
start