Книга: Программирование на языке Пролог для искусственного интеллекта
Резюме
Резюме
• Пространство состояний есть формализм для представления задач.
• Пространство состояний — это направленный граф, вершины которого соответствуют проблемным ситуациям, а дуги — возможным ходам. Конкретная задача определяется стартовой вершиной и целевым условием. Решению задачи соответствует путь в графе. Таким образом, решение задачи сводится к поиску пути в графе.
• Оптимизационные задачи моделируются приписыванием каждой дуге пространства состояний некоторой стоимости.
• Имеются две основных стратегии поиска в пространстве состояний — поиск в глубину и поиск в ширину.
• Поиск в глубину программируется наиболее легко, однако подвержен зацикливаниям. Существуют два простых метода предотвращения зацикливания: ограничить глубину поиска и не допускать дублирования вершин.
• Реализация поиска в ширину более сложна, поскольку требуется сохранять множество кандидатов. Это множество может быть с легкостью представлено списком списков, но более экономное представление — в виде дерева.
• Поиск в ширину всегда первым обнаруживает самое короткое решение, что не верно в отношении стратегии поиска в глубину.
• В случае обширных пространств состояний существует опасность комбинаторного взрыва. Обе стратегии плохо приспособлены для борьбы с этой трудностью. В таких случаях необходимо руководствоваться эвристиками.
• В этой главе были введены следующие понятия:
пространство состояний
стартовая вершина, целевое условие,
решающий путь
стратегия поиска
поиск в глубину, поиск в ширину
эвристический поиск.
Литература
Поиск в глубину и поиск в ширину — базовые стратегии поиска, они описаны в любом учебнике по искусственному интеллекту, см., например, Nilsson (1971, 1980) или Winston (1984). P. Ковальский в своей книге Kowalski (1980) показывает, как можно использовать аппарат математической логики для реализации этих принципов.
Kowalski R. (1980). Logic for Problem Solving. North-Holland.
Nilsson N. J. (1971). Problem Solving Methods in Artificial Intelligence. McGraw-Hill.
Nilsson N. J. (1980). Principles of Artificial Intelligence. Tioga; also Springer-Verlag, 1981.
Winston P. H. (1984). Artificial Intelligence (second edition). Addison-Wesley. [Имеется перевод первого издания: Уинстон П. Искусственный интеллект. — М.: Мир, 1980.]
Оглавление книги
