Искусственный интеллект. Основные понятия - страница 28

Этот код создает лабиринт, используя матрицу, где 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`. Визуализируется весь граф, а кратчайший путь отображается красным цветом.

Эти примеры демонстрируют, как каждый из методов поиска может быть использован для решения различных задач. DFS подходит для задач, где важно найти любой возможный путь, в то время как BFS используется, когда необходимо найти кратчайший путь или оптимальное решение.

Оба этих метода имеют свои преимущества и недостатки, и выбор конкретного метода зависит от характеристик задачи и требуемых критериев оптимальности. Кроме того, существуют и другие методы поиска, такие как алгоритмы A* и Dijkstra, которые также находят широкое применение в различных областях искусственного интеллекта и информатики.