В этой главе показано, что, рассматривая состояния на более высоком уровне детализации, чем просто как маленькие "черные ящики", можно прийти к созданию целого ряда мощных новых методов поиска и более глубокому пониманию структуры и сложности задачи.

В главах 3 и 4 рассматривался подход, согласно которому задачи можно решать, выполняя поиск в пространстве состояний. Для реализации этого подхода состояния необходимо оценивать с помощью эвристических функций, соответствующих данной проблемной области, а также проверять для определения того, не являются ли они целевыми состояниями. Однако с точки зрения таких алгоритмов поиска каждое состояние представляет собой черный ящик с неразличимой внутренней структурой. Они представлены с помощью произвольно выбранной структуры данных, доступ к которой может осуществляться только с применением процедур, относящихся к данной проблемной области, — функции определения преемника, эвристической функции и процедуры проверки цели.

В настоящей главе рассматриваются задачи удовлетворения ограничений, в которых состояния и проверка цели соответствуют стандартному, структурированному и очень простому представлению (см. раздел 5.1). Это позволяет определять алгоритмы поиска, способные воспользоваться преимуществом такой структуры состояний, и применять для решения крупных задач эвристические функции общего назначения, а не функции, относящиеся к конкретной задаче (см. разделы 5.2, 5.3). Но, возможно, еще более важно то, что применяемое стандартное представление проверки цели раскрывает структуру самой задачи (см. раздел 5.4). Это позволяет создать методы декомпозиции задачи и понять внутреннюю связь между структурой задачи и сложностью ее решения.