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 = 'A'

end = 'G'

# Поиск кратчайшего пути в графе дорожной сети

shortest_path = bfs(road_network, start, end)

print("Кратчайший путь от", start, "к", end, ":", shortest_path)

# Создание графа и добавление вершин

G = nx.Graph()

for node in road_network:

G.add_node(node)

# Добавление ребер между вершинами

for node, neighbors in road_network.items():

for neighbor in neighbors:

G.add_edge(node, neighbor)

# Отображение графа

pos = nx.spring_layout(G) # Положение вершин на графе

nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=1000)

# Выделение кратчайшего пути

shortest_path_edges = [(shortest_path[i], shortest_path[i + 1]) for i in range(len(shortest_path) – 1)]

nx.draw_networkx_edges(G, pos, edgelist=shortest_path_edges, width=2, edge_color='red')

plt.title('Граф дорожной сети с кратчайшим путем от {} к {}'.format(start, end))

plt.show()

```

Этот код создает граф дорожной сети на основе словаря смежности, а затем использует алгоритм BFS для поиска кратчайшего пути от начальной до конечной точки. Результат отображается с помощью библиотеки `matplotlib`. Визуализируется весь граф, а кратчайший путь отображается красным цветом.