Программирование на языке ПРОЛОГ для искуственного интеллекта
aa13d773

Пространство состояний есть формализм для


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

    пространство состояний
            стартовая вершина, целевое условие,
            решающий путь
            стратегия поиска
            поиск в глубину, поиск в ширину
            эвристический поиск.


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