6.2. Слепой поиск

6.2.1. Поиск в ширину

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

Рис. 6.1. Деревья поиска в ширину при нулевая вершина (дерево глубиной дерево после нахождения последователей нулевой вершины (дерево глубиной к дерево после нахождения последователей первой вершины, дерево после нахождения последователей второй вершины (дерево глубиной

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

Оценим время и память, затрачиваемые в процессе поиска в ширину. Будем полагать, что число последователей каждой вершины равно Тогда в начале поиска в ширину мы имеем одну начальную вершину, затем последователей, потом Р последователей и т.д. В общем случае при глубине дерева поиска, равной к, число вершин, изучаемых в процессе поиска, равно

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

Посмотрим, что это будут за величины при для различных значений к (табл. 6.1). Предполагается, что 1000 вершин-последователей могут быть получены за 1 с, и что одна вершина требует 100 байт памяти. Эти значения соответствуют средним затратам времени и памяти, требуемым для решения многих иллюстративных задач типа головоломок. Из табл. 6.1 можно сделать два важных вывода. Во-первых, рост требований к памяти для решения задач поиском в ширину гораздо более серьезная проблема, чем рост требований ко времени решения тех же задач. Так, например, вполне приемлемо подождать решения задачи в течение 18 мин при но необходимость наличия 111 Мбайт памяти для решения таких сравнительно простых задач кажется слишком высокой ценой. Во-вторых, для задач, в которых помимо катастрофического увеличения требований к памяти, наблюдается стремительный рост временных затрат, не позволяющий решать реальные задачи с помощью поиска в ширину даже на современных мощных компьютерах. Это приводит к следующему заключению: Стратегии поиска, имеющие экспоненциальные оценки сложности решения задач по времени или памяти, в частности стратегия поиска в ширину, нельзя использовать для решения задач большой размерности, т.е. задач, у которых

6.2.2. Монотонный поиск в ширину

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

Таблица 6.1

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

Вернемся к задаче поиска пути из Иванова в Москву. На рис. 6. 2, б схематически показана карта участка дорог, ведущих из Иванова в Москву. Каждая из дорог, ведущих из одного пункта в другой, снабжена числовой оценкой действия. На рис. 6. 1, с показана последовательность монотонного поиска в ширину. Каждая из вершин помечена ценой пути, ведущего в эту вершину.

Рис. 6. 2. Задача нахождения маршрута из Иванова в Москву: а — порядок монотонного поиска в ширину. Каждая вершина помечена ценой пути, ведущим в нее из начальной вершины (снаружи вершины) и номером ее получения в процессе поиска (внутри вершины). На последнем шаге монотонного поиска в ширину найдена целевая вершина с ценой пути, равным 10; б — пространство состояний, иллюстрирующее цену действий, соответствующую участкам пути между городами

6.2.3. Поиск в глубину

При поиске в глубину, начиная с корневой вершины (корневая вершина находится на уровне 1), рассматриваются все инцидентные ей вершины уровня 2, начиная слева направо. Если удается найти среди них все целевые вершины, то на этом поиск прекращается. Если среди них не удается найти все целевые вершины, а максимальная глубина дерева еще не достигнута, то берется самая левая вершина уровня 2 и рассматриваются все инцидентные ей вершины уровня 3 слева направо. Если после этого все целевые вершины все еще не найдены, то берется самая левая вершина из уровня 3. Затем снова рассматриваются все инцидентные ей вершины уровня 3 слева направо и так до тех пор, пока либо не будут найдены все целевые вершины, либо достигнута максимальная глубина дерева, на которой в соответствии с рассматриваемой процедурой просмотрены все вершины, инцидентные самой левой вершине предыдущего уровня, и все целевые все еще не найдены. В последнем случае осуществляется подъем по дереву на один уровень вверх, выбор на этом уровне самой левой вершины, инцидентные которой вершины следующего уровня еще не рассмотрены, и поиск дальше среди целевых вершин по тому же принципу. И так до тех пор, пока все вершины дерева не будут рассмотрены. На рис. 6.3 показана последовательность поиска в глубину для дерева с тремя уровнями и степенью ветвления 2. Вершины на этом рисунке пронумерованы в соответствии с последовательностью их просмотра.

Рис. 6.3. Стратегия поиска в глубину

Требования к объему памяти при поиске в глубину существенно меньше, чем при поиске в ширину. Как видно из рис. 6. 3, в памяти необходимо хранить все вершины, инцидентные вершинам на пути из корневой вершины к любой другой, соседние вершины которой рассматриваются. Очевидно, что при степени ветвления и глубине дерева к оценка сложности по памяти при поиске в глубину равна Оценка сложности по времени для поиска в глубину остается такой же, как и при поиске в ширину, а именно

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

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

6.2.4. Ограниченный поиск в глубину

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