[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 = 'A'
end = 'G'
# Поиск кратчайшего пути в графе дорожной сети
shortest_path = bfs(road_network, start, end)
print("Кратчайший путь от", start, "к", end, ":", shortest_path)
# Создание графа и добавление вершин
G = nx.Graph()
for node in road_network: