2.3. ЦЕЛЕВЫЕ СОСТОЯНИЯ
Во все наши процедуры исследования пространства состояний входит построение новых описаний состояний, исходя из старых с последующей проверкой новых описаний состояний,
с тем чтобы убедиться, не описывают ли они состояние, отвечающее поставленной цели. Часто это просто проверка того, соответствует ли некоторое описание состояния данному целевому описанию состояния, но иногда должна быть произведена более сложная проверка. Например, для игры в пятнадцать целью может быть создание конфигурации из фишек, в которой в верхних двух рядах не будет фишек с номерами, превосходящими 12. Во всяком случае, то свойство, которому должно удовлетворять описание состояния, для того чтобы это состояние было целевым, должно быть охарактеризовано исчерпывающим образом.
В некоторых задачах оптимизации недостаточно найти любой путь, ведущий к цели, а необходимо найти путь, оптимизирующий некоторый критерий (например, минимизирующий число применений операторов). С такими задачами проще всего работать, сделав так, чтобы поиск не оканчивался до тех пор, пока не будет найдено некоторое оптимальное решение. Методы поиска в пространстве состояний, рассматриваемые в следующей главе, позволяют получить оптимальное решение.
Таким образом, мы видим, что для полного представления задачи в пространстве состояний необходимо задать: а) форму описания состояний и, в частности, описание начального состояния, б) множество операторов и их воздействий на описания состояний, в) свойства описания целевого состояния.
Мы уже отмечали, что пространство состояний полезно представлять себе в виде направленного, графа. Такое представление особенно полезно для исследования различных методов поиска в пространстве состояний. В следующем разделе мы приведем некоторые необходимые сведения из теории графов.
