Искусственный интеллект. Информированный поиск

1.

Искусственный интеллект
Информированный поиск

2.

Сегодня
1) Информированный поиск
–Эвристики
–Жадный
–А*
поиск
поиск
2) Поиск на графе

3.

Поиск
Проблема поиска:
Пространство состояний (все
возможные состояния среды)
Действия
Функция следования
(действия, стоимость)
Проверка на цель
Дерево поиска
Узлы: содержат планы для

4.

Блинная сортировка
Стоимость: количество перевернутых блинов

5.

6.

Блинная сортировка
Граф пространства состояний со стоимостями

7.

Общий вид алгоритма поиска
1)function Tree-Search(problem, strategy) returns
решение или неудача
2) инициализация поиска в дереве: создание
структуры данных, получение начального
состояния из problem
3) loop do
4)
if нет узлов в периферии then return неудача
5)
выбрать следующий узел из периферии в
соответствии со strategy
6)
if узел содержит цель then return решение

8.

Очереди
Все эти алгоритмы поиска
отличаются только стратегией
изъятия узлов из периферии
Все стратегии можно
реализовать с помощью
очереди с приоритетом
На практике, для DFS и BFS
используются очереди и стеки
Можно использовать одну
реализацию, которая
использует разные структуры

9.

Поиск по критерию стоимости
(Uniform Cost Search)

10.

Поиск по критерию стоимости
1)Запомните: UCS исследует
возрастающую стоимость
2)Плюсы: полнота и
оптимальность
3)Минусы:
–Исследование
во всех
направлениях одинаковы
–Не
учитывает информацию
о том, где находится цель

11.

Информированный поиск
(Informed Search)

12.

Поисковые эвристики
Эвристика:
Функция, которая оценивает как
близко состояние к цели
Создается под конкретную задачу
Примеры: манхеттенское
расстояние, евклидово расстояние
для пути

13.

14.

15.

Жадный поиск
(Greedy Search)

16.

17.

18.

Жадный поиск
Стратегия: выбираем узел,
который, как мы думаем,
находится ближе всего к цели
Эвристика: оценка
дистанции до цели для
каждого узла
В худшем случае:
Те же проблемы, что и у DFS

19.

Поиск А*
(A* Search)

20.

Комбинирование UCS и жадного
поиска
UCS: кумулятивная стоимость пути g(n)
Жадный поиск: эвристическая стоимость пути h(n)
Поиск А*: сумма f(n) = g(n) + h(n)

21.

Поиск А* оптимален?
Стоимость плохого пути < оценка стоимости
хорошего пути

22.

Допустимость эвристик
Недопустимая эвристика
задерживает хорошие
планы в периферии
Допустимая эвристика
задерживает плохие
планы, но никогда не
превышает реальную

23.

Допустимые эвристики
Эристика h допустима если:
0 <= h(n) <= h*(n)
где h*(n) действительная стоимость ближайшей
цели
Придумывание допустимых эвристик это основное
в использовании алгоритма А* на практике

24.

Оптимальность поиска А* по дереву
А — узел с оптимальным
планом
B — узел с субоптимальным
планом
h — допустимая эвристика
Требование:
А должно покинуть
периферию до В

25.

Оптимальность поиска А* по дереву:
блокировка
Предположим В в периферии
n некоторый предок A в
периферии
Требование: n должно быть
добавлено раньше B
f(n) <= f(A)

26.

UCS и А*
Поиск по критерию
стоимости расширяется по
всем направлениям
A* расширяется в основном
к цели, но
подстраховывается, чтобы
обеспечить оптимальность