Похожие презентации:
Искусственный интеллект. Поиск
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-FirstSearch)
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)Ваш поиск будет настолько
хорош, насколько хороша
будет ваша модель