Главная arrow Поиск arrow Поиск в ширину
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

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

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

В очереди FIFO предусмотрена вставка всех вновь сформированных преемников в конец очереди, а это означает, что поверхностные узлы развертываются прежде, чем более глубокие.

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

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

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

До сих пор приведенное выше описание поиска в ширину не предвещало никаких неприятностей. Но такая стратегия не всегда является оптимальной; чтобы понять, с чем это связано, необходимо определить, какое количество времени и какой объем памяти требуются для выполнения поиска. Для этого рассмотрим гипотетическое пространство состояний, в котором каждое состояние имеет b преемников.

Корень этого дерева поиска вырабатывает b узлов на первом уровне, каждый из которых вырабатывает еще b узлов, что соответствует общему количеству узлов на втором уровне, равному b2. Каждый из них также вырабатывает b узлов, что приводит к получению b3 узлов на третьем уровне, и т.д.

А теперь предположим, что решение находится на глубине d. В наихудшем случае на уровне d необходимо развернуть все узлы, кроме последнего (поскольку сам целевой узел не развертывается), что приводит к выработке bd+1-b узлов на уровне d+1. Это означает, что общее количество выработанных узлов равно:

b + b2 + b3 + … bd + (bd+1 - b) = O(bd+1)

Каждый выработанный узел должен оставаться в памяти, поскольку он либо относится к периферии, либо является предком периферийного узла. Итак, пространственная сложность становится такой же, как и временная (с учетом добавления одного узла, соответствующего корню).

Поэтому исследователи, выполняющие анализ сложности алгоритма, огорчаются (или восхищаются, если им нравится преодолевать трудности), столкнувшись с экспоненциальными оценками сложности, такими как O(bd+1).

В таблице показано, с чем это связано. В ней приведены требования ко времени и к объему памяти при поиске в ширину с коэффициентом ветвления b = 10 для различных значений глубины решения d. При составлении этой таблицы предполагалось, что в секунду может быть сформировано 10 000 узлов, а для каждого узла требуется 1000 байтов памяти.

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

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

Глубина
Количество узлов
Время
Память
2
1100
0,11 секунды
1 мегабайт
4
111 100
11 секунд
106 мегпбайтов
6
10719 минут
10 гигабайтов
8
109
31 час
1 терабайт
10
1011
129 суток
101 терабайт
12
1013
35 лет
10 петабайтов
14
1015
3523 года
1 эксабайт

 

 

 

 

 

 

 

Второй вывод состоит в том, что требования ко времени все еще остаются важным фактором. Если рассматриваемая задача имеет решение на глубине 12, то (с учетом принятых предположений) потребуется 35 лет на поиск в ширину (а в действительности на любой неинформированный поиск), чтобы найти ее решение. Вообще говоря, задачи поиска с экспоненциальной сложностью невозможно решить с помощью неинформированных методов во всех экземплярах этих задан, кроме самых небольших.