Искусственный интеллект. Поиск

1.

Искусственный интеллект
Поиск

2.

Сегодня
1)Планирование
2)Проблема поиска
3)Неинформированные
методы поиска
–Поиск
в глубину
–Поиск
в ширину
–Поиск
по критерию
стоимости

3.

4.

Рефлексные агенты
1)Рефлексные агенты:
–Выбирает
действия
основываясь на текущем
восприятии (и может быть
памяти)
–Может
иметь память или
модель мира в текущий
момент времени
–Не
рассматривает будущие
последствия своих действий
–Рассматривает
только

5.

Агенты способные планировать свои
действия
1)Агенты составлять планы:
–Спрашивают
«Что если?»
–Принятие
решений
основывает на
(гипотетической)
последовательности
действий
–Может
иметь модель мира,
включающую отклик среды
на последовательность
действий

6.

Проблема поиска
1)Проблема поиска состоит
из:
–Пространства
состояний
–Функции
следования
(действия, стоимость)
–Стартовое
цель
состояние и

7.

8.

Пример: путешествие по Румынии
1)Пространство
состояний:
–Города
2)Функция
следования:
–Дорога:
перейти в
соседний город
–цена
= расстояние
3)Начальное

9.

10.

11.

Граф пространства состояний
1)Граф пространства
состояний: Математическое
представление проблемы
поиска
–Узлы
— это абстрактное
представление состояний
мира
–Ребра
— это результаты
действий
–Цель
— это определённый
набор состояний (возможно

12.

Граф пространства состояний
1)Граф пространства
состояний: Математическое
представление проблемы
поиска
–Узлы
— это абстрактное
представление состояний
мира
–Ребра
— это результаты
действий
–Цель
— это определённый
набор состояний (возможно

13.

Поисковые деревья
1)Поисковое дерево:
–«Что
если» дерево планов с выходными
значениями
–Стартовое
–Дочерние
–Узлы
состояние это корень дерева
узлы
показывают состояния; план - это путь от

14.

15.

16.

Поиск в поисковом дереве
1)Поиск:
–Добавляем
потенциальный план (узел дерева)
–Храним
периферию рассматриваемых
потенциальных планов
–Добавляем
новые узлы пока это возможно

17.

Общий вид поискового дерева
1)Ключевые понятия
–Периферия
–Расширение
–Стратегия
–Главный
исследования
вопрос: как добавлять узлы в
периферию?

18.

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

19.

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

20.

21.

Свойства поискового алгоритма
1)Полнота: гарантирует
нахождения решения, если
оно есть?
2)Оптимальность:
гарантирует нахождение
наименьшей стоимости
пути?
3)Сложность по времени?
4)Пространственная
сложность?

22.

Свойства поиска в глубину
1)Как поиск в глубину
выбирает узлы?
–Самый
левый узел в дереве
–Процесс
идет до тех пор,
пока не кончатся узлы
–Если
m конечно, то
сложность O(bm)
2)Размер пространства
состояний в периферии:
Если узлы одного уровня,
то O(bm)
–

23.

Поиск в ширину (Breadth-First
Search)

24.

25.

Свойства поиска в ширину
1)Как поиск в ширину
выбирает узлы?
–Самый
ближний к корню
узел в дереве
–Глубина
самого ближнего к
корню решения равна s
–Сложность
алгоритма O(bs)
2)Размер пространства
состояний в периферии:
–
Примерно O(bs)

26.

Поиск учитывающий стоимость
Поиск в ширину находит кратчайший путь по
количеству шагов (действий). Это не путь
наименьшей стоимости.

27.

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

28.

29.

Свойства поиска по критерию
стоимости
1)Как поиск поиск по
критерию стоимости
выбирает узлы?
–Выбирает
узел, путь к
которому самый меньший по
стоимости
–Если
стоимость решения С*
и стоимость дуги не менее ε,
то «эффективная глубина»
примерно равна С*/ε
–Сложность
С*/ε
алгоритма

30.

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

31.

Очереди
1)Все эти алгоритмы одинаковые за исключением
того, какую стратегию мы используем для
добавления новых узлов:
–Во
всех трех алгоритмах используются очереди с
приоритетом
–При
реализации алгоритмов можно использовать
один код, но с разными параметрами очереди

32.

Поиск и модели
1)В реальном мире агент не
может рассмотреть все
варианты планов
2)Планирование — это
симуляция
3)Ваш поиск будет настолько
хорош, насколько хороша
будет ваша модель