Учимся использовать и реализовывать на Python алгоритм поиска в ширину (BFS) для решения реальных задач.

Давайте поговорим о популярном алгоритме, который называется «Поиск в ширину» (BFS). Затем реализуем этот алгоритм, чтобы найти решение для реальной задачи: как выбраться из лабиринта.

Алгоритмы поиска применяются для решения таких задач, которые можно смоделировать как графы. Каждый узел графа – это экземпляр задачи. Каждый поисковый алгоритм начинается с узла (исходный экземпляр – состояние) и наращивает вслед за этим узлом новые (то есть, новые экземпляры задачи), решая задачу допустимыми способами. Этот процесс останавливается, как только алгоритм находит решение (успех – конечное состояние) или не может создать ни одного нового узла (провал). Среди самых популярных алгоритмов поиска – поиск в глубину (DFS), поиск в ширину (BFS), жадный алгоритм, поиск по критерию стоимости (UCS), A*-поиск, т.д. В этой статье речь пойдет о поиске в ширину.

Поиск в ширину – это «слепой» алгоритм. Он называется «слепым», так как не учитывает стоимости перехода между вершинами графа. Алгоритм начинает работу с корневого узла (представляющего собой исходное состояние задачи) и исследует все узлы на рассматриваемом уровне, а только после этого переходит к узлам следующего уровня. Если алгоритм находит решение, то он возвращается и прекращает поиск, в противном случае наращивает от узла новое ребро и продолжает поиск. Алгоритм поиска в ширину является «полным» - это означает, что он всегда возвращает решение, если оно существует.  Точнее, алгоритм возвращает то решение, которое ближе всего к корню. Поэтому в задачах, где переход от узла к любому его дочернему узлу стоит единицу, алгоритм BFS возвращает наилучшее решение. Кроме того, чтобы исследовать узлы уровень за уровнем, он использует структуру данных под названием очередь, так что новые узлы добавляются в хвост очереди, а старые узлы удаляются из головы очереди. Псевдокод для алгоритма BFS выглядит так:

procedure BFS_Algorithm(graph, initial_vertex):
  create a queue called frontier
  create a list called visited_vertex
  add the initial vertex in the frontier
  while True:
    if frontier is empty then
      print("No Solution Found")
      break
  
    selected_node = remove the first node of the frontier
    add the selected_node to the visited_vertex list
  
    // Проверить, является ли выбранный узел решением задачи 
    if selected_node is the solution then 
      print(selected_node)
      break
  
    // Продолжить поиск от узла
    new_nodes = extend the selected_node  
    // Добавить узлы, находящиеся на переднем крае
    for all nodes from new_nodes do
      if node not in visited_vertex and node not in frontier then
      add node at the end of the queue

Из вышеприведенного кода очевидно, что для решения задачи при помощи алгоритма поиска, например, BFS, необходимо смоделировать задачу в форме графа и определить ее исходное состояние (начальный узел). После этого требуется найти такие правила, которым нужно будет следовать, чтобы наращивать узлы (экземпляры задачи). Эти правила определяются самой задачей. Последнее, что нам остается сделать – определить целевой узел или механизм, такой, при помощи которого алгоритм мог бы распознать целевой узел.

Итак, мы в общих чертах разобрались, как работает поиск в ширину, обсудим задачу, которую станем решать при помощи этого алгоритма. Допустим, имеется лабиринт, такой, как на следующем рисунке, и мы хотим перейти от входа к выходу за наименьшее возможное количество шагов. За один шаг будем считать любой переход из одной комнаты в другую. В нашем лабиринте 11 комнат, и у каждой из них – уникальное имя, например, “A”, “B”, т.д. Итак, наша цель – перейти из комнаты “S” в комнату “I”.

Итак, мы определили задачу, теперь нужно смоделировать ее в виде графа. Чаще всего для этого создается вершина на каждую комнату и ребро на каждую дверь в лабиринте. После такого моделирования получается показанный ниже граф – в нем 11 вершин и 15 ребер.

Итак, от каждой вершины мы можем перейти к соседним, начиная от вершины “S” (это начальное состояние) до вершины “I” (это целевой узел, по достижении которого задача решена). Как я уже упоминал выше, алгоритм поиска в ширину обследует все узлы на актуальном уровне, а потом перейдет к узлам следующего уровня – как показано на следующей картинке.

Теперь, смоделировав ранее определенную задачу, давайте перейдем к реализации алгоритма. Сначала нам нужно представить лабиринт в нашей программе. Как правило, для представления графа используется список смежности или таблица смежности. Но в нашем примере мы остановимся на словаре, так, чтобы ключами в этом словаре были имена вершин, а значением каждого ключа был список всех вершин, смежных с данной конкретной вершиной, как показано ниже.

graph = {
    "A": ['S'],
    "B": ['C', 'D','S'],
    "C": ['B', 'J'],
    "D": ['B', 'G', 'S'],
    "E": ['G', 'S'],
    "F": ['G', 'H'],
    "G": ['D', 'E', 'F', 'H', 'J'],
    "H": ['F', 'G', 'I'],
    "I": ['H', 'J'],
    "J": ['C', 'G', 'I'],
    "S": ['A', 'B', 'D', 'E']
  }

Далее создадим класс Node. Этот класс будет реализован как интерфейс, чтобы в будущем мы могли использовать для решения других задач алгоритм с такой же структурой. Итак, определим абстрактные методы, которые потребуется реализовать пользователям для решения каждой конкретной задачи.

from abc import ABC, abstractmethod
class Node(ABC):
  """
    Этот класс применяется для представления узла в графе 
    Этот интерфейс важно реализовать, чтобы класс для BFS получился более общим,
    и его можно было использовать для решения различных задач 
    ...


    Methods
    -------
    __eq__(self, other)
        Determines if two nodes are equal or not
    
    is_the_solution(self)
        Determines if the current node is the solution of the problem

    def is_the_solution(self)
        Extends the current node according to the rules of the problem
    
    __str__(self)
        Prints the node data
  """

  @abstractmethod
  def __eq__(self, other):
    pass

  @abstractmethod
  def is_the_solution(self, state):
    pass

  @abstractmethod
  def extend_node(self):
    pass

  @abstractmethod
  def __str__(self):
    pass

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

class BFS:
  """
    This class used to represent the  Breadth First Search algorithm (BFS)

    ...

    Attributes
    ----------
    start_state : Node
        represent the initial state of the problem 
    final_state : Node
        represent the final state (target) of the problem 
    frontier : List
        represents the stack and is initialized with the start node
    checked_nodes : List
        represents the list of nodes that have been visited throughout the algorithm execution
    number_of_steps : Integer
        Keep track of the algorithm's number of steps 
    path : List
        represents the steps from the initial state to the final state

    Methods
    -------
    insert_to_frontier(self, node)
        Insert a new node to the frontier. In this algorithm the frontier is a queue, so each new element is inserted to end of the data structure 
    
    remove_from_frontier(self)
        Remove the first element from the frontier, following the FIFO technic. The removed node is added to the checked_node list

    remove_from_frontier(self)
        check if the frontier is empty
    
    search(self)
        Implements the core of algorithm. This method searches, in the search space of the problem, a solution 
    """

  def __init__(self, start, final):
    self.start_state = start
    self.final_state = final
    self.frontier = [self.start_state]
    self.checked_nodes = []
    self.number_of_steps = 0
    self.path = []

  def insert_to_frontier(self, node):
    """
      Insert a node at the end of the frontier

      Parameters
      ----------
      node : Node
          The node of the problem that will be added to the frontier
    """
    self.frontier.append(node)
  

  def remove_from_frontier(self):
    """
      Remove a node from the beginning of the frontier
      Then add the removed node to the checked_nodes list

      Returns
      -------
      Node
        the first node of the frontier
    """
    first_node = self.frontier.pop(0)
    self.checked_nodes.append(first_node)
    return first_node


  def frontier_is_empty(self):
    """
      Check if the frontier id empty, so no solution found

      Returns
      -------
      Boolean
        True if the frontier is empty
        False if the frontier is not empty
    """
    if len(self.frontier) == 0:
      return True
    return False

  
  def search(self):
    """
      Is the main algorithm. Search for a solution in the solution space of the problem
      Stops if the frontier is empty, so no solution found or if find a solution. 
    """
    while True:

      self.number_of_steps += 1
      
      # print(f"Step: {self.number_of_steps}, Frontier Size: {len(self.frontier)} ")
      if self.frontier_is_empty():
        print(f"No Solution Found after {self.number_of_steps} steps!!!")
        break
        
      selected_node = self.remove_from_frontier()

      # проверить, является ли выбранный узел решением задачи
      if selected_node.is_the_solution(self.final_state):
        print(f"Solution Found in {self.number_of_steps} steps")
        print(selected_node)
        break

      # нарастить узел
      new_nodes = selected_node.extend_node()

      # добавить нарощенные узлы на передний край
      if len(new_nodes) > 0:
        for new_node in new_nodes:
          if new_node not in self.frontier and new_node not in self.checked_nodes:
            self.insert_to_frontier(new_node)

После этого создадим класс, представляющий узел в лабиринте. Этот класс реализует интерфейс Node, в который заложены все необходимые методы.

from BFS_Algorithm import Node 
class MazeNode(Node):
  """
    This class used to represent the node of a maze
    ...
    Attributes
    ----------
    graph : Dictionary
        represent the graph  
    value : String
        represents the id of the vertex
    parent : MazeNode
        represents the parent of the current node
  
    Methods
    -------
    __eq__(self, other)
        Determines if the current node is the same with the other 
    is_the_solution(self, final_state)
        Checks if the current node is the solution
    extend_node(self)
        Extends the current node, creating a new instance of MazeNode for each edge starts from current node 
    _find_path(self)
        Find the path (all verticies and edges from the intitial state to the final state)
    __str__(self)
        Returns the solution of the maze, the whole path vertex by vertex in order to be printed properly.
  """

  def __init__(self, graph, value):
    self.graph = graph
    self.value = value
    self.parent = None

  
  def __eq__(self, other):
    """
      Check if the current node is equal with the other node.
      Parameters
      ----------
      Other : MazeNode
          The other vertex of the graph
      Returns
      -------
      Boolean
        True: if both verticies are the same
        False: If verticies are different
    """ 
    if isinstance(other, MazeNode):
      return self.value == other.value
    return self.value == other

  
  def is_the_solution(self, final_state):
    """
      Checks if the current node is the solution
      Parameters
      ----------
      final_state : MazeNode
          The target vertex (final state) of the graph
      Returns
      -------
      Boolean
        True: if both verticies are the same, so solution has been found
        False: If verticies are different, so solution has not been found
    """
    return self.value == final_state

  
  def extend_node(self):
    """
      Extends the current node, creating a new instance of MazeNode for each edge starts from the current node
      Returns
      -------
      List
        List with all valid new nodes
    """
    children = [MazeNode(self.graph, child) for child in self.graph[self.value]]
    for child in children:
      child.parent = self
    return children

  def _find_path(self):
    """
      Find the path, all verticies and edges from the intitial state to the final state
      Returns
      -------
      List
        List with all nodes fron start to end in a row
    """
    path = []
    current_node = self
    while current_node.parent is not None:
      path.insert(0, current_node.value)
      current_node = current_node.parent
    path.insert(0, current_node.value)
    return path

  def __str__(self):
    """
      Returns the solution of the maze, the whole path vertex by vertex as well as the path lenght, in order to be printed properly.
      Returns
      -------
      str
        the solution of the problem
    """
    total_path = self._find_path()
    path = ""
    for index in range(len(total_path)):
      if index == len(total_path) - 1:
        path += f"{total_path[index]} "
      else:
        path += f"{total_path[index]} -> "


    return path + f"\nPath lenght: {len(total_path)-1}"

Последний шаг – создать все необходимые объекты и выполнить программу. После этого алгоритм вычислит и выведет на экран кратчайший путь от входа в лабиринт до выхода из лабиринта. Этот путь имеет длину 4 и выглядит так: “S” -> “B” -> “C” -> “J” -> “I”.

Заключение

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

Весь исходный код проекта выложен на GitHub здесь.