LITMIR.BIZ

Скачать книгу

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

Скачать книгу