Техника поиска в ширину (BFS) — это систематическая стратегия поиска, которая начинается с начального узла (начальное состояние), и от начального узла поисковые действия применяются вниз по древовидной структуре в порядке ширины.
Поисковое действие состоит из:
Выбор узла в качестве текущего узла
Проверка текущего узла на соответствие критериям целевого теста
Если целевое состояние не достигнуто, выберите следующий узел в порядке ширины
Поиск заканчивается либо тогда, когда все узлы были просмотрены, либо если цель найдена.
В примере с ключом от машины порядок поиска BFS соответствует последовательности узлов: 1, 2, 3, 4, 5… и т. д. в порядке ширины. Поиск BFS сначала пройдет по всем комнатам, затем по всем столам, затем по всем ящикам в этой последовательности.
1.( Дом )
/ | \
/ | \
2.(комната A) 3.(комната B) 4.(комната C)
/ *car key
/ |
5.(стол1) 6.(стол2)
Зачем нужен алгоритм поиска в ширину?
Есть несколько причин, по которым вам следует использовать алгоритм BFS для обхода структуры данных графа. Ниже приведены некоторые важные особенности, которые делают алгоритм BFS необходимым:
Алгоритм BFS имеет простую и надежную архитектуру.
Алгоритм BFS помогает оценивать узлы в графе и определяет кратчайший путь для обхода узлов.
Алгоритм BFS может пройти по графу за наименьшее возможное количество итераций.
Итерации в алгоритме BFS плавные, и этот метод не может застрять в бесконечном цикле.
По сравнению с другими алгоритмами результат алгоритма BFS имеет высокий уровень точности.
BFS может быть реализована с использованием списка или структуры данных очереди. Изначально список содержит только начальное состояние. Алгоритм поиска включает в себя повторное тестирование и удаление первого узла из начала списка, а затем поиск и добавление преемников узла в список. Этот процесс продолжается до тех пор, пока первый узел в списке не станет целевым состоянием или список не станет пустым.
Продолжая пример с ключом от машины, список инициализируется следующим образом:
[ 1 (дом) ]
После того, как узел 1 не прошел целевой тест, он удаляется из списка, а узлы-преемники 2, 3, 4 добавляются к списку:
[2. (комната А), 3 (комната Б), 4 (комната С)]
Когда узел 2 проверен и удален, а узел 5 добавлен:
[3 (комната B), 4 (комната C), 5 (стол 1)]
Допустим , что, поиск завершается успешно, когда узел 3 идентифицируется как целевое состояние, т. е. ключ от машины находится в комнате B.
==========================================
BFS — алгоритм исчерпывающего поиска. Это просто реализовать. И его можно применить к любой задаче поиска. Сравнивая BFS с алгоритмом поиска в глубину, BFS не страдает от какой-либо потенциальной проблемы с бесконечным циклом, которая может привести к сбою компьютера, тогда как поиск в глубину идет вглубь. Одним из недостатков BFS является то, что это «слепой» поиск, когда пространство поиска велико, производительность поиска будет низкой по сравнению с другими эвристическими поисками.
BFS будет хорошо работать, если пространство поиска невелико. Он работает лучше всего, если целевое состояние находится в верхней левой части дерева. Но он будет работать относительно плохо по сравнению с алгоритмом поиска в глубину, если целевое состояние находится в нижней части дерева. BFS всегда найдет кратчайший путь, если вес ссылок одинаков. Таким образом, BFS является полным и оптимальным. Однако, использование памяти в BFS плохое, поэтому мы можем сказать, что BFS требуется больше памяти по сравнению с DFS.
Sample of Python code
boris@boris-All-Series:~/BFS$ cat searchBFS2.py
from queue import Queue
class Graph:
# Constructor
def __init__(self, num_of_nodes, directed=True):
self.m_num_of_nodes = num_of_nodes
self.m_nodes = range(self.m_num_of_nodes)
# Directed or Undirected
self.m_directed = directed
# Graph representation - Adjacency list
# We use a dictionary to implement an adjacency list
self.m_adj_list = {node: set() for node in self.m_nodes}
# Add edge to the graph
def add_edge(self, node1, node2, weight=1):
self.m_adj_list[node1].add((node2, weight))
if not self.m_directed:
self.m_adj_list[node2].add((node1, weight))
# Print the graph representation
def print_adj_list(self):
for key in self.m_adj_list.keys():
print("node", key, ": ", self.m_adj_list[key])
def bfs(self, start_node, target_node):
# Set of visited nodes to prevent loops
visited = set()
queue = Queue()
# Add the start_node to the queue and visited list
queue.put(start_node)
visited.add(start_node)
# start_node has not parents
parent = dict()
parent[start_node] = None
# Perform step 3
path_found = False
while not queue.empty():
current_node = queue.get()
if current_node == target_node:
path_found = True
break
for (next_node, weight) in self.m_adj_list[current_node]:
if next_node not in visited:
queue.put(next_node)
parent[next_node] = current_node
visited.add(next_node)
# Path reconstruction
path = []
if path_found:
path.append(target_node)
while parent[target_node] is not None:
path.append(parent[target_node])
target_node = parent[target_node]
path.reverse()
return path
graph = Graph(6, directed=False)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(0, 3)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(2, 5)
graph.add_edge(3, 4)
graph.add_edge(3, 5)
graph.add_edge(4, 5)
graph.print_adj_list()
path = []
path = graph.bfs(0, 5)
print(path)
boris@boris-All-Series:~/BFS$ python3 searchBFS2.py
node 0 : {(3, 1), (1, 1), (4, 1), (2, 1)}
node 1 : {(0, 1), (2, 1)}
node 2 : {(0, 1), (1, 1), (5, 1), (3, 1)}
node 3 : {(0, 1), (5, 1), (4, 1), (2, 1)}
node 4 : {(0, 1), (5, 1), (3, 1)}
node 5 : {(3, 1), (4, 1), (2, 1)}
[0, 3, 5]
No comments:
Post a Comment