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


         

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


  • И / ИЛИ-граф - это формальный аппарат для представления задач. Такое представление является наиболее естественным и удобным для задач, которые разбиваются на независимые подзадачи. Примером могут служить игры.

  • Вершины И / ИЛИ-графа бывают двух типов: И- вершины и ИЛИ-вершины.

  • Конкретная задача определяется стартовой вершиной и целевым условием. Решение задачи представляется решающим деревом.

  • Для моделирования оптимизационных задач в И / ИЛИ-граф можно ввести стоимости дуг и вершин.

  • Процесс решения задачи, представленной И / ИЛИ-графом, включает в себя поиск в графе. Стратегия поиска в глубину предусматривает систематический просмотр графа и легко программируется. Однако эта стратегия может привести к неэффективности из-за комбинаторного взрыва.

  • Для оценки трудности задач можно применить эвристики, а для управления поиском - принцип эвристического поиска с предпочтением. Эта стратегия более трудна в реализации.

  • В данной главе были разработаны прологовские программы для поиска в глубину и поиска с предпочтением в И / ИЛИ-графах.

  • Были введены следующие понятия:

            И / ИЛИ-графы

            И-дуги, ИЛИ-дуги

            И-вершины, ИЛИ-вершины

            решающий путь, решающее дерево

            стоимость дуг и вершин

            эвристические оценки в И / ИЛИ-графах

            "возвращенные" оценки

            поиск в глубину в И / ИЛИ-графах

            поиск с предпочтением в И / ИЛИ-графах


  • Содержание  Назад  Вперед