Лабораторная работа №3
«Стратегии слепого поиска. Рекурсивный поиск». (4 часа).
Цель работы:Определить уровень подготовки студентов в соответствии с материалом, изученным в предыдущих курсах, являющихся базовыми для получения знаний из области искусственного интеллекта.
Теоретические сведения:
Большая часть исследований в области поиска посвящена разработке стратегий поиска.
Поиск в пространстве состояний можно вести в двух направлениях: от исходных данных задачи к цели и в обратном направлении от цели к исходным данным. Поиск на основе данных начинается с условий задачи и выполняется путем применения правил или допустимых ходов для получения новых фактов, ведущих к цели. Поиск от цели начинается с обращения к цели и продолжается путем определения правил, которые могут привести к цели, и построения цепочки подцелей, ведущей к исходным данным задачи.
Рассмотрим несколько основных стратегий, часто называемых стратегиямислепого поиска (blind search).Стратегии слепого поиска, в отличие от стратегий эвристического поиска, (heuristic search)не отдают предпочтение отдельным узлам. Особенностью этих стратегий является "равноправность" всех узлов по отношению к выбору, а отличие одной стратегии от другой определяется порядком выбора узлов, подвергающихся расширению.
Поиск "сначала в ширину" (breadth-first search)
При стратегии поиска "сначала в ширину" расширение начинается с корневого узла, затем расширяются все узлы полученные из корневого узла и т.д. Общее правило поиска таково: все узлы, глубиной d должны быть расширены прежде, чем будут расширяться узлы, глубиной d + 1. Алгоритм поиска "сначала в ширину" может быть реализован так:
Поиск "сначала в глубину" (depth-first search)
При стратегии поиска "сначала в глубину" всегда расширяется узел, находящийся на наиболее глубоком уровне дерева поиска. В том случае, если поиск обнаруживает тупиковый узел (не целевой и не расширяемый узел), алгоритм возвращается на один уровень вверх. при работе алгоритма поиска "сначала в глубину" необходимо хранить в памяти только единственный путь от корня к текущему листу вместе с оставшимися нерасширенными дочерними узлами. Для дерева поиска с фактором ветвленияb и максимальной глубиной m, поиск "сначала в глубину" требует хранить в памяти только bm узлов в отличие от bm узлов, которые необходимо хранить для реализации алгоритма "сначала в ширину".
Недостаток алгоритма поиска "сначала в глубину" заключается в том, что он может потратить значительные ресурсы, двигаясь вдоль неверного пути. Большое количество проблем характеризуются очень глубоким, а иногда - бесконечным деревом поиска. Поэтому алгоритм поиска "сначала в глубину" может никогда не "вернуться" на решение находящееся вблизи корня дерева.
|
Алгоритм поиска "сначала в глубину" может быть реализован так: