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

Поиск в ширину может быть реализован путем вызова процедуры Tree-Search с пустой периферией, которая представляет собой последовательную очередь (First-In-First-Out — FIFO), гарантирующую, что прежде всего будут развернуты узлы, которые должны посещаться первыми. Иными словами, к организации поиска в глубину приводит вызов процедуры Tree-Search (problem, FIFO-Queue () ). В очереди FIFO предусмотрена вставка всех вновь сформированных преемников в конец очереди, а это означает, что поверхностные узлы развертываются прежде, чем более глубокие. На рис. 3.7 показан ход поиска в простом бинарном дереве.

Рис. 3.7. Поиск в ширину в простом бинарном дереве. На каждом этапе узел, подлежащий развертыванию в следующую очередь, обозначается маркером

Проведем оценку поиска в ширину с использованием четырех критериев, описанных в предыдущем разделе. Вполне очевидно, что этот поиск является полным — если самый поверхностный целевой узел находится на некоторой конечной глубине d, то поиск в ширину в конечном итоге позволяет его обнаружить после развертывания всех более поверхностных узлов (при условии, что коэффициент ветвления b является конечным). Самый поверхностный целевой узел не обязательно является оптимальным; формально поиск в ширину будет оптимальным, если стоимость пути выражается в виде неубывающей функции глубины узла. (Например, такое предположение оправдывается, если все действия имеют одинаковую стоимость.)