14.7. Измерьте время, необходимое программе, приведенной в листинге 14.4, для
решения рассматриваемой задачи. Затем замените цель разметки следующим
образом:
labeling! [ff], Vars)
Опция разметки "ff (сокращение от "first fail") определяет принцип работы "до первого неудачного завершения". Это означает, что в первую очередь значение присваивается переменной, которая в настоящее время имеет наименьшую область определения. А поскольку область определения мала, то, как правило, такая переменная может с наибольшей вероятностью стать причиной неудачи. Подобная стратегия разметки предназначена для обнаружения несовместимости как можно быстрее, чтобы был исключен бесполезный поиск среди несовместимых вариантов. Измерьте время выполнения модифицированной программы.
14.8. Обобщите программу CLP(FD) с восемью ферзями до программы с N ферзями.
Для больших значений N хорошая стратегия разметки для N ферзей состоит в
движении от "среднего", когда поиск начинается в середине области определе
ния, а затем продолжается среди значений, отстоящих все дальше и дальше от
середины. Реализуйте эту стратегию разметки и сравните с помощью экспери
ментов ее эффективность с последовательной разметкой (как в листинге 14.5).
Резюме
• Задачи удовлетворения ограничений формулируются в терминах переменных, областей определения переменных и ограничений между переменными.
• Задачи удовлетворения ограничений часто представляются в виде сетей ограничений.
• Алгоритмы обеспечения совместимости применяются к сетям ограничений и сокращают области определения переменных.
Ш Логическое программирование в ограничениях (Constraint Logic Programming — CLP) представляет собой сочетание подхода, связанного с удовлетворением ограничений, и логического программирования.
• Системы CLP различаются по типам областей определения и ограничений. Системы логического программирования в ограничениях классифицируются по типам ограничений следующим образом: CLP(R) — действительные числа; CLP(Q) — рациональные числа; CLP(Z) — целые числа; CLP(FD) — конечные области определения; CLP(B) — логические значения.
• Потенциал системы CLP в основном зависит от потенциала специализированных процедур решения задач в ограничениях, которые могут находить решения для систем ограничений конкретных типов и, возможно, осуществлять оптимизацию по заданному критерию в рамках этих ограничений.
• Одним из аспектов программирования CLP является определение ограничений, которые являются настолько жесткими, насколько это возможно. Чем более жесткими являются ограничения, тем в большей степени они сокращают пространства поиска и тем самым способствуют повышению эффективности. Повышению эффективности может способствовать даже добавление избыточных ограничений.
• К типичным областям практического применения систем CLP относятся планирование, снабжение и управление ресурсами.
• Б этой главе приведены программы CLP для планирования, моделирования электрических схем, решения числовых ребусов и задачи с восемью ферзями.
324 Часть II. Применение языка Prolog в области искусственного интеллекта
В данной главе рассматривались следующие понятия:
• задачи удовлетворения ограничений;
• удовлетворение ограничений;
• сети ограничений;
• алгоритмы обеспечения совместимости дуг;
• логическое программирование в ограничениях (Constraint Logic Programming - CLP);,
• CLP(R),CLP(Q), CLP(PD);
• метод ветвей и границ.
