Поиск в пространстве состояний
Задачи удобнее решать, когда они формализованы, т.е. представлены в одной из стандартных форм, методы решения для которой известны. Существует несколько типовых форм представления задач. Основные из них - поиск в пространстве состояний и поиск на графах «И-ИЛИ». Процедуры поиска м/б информированными или неинформированными. Информированные - когда известна какая-либо дополнительная информация кроме минимально необходимой. Например: минимальная информация для поиска пути - матрица связи городов дорогами, к дополнительной информации относится: качество дорог, посты ДПС, длина дорог. Дополнительная информация позволяет быстрей найти наилучшее решение. Для ее использования разработаны различные эвристические алгоритмы.
Когда информация минимальна, то используются методы полного перебора в том или ином варианте.
Поиск в пространстве состояний.
Решение задачи представляется как поиск путей на множестве состояний. Есть тройка множеств (S0,F,Sy), где
S0- множество исходных состояний,
Sy - множество целевых состояний,
F- множество операторов, переводящих одни состояния в другие.
Требуется найти путь из S0 в Sy.
Решить задачу - найти последовательность операторов f1,f2,f3,…,fk,(fi принадлежит F),
f- преобразовывает начальное состояние в целевое.
Поиск удобно вести на графе. Вершины - состояния, дуги - операторы перехода.
Если Pi -> Pj , то Pi вершина-родитель, а Pj вершина-преемник, потомок, дочерняя. Раскрытие вершины - определение множества ее потомков.
Процесс поиска удобно отображать в виде дерева.
Пример:
Дерево: