Проблема удовлетворения ограничений формулируется, как описано ниже.
Дано:
1) множество переменных;
2) области определения, из которых могут выбираться значения переменных;
3) ограничения, которым должны удовлетворять переменные. Найти:
такие значения, присваиваемые переменным, которые удовлетворяют всем заданным ограничениям.
Часто существует несколько вариантов присваивания, удовлетворяющих ограничениям. В задачах оптимизации может быть определен критерий выбора вариантов присваивания, которые удовлетворяют ограничениям.
Как оказалось, подход, предусматривающий поиск значений переменных, удовлетворяющих ограничениям, и особенно его сочетание с логическим программированием, представляет собой инструментальное средство, которое может весьма успешно применяться для решения широкого круга задач. К типичным примерам таких задач относятся задачи планирования, снабжения и управления ресурсами на производстве, на транспорте и в складском хозяйстве. Для решения этих задач необходимо распределять ресурсы по процессам, например: автобусы по маршрутам; солдат по постам; экипажи по самолетам; бригады по поездам; врачей и медсестер по дежурствам и сменам и т.д.
Рассмотрим типичный пример из области планирования. Предположим, что имеются четыре задания, а, Ь, с Я d, продолжительности которых составляют соответственно 2, 3, 5 и 4 часа. Между этими заданиями установлены ограничения предшествования: задание а должно предшествовать заданиям Ь и с, а задание b должно предшествовать заданию d (рис. 14.1). Задача состоит в том, чтобы найти значения времени начала выполнения соответствующих задач Та, ТЬ, Тс и Td таким образом, чтобы время завершения Tf выполнения всего расписания было минимальным. Допустим, что самым ранним временем запуска является 0.
Рис. 14.1. Ограничения предшествования между заданиями а, Ь, с, a
Соответствующую задачу удовлетворения ограничений можно формально определить, как описано ниже.
Переменные: Та, ть, тс, Td, Tf.
Области определения: все переменные - неотрицательна действительные числа.
Ограничения:
Та + 2 < ТЬ. Задача а, на выполнение которой требуется 2 часа, предшествует Ь;
Та +2 <Тс Задача а предшествует задаче с;
ТЬ + 3 _< Td. Задача Ь предшествует задаче d;
тс + 5 й ТС. Задача с завершается к моменту времени Tf;
Td + 4 _< Tf. Задача d завершается к моменту времени Tf. Критерий: минимизация значения Tf.
Эта задача удовлетворения ограничений имеет множество решений, причем все они позволяют обеспечить минимальное время завершения. Это множество решений можно определить следующим образом:
Та = О
ТЬ - О
2 <, Тс < А
Td = 5 Tf - 9
Определены все значения времени начала, за исключением задания с, выполнение которого может начаться в любое время в интервале от 2 до 4.
302 Часть II. Применение языка Prolog в области искусственного интеллекта
