это формальный аппарат для представления
- И / ИЛИ-граф - это формальный аппарат для представления задач. Такое представление является наиболее естественным и удобным для задач, которые разбиваются на независимые подзадачи. Примером могут служить игры.
- Вершины И / ИЛИ-графа бывают двух типов: И- вершины и ИЛИ-вершины.
- Конкретная задача определяется стартовой вершиной и целевым условием. Решение задачи представляется решающим деревом.
- Для моделирования оптимизационных задач в И / ИЛИ-граф можно ввести стоимости дуг и вершин.
- Процесс решения задачи, представленной И / ИЛИ-графом, включает в себя поиск в графе. Стратегия поиска в глубину предусматривает систематический просмотр графа и легко программируется. Однако эта стратегия может привести к неэффективности из-за комбинаторного взрыва.
- Для оценки трудности задач можно применить эвристики, а для управления поиском - принцип эвристического поиска с предпочтением. Эта стратегия более трудна в реализации.
- В данной главе были разработаны прологовские программы для поиска в глубину и поиска с предпочтением в И / ИЛИ-графах.
- Были введены следующие понятия:
И / ИЛИ-графы
И-дуги, ИЛИ-дуги
И-вершины, ИЛИ-вершины
решающий путь, решающее дерево
стоимость дуг и вершин
эвристические оценки в И / ИЛИ-графах
"возвращенные" оценки
поиск в глубину в И / ИЛИ-графах
поиск с предпочтением в И / ИЛИ-графах
Содержание раздела