Поиск в ширину
Поиск в ширину ( BFS ) — это алгоритм поиска в древовидной структуре данных узла, удовлетворяющего заданному свойству. Он начинается с корня дерева и исследует все узлы на текущей глубине , прежде чем перейти к узлам на следующем уровне глубины. Дополнительная память, обычно очередь , необходима для отслеживания дочерних узлов, которые были обнаружены, но еще не исследованы.
Например, в шахматном эндшпиле шахматный движок может построить дерево игры из текущей позиции, применяя все возможные ходы, и использовать поиск в ширину, чтобы найти выигрышную позицию для белых. Неявные деревья (такие как игровые деревья или другие деревья решения проблем) могут иметь бесконечный размер; поиск в ширину гарантированно найдет узел решения [1] , если он существует.
Напротив, (простой) поиск в глубину , который исследует ветвь узла как можно дальше, прежде чем вернуться и расширить другие узлы, [2] может потеряться в бесконечной ветви и никогда не добраться до узла решения. Итеративный поиск в глубину позволяет избежать последнего недостатка за счет многократного изучения верхних частей дерева. С другой стороны, оба алгоритма поиска в глубину обходятся без дополнительной памяти.
Поиск в ширину можно обобщить на графы , когда начальный узел (иногда называемый «ключом поиска») [3] задается явно и принимаются меры предосторожности против двойного следования за вершиной.
BFS и его применение для поиска компонентов связности графов были изобретены в 1945 году Конрадом Цузе в его (отклоненной) докторской степени. диссертацию по языку программирования Планкалкюль , но она не была опубликована до 1972 года. [4] Он был повторно изобретен в 1959 году Эдвардом Ф. Муром , который использовал его для поиска кратчайшего пути из лабиринта, [5] [6] и позже разработан CY Lee в алгоритм маршрутизации проводов (опубликован в 1961 г.). [7]
Эта нерекурсивная реализация похожа на нерекурсивную реализацию поиска в глубину , но отличается от нее двумя способами:
