10.2.4. Поиск в глубину с итерационным заглублением.

Хорошим решением проблем поиска в глубину является использование предельного значения глубины поиска. Предельная глубина позволяет ограничить поиск только за­данным числом уровней. Это обеспечивает некоторое подобие "развертки" области по­иска в ширину при поиске в глубину.

Ограниченный поиск в глубину наиболее полезен, если известно, что решение находит­ся в пределах некоторой глубины, имеются ограничения во времени или пространство со­стояний чрезвычайно велико (как в шахматах). В таких задачах число рассматриваемых со­стояний ограничивают предельной глубиной поиска. На рис. 10.11. показан поиск в глубину для 8-головоломки, для которого предельная глубина ограничена пятью уровнями. Поэто­му именно на этой глубине возникает поперечная развертка пространства.

Такая модификация позволяет исправить нсмало недостатков как поиска в глубину, так и поиска в ширину. Итерационным заглублением [Korf, 1987] называется поиск в глубину, первая итерация которого ограничена 1 уровнем. Если цель не найдена, выпол­няется еще один шаг с предельной глубиной 2. В процессе поиска предельная глубина увеличивается на 1 на каждой итерации. На каждой итерации алгоритм выполняет поиск в глубину с учетом текущего предельного числа уровней. При этом при переходе от од­ной итерации к другой информация о пространстве состояний не сохраняется.

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

На первый взгляд кажется, что итерационное продвижение в глубину менее эффек­тивно по времени, чем поиск глубину или в ширину. Однако временная сложность алго­ритма (время выполнения алгоритма в зависимости от размерности задачи) в действительности имеет тот же самый порядок величины, что и каждый из этих алгоритмов О(Вⁿ). Объяснение этого кажущегося парадокса приведено в [Korf, 1987].

«Поскольку число вершин на данном уровне дерева растет экспоненциально с увеличением глубины, почти все время вычислений тратится на самом глубоком уровне.»

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

%инициализация

%есть состояния

10.3. Эвристический поиск.

В [Polya, 1945] эвристика определяется как "изучение методов и правил открытий и изобретений". Это слово имеет греческий корень, глагол eurisco означает "исследовать". Когда Архимед выскочил из ванны, держа золотой венец, он закричал "Эврика!", что значит "Я нашел!". В пространстве состояний поиска эвристика определяется как набор правил для выбора тех ветвей из пространства состояний, которые с наибольшей вероят­ностью приведут к приемлемому решению проблемы.

Специалисты по искусственному интеллекту используют эвристику в двух ситуациях.

1. Проблема может не иметь точного решения из-за неопределенности в поста­новке задачи и/или в исходных данных. Медицинская диагностика – пример такой проблемы. Определенный набор признаков может иметь несколько при­чин; поэтому врачи используют эвристику, чтобы поставить наиболее точный диагноз и подобрать соответствующие методы лечения. Система технического зрения - другой пример задачи с неопределенностью. Визуальные сцены час­то неоднозначны, вызывают различные (часто не связанные друг с другом) предположения относительно протяженности и ориентации объектов. Оптический обман - хорошая иллюстрация таких двусмысленностей. Системы тех­нического зрения часто используют эвристику для выбора наиболее вероятной интерпретации из нескольких возможных.

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

К сожалению, подобно всем правилам открытия и изобретения, эвристика может ошибаться. Эвристика - это только предложение следующего шага, который будет сде­лан на пути решения проблемы. Такие предположения часто основываются на опыте или интуиции. Поскольку эвристика использует такую ограниченную информацию, как опи­сание текущих состояний в списке open, то она редко способна предсказать дальнейшее поведение пространства состояний. Эвристика может привести алгоритм поиска к субоп­тимальному решению или не найти решение вообще. Это ограничение присуще эвристи­ческому поиску и не может быть устранено "лучшей" эвристикой или более эффектив­ным алгоритмом поиска [Garey и Johnson, 1979].

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

Исследование в области экспертных систем подтвердило важность эвристики как основного компонента при решении задач. Эксперт-человек, решая проблему, анализирует доступную информацию и делает вывод. Интуитивные правила ("rules of thumb"), кото­рые использует эксперт, чтобы эффективно решить ту или иную проблему, в значитель­ной степени эвристичны по природе. Такие эвристики были созданы и формализованы разработчиками экспертных систем.

Эвристические алгоритмы состоят из двух частей: эвристической меры и алгорит­ма, который использует ее для поиска в пространстве состояний