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

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

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

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

Рис. 4. 2. Задача нахождения маршрута из Иванова в Москву:

а – порядок монотонного поиска в ширину. Каждая вершина помечена ценой пути, ведущим в нее из начальной вершины (снаружи вершины) и номером ее получения в процессе поиска (внутри вершины). На последнем шаге монотонного поиска в ширину найдена целевая вершина с ценой пути, равным 10;

б – пространство состояний, иллюстрирующее цену действий, соответствующую участкам пути между городами.

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

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

На рис. 4.3 показана последовательность поиска в глубину для дерева с тремя уровнями и степенью ветвления 2. Вершины на этом рисунке пронумерованы в соответствии с последовательностью их просмотра.

Требования к объему памяти при поиске в глубину существенно меньше, чем при поиске в ширину. Как видно из рис. 4.3, в памяти необходимо хранить все вершины, инцидентные вершинам на пути из корневой вершины к любой другой, соседние вершины которой рассматриваются. Очевидно, что при степени ветвления l и глубине дерева k оценка сложности по памяти при поиске в глубину равна O(lk). Оценка сложности по времени для поиска в глубину остается такой же, как и при поиске в ширину, а именно O(l^k).

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

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