3 Неинформ поиск

1. ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ

Лекция №3 Пространство состояний. Неинформированные методы
поиска

2. Представление задач в пространстве состояний

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

3. Задача поиска в пространстве состояний

G, S , T , F , P
G – множество состояний задачи;
S – подмножество начальных состояний;
T – подмножество целевых состояний;
F – множество операторов;
P – решение задачи в виде
последовательности операторов

4. Общая характеристика методов поиска

Различают следующие стратегии поиска:
поиск на основе данных (от начального
состояния к целевому);
поиск от цели (от целевого состояния к
начальному);
двунаправленный поиск.

5. Общая характеристика методов поиска

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

6. Общая характеристика методов поиска

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

7. Шаблон алгоритма поиска

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

8. Шаблон алгоритма поиска

O:=[ s]; C:=[];
цикл пока O []
x:=first(O);
если x цель, то выход (путь найден);
переместить x из O в C;
P:<раскрытие x и обработка вершин>;
конец цикла;
Выход (решения нет)
конец

9. Методы неинформированного поиска

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

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

Достоинства:
гарантировано нахождение решения с
минимальной длиной пути.
Недостатки:
экспоненциальная сложность;
экспоненциальная степень использованного
пространства состояний.

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

Достоинства:
линейная степень использования пространства
состояний.
Недостатки:
экспоненциальная сложность;
отсутствие гарантии нахождения решения.

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

Основная идея заключается в выполнении
поиска в глубину с ограничением по
глубине (на 1-ой итерации макс. глубина 1,
на 2-ой – 2 и т.д.).
Достоинства:
линейная сложность;
гарантировано достижение цели.