Упражнения. 14.7. Измерьте время, необходимое программе, приведенной в листинге 14.4, для решения рассматриваемой задачи

14.7. Измерьте время, необходимое программе, приведенной в листинге 14.4, для
решения рассматриваемой задачи. Затем замените цель разметки следующим
образом:

labeling! [ff], Vars)

Опция разметки "ff (сокращение от "first fail") определяет принцип работы "до первого неудачного завершения". Это означает, что в первую очередь зна­чение присваивается переменной, которая в настоящее время имеет наимень­шую область определения. А поскольку область определения мала, то, как правило, такая переменная может с наибольшей вероятностью стать причиной неудачи. Подобная стратегия разметки предназначена для обнаружения несо­вместимости как можно быстрее, чтобы был исключен бесполезный поиск сре­ди несовместимых вариантов. Измерьте время выполнения модифицированной программы.

14.8. Обобщите программу CLP(FD) с восемью ферзями до программы с N ферзями.
Для больших значений N хорошая стратегия разметки для N ферзей состоит в
движении от "среднего", когда поиск начинается в середине области определе­
ния, а затем продолжается среди значений, отстоящих все дальше и дальше от
середины. Реализуйте эту стратегию разметки и сравните с помощью экспери­
ментов ее эффективность с последовательной разметкой (как в листинге 14.5).

Резюме

• Задачи удовлетворения ограничений формулируются в терминах переменных, областей определения переменных и ограничений между переменными.

• Задачи удовлетворения ограничений часто представляются в виде сетей огра­ничений.

• Алгоритмы обеспечения совместимости применяются к сетям ограничений и сокращают области определения переменных.

Ш Логическое программирование в ограничениях (Constraint Logic Program­ming — CLP) представляет собой сочетание подхода, связанного с удовлетворе­нием ограничений, и логического программирования.

• Системы CLP различаются по типам областей определения и ограничений. Системы логического программирования в ограничениях классифицируются по типам ограничений следующим образом: CLP(R) — действительные числа; CLP(Q) — рациональные числа; CLP(Z) — целые числа; CLP(FD) — конечные области определения; CLP(B) — логические значения.

• Потенциал системы CLP в основном зависит от потенциала специализирован­ных процедур решения задач в ограничениях, которые могут находить реше­ния для систем ограничений конкретных типов и, возможно, осуществлять оптимизацию по заданному критерию в рамках этих ограничений.

 

• Одним из аспектов программирования CLP является определение ограничений, которые являются настолько жесткими, насколько это возможно. Чем более жесткими являются ограничения, тем в большей степени они сокращают про­странства поиска и тем самым способствуют повышению эффективности. По­вышению эффективности может способствовать даже добавление избыточных ограничений.

• К типичным областям практического применения систем CLP относятся пла­нирование, снабжение и управление ресурсами.

• Б этой главе приведены программы CLP для планирования, моделирования электрических схем, решения числовых ребусов и задачи с восемью ферзями.

324 Часть II. Применение языка Prolog в области искусственного интеллекта


В данной главе рассматривались следующие понятия:

• задачи удовлетворения ограничений;

• удовлетворение ограничений;

• сети ограничений;

• алгоритмы обеспечения совместимости дуг;

• логическое программирование в ограничениях (Constraint Logic Program­ming - CLP); ,

• CLP(R),CLP(Q), CLP(PD);

• метод ветвей и границ.