Программирование на языке Пролог для искусственного интеллекта

       

это формальный аппарат для представления


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

            И / ИЛИ-графы
            И-дуги, ИЛИ-дуги
            И-вершины, ИЛИ-вершины
            решающий путь, решающее дерево
            стоимость дуг и вершин
            эвристические оценки в И / ИЛИ-графах
            "возвращенные" оценки
            поиск в глубину в И / ИЛИ-графах
            поиск с предпочтением в И / ИЛИ-графах


Содержание раздела