Учимся использовать и реализовывать на 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 здесь.