Представление задачи в терминах пространства состояний
Многие задачи искусственного интеллекта формализуются путем сведения к пространству состояний. Пространство состояний – это граф, вершины которого соответствуют ситуациям, встречающимся в задаче, а решение задачи сводится к поиску пути в этом графе. Конкретная задача определяется:
Пространством состояний
Стартовой вершиной
Целевым условием (ограничения задачи). Целевыми будут являться вершины, удовлетворяющие этим условиям.
Выбор стратегии поиска в пространстве состояний определяет порядок выбора альтернатив решения задачи.
Простейшим пространством состояний является сеть для решения транспортной задачи. В процессе поиска по сети идет вопрос о двух стоимостях:
Вычисление пути
Путешествие по нему
Наиболее очевидный путь – просмотр всех возможных путей, исключая циклические. Возможные пути удобно представить в виде поисковых деревьев.
Поисковое дерево – это семантическое дерево, в котором узлы обозначают пути, а ветви соединяют пути, отличающиеся на 1 шаг.
-
Yandex.RTB R-A-252273-3
- Министерство образования и науки Российской Федерации
- Лабораторная работа № 1
- Данные и знания
- Синтаксис языка Пролог
- Семантика языка Пролог
- Алгоритм работы Пролог-машины.
- Пример построения базы правил на Пролог
- Задание на лабораторную работу
- Лабораторная работа № 2
- Использование списков в Пролог.
- Использование накапливающего параметра
- Управление перебором
- Задание на лабораторную работу
- Лабораторная работа № 3
- Представление задачи в терминах пространства состояний
- Слепые методы поиска
- Методы эвристического поиска
- Поиск оптимального пути
- 3.4 Задание на лабораторную работу
- Лабораторная работа № 4
- Основные понятия теории игр
- Представление игры в матричной форме
- Представление игры в виде игрового дерева
- Задание на лабораторную работу