Применение метода CLP для обработки действительных чисел - CLP(R)

Рассмотрим следующий запрос: ?- 1 + х = 5.

В языке Prolog такое согласование оканчивается неудачей, поэтому ответом сис­темы Prolog является "по". Но если пользователь имел в виду, что X — число, а зна­ком "+ " обозначена операция арифметического сложения, то ответ X = 4 был бы бо­лее приемлемым. Использование вместо знака "=" встроенного предиката is не по­зволяет полностью добиться такой интерпретации, а система CLP(R) позволяет. В соответствии с применяемыми синтаксическими соглашениями (версии SICStus Prolog) этот запрос CLP(R) может быть записан следующим образом:

?- { 1 + X = 5 !. % Числовое ограничение X = 4

Это ограничение обрабатывается специализированной процедурой решения задач в ограничениях, которая способна выполнять операции с действительными числами и обычно может находить решения систем уравнений, заданных в виде равенств или неравенств определенных типов. В соответствии с применяемыми синтаксическими соглашениями множество ограничений вставляется в предложение Prolog в виде це­ли, заключенной в фигурные скобки. Отдельные ограничения разделяются запятыми и точками с запятой. Как и в языке Prolog, запятая означает конъюнкцию, а точка с запятой - дизъюнкцию. Поэтому конъюнкция ограничений Cl. C2 и СЗ может быть записана так: <; Cl, C2, сз)

Каждое ограничение задается в следующей форме:

Exprl Operator Expr2

И Exprl, и Бхрг2 представляют собой обычные арифметические выражения. Они могут также, в зависимости от конкретной системы CLP(R), включать вызовы неко­торых стандартных функций, таких как sin;X). В качестве Operator может быть задан один из следующих операторов, в зависимости от типа ограничения.

• =. Проверка на равенство.

• =\=. Проверка на неравенство.

• <,_<, >, >=. Арифметическое сравнение.

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

Теперь рассмотрим некоторые простые примеры использования этих ограничений и, в частности, определим, насколько более гибкими они являются по сравнению с обычными встроенными средствами языка Prolog.

В языке Prolog для преобразования значений температуры из градусов Цельсия в градусы Фаренгейта может применяться встроенный предикат is, например, сле­дующим образом:

convert; Centigrade, Fahrenheit) :-Centigrade is (Fahrenheit - 32)*5/9.

С помощью этой программы можно легко преобразовать значение температуры 35 градусов Цельсия в градусы Фаренгейта, но обратное преобразование невозможно, поскольку предполагается, что при использовании встроенного предиката is все, что находится справа от него, должно быть конкретизировано. Для того чтобы обеспе­чить работу этой процедуры в обоих направлениях, необходимо проверить, являются ли ее параметры конкретизированы значением числа, а затем использовать формулу преобразования, подготовленную соответствующим образом для каждого случая. Но все эти операции могут быть реализованы гораздо более изящно в системе CLP(R), где одна и та же формула, интерпретируемая как числовое ограничение, действует в обоих направлениях, как показано ниже.

convert E Centigrade, Fahrenheit) :-

{ Centigrade = [Fahrenheit - 32) *S/9 ). ?- convert ( 35, F). F = 95

?- convert ( C, 95) . С = 35

Такая программа CLP{R) работает, даже если не конкретизирован ни один из двух параметров:

?- convert! С, F). t F = 32.0 + 1.8*С }

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

Типичная процедура решения задач в ограничениях способна решать системы ли­нейных уравнений, заданных с помощью операторов проверки на равенство и нера­венство, а также операторов арифметического сравнения. Ниже приведены подобные примеры.

?- ( 3*Х - 2*Y = 6, 2*Y = X}.

X - 3.0

У - 1.5

?- { 1 =< Х-2, Z =< 6-Х, 2 + 1 = 2).

Е = 1.0

{X >= 3.0}

(X=< 5.0}

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

minimize! Expr) maximize( Expr)

В этих двух предикатах Expr — это линейное выражение в терминах перемен­ных, которые появляются в линейных ограничениях. Указанные предикаты находят значения переменных, удовлетворяющих этим ограничениям, и соответственно ми­нимизируют или максимизируют значение выражения, как показано ниже.

Глава 14.Логическое программирование в ограничениях

■?- {	X =< 5), maximize(X).
X -	5.0
?- {	X =< 5, 2 =< X}, minimize ( 2*X + 3)
X =	2.0
?- {	X >-2, Y >=2, Y -< X+l, 2*Y -< 3-Х,
X -	4.0
Y =	2.0
Z =	14.0
?- {	X =< 5}, minimize! X).
no

S

2*X + 3*Y}_r maximize(2)

В последнем примере значение X не имеет нижней границы, поэтому цель мини­мизации не достигается.

Следующие предикаты CLP(R) находят супремум (наименьшую верхнюю грань) или инфимум (наибольшую нижнюю грань) любого выражения:

supf Expr, MaxVal)

inf( Expr, MinVal)

где Expr — это линейное выражение в терминах переменных с линейными ограни­чениями, a MaxValи MinVal — максимальное и минимальное значения, которые принимает это выражение в тойобласти, в которойудовлетворяются ограничения. В отличие от предикатов maximize/1 иminimize/1, переменные в выражении Expr не конкретизируются крайними значениями, как показано ниже,

?- { 2 =< Х_г X =< 5), inf(X, Min), sup; X, Мак].

Max =5.0

Min -2.0

(X >- 2.0J

{X =< 5.0У

?- (X >=2, Y >=2, Y -< X+l, 2*Y=< 8-X, 2 = 2*X + 3*Y},

sup ( Z,Max), inflZ.Min) , maximize ( Z) .

X = 4.0

Y = 2 . 0

Z = 14.0

Мак- 14.0

Min = 10.0

Приведенный в начале этой главы простой пример составления расписания с за­даниями а, Ь, с и d может быть представлен в системе CLP(R) в следующем непо­средственном виде:

?- (Та + 2=<= ТЬ, %	Задание
Та + 2 =< Тс, %	Задание
ТЬ + 3 =< Td, %	Задание
Тс + 5 =< Tf, %	Задание
Td + 4 = < Tf }, %	Задание
minimize( Tf),
Та = 0.0
Tb = 2.0
Td = 5.0
Tf » 9.0
{Тс -< 4.0}
{Тс >= 2.0>

а предшествует заданию Ь а предшествует заданию с Ь предшествует заданию d с завершается ко времени завершения Tf

d завершается ко времени завершения Tf

Следующий пример еще более наглядно показывает, насколько гибкими являются ограничения по сравнению со стандартными арифметическими средствами Prolog. Рассмотрим применение предиката fib { N, F) для вычисления Ы-го числа Фибо­наччи Г следующим образом: F (0) -1, F(l)«l, Г(2)»2, F<3)-3, Г(4)=5и т.д. В об­щем для N > 1, F(N> = F(N-l) + F (N-2). Ниже приведено определение процедуры fib/2 на языке Prolog.

fib( и, F) :-N=0, F=l

И-1, F=l

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

В>1,

N1 is H-l, fib(Hl.Pl), N2 is H-2, fib{N2,F2), F is Fl + F2.

Предполагается, что эта программа должна использоваться таким образом: ?- fib(6, г} . F=13

Но рассмотрим следующий вопрос, в котором предпринята попытка решить об­ратную ^задачу: ?- fib CM, 13) .

Он приводит к ошибке, поскольку цель N > 1 выполняется с неконкретизирован-ным значением к. Но эта же программа, записанная с помощью определений CLP(R), может использоваться более гибко, как показано ниже,

fib ( N, Т) :-i N = О, F - 13

'(И - 1, F-1}

t К > 1, F = F1+F2, HI -S-1, N2 = Н-2Ь fib(HI, Fl), fib(N2, F2>.

Эта программа может быть вызвана на выполнение в противоположном направле­нии. Например, она позволяет следующим образом определить по числу Фибоначчи F его индекс Ы: ?- fib( N, 13) . N = 6

Но данная программа все еще сталкивается с затруднениями после получения во­проса, для которого нельзя найти удовлетворительного решения: ?- fib{ Ы, 4}.

Эта программа постоянно предпринимает попытки найти такие два числа Фибо­наччи F1 и F2, что Fl + F2 = 4. Она продолжает вырабатывать все более крупные значения F1 и F2 в расчете на то, что в конечном итоге их сумма будет равна 4. Про­грамме неизвестно, что после того как сумма чисел Фибоначчи превысит 4, она будет лишь возрастать и поэтому никогда не станет равной 4. Наконец, этот бессмыслен­ный поиск оканчивается переполнением стека. Решение, которое показывает, как исправить эту ситуацию, введя некоторые очевидные дополнительные ограничения в процедуру fib, является очень поучительным. Легко понять, что для всех N имеет место F(N) £ N. Поэтому переменные N1, Fl, N2 и F2 в данной программе должны всегда удовлетворять следующим ограничениям: F1 >= N1, F2 >= N2. Эти дополни­тельные ограничения можно добавить к ограничениям в третьем дизъюнкте в теле предложения fib. В результате эта программа принимает вид

fib( S, F) :-

{ Я > 1, F = F1+F2, Hi = Н-1, N2 = 8-2,

F1 >= HI, F2 >- Н2}, % Дополнительные ограничения fib(HI, Fl) , fib( 82» F2) .

Указанные дополнительные ограничения позволяют программе определить, что приведенный выше вопрос должен окончиться неудачей:

?- fib С К, 4) .

по

При рекурсивных вызовах процедуры fib фактически развертывается выражение

для F в условии F = 4:

4 - F - Fl + F2 =

Fl' + F2' + F2 =

Р1< ' + F2" + F2" + F2

Глава 14. Логическое программирование в ограничениях

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

Рассмотрим кратко системы CLP(Q), которые являются ближайшими аналогами систем CLP(R). Различие между ними состоит в том, что в системах CLP(R) действи­тельные числа аппроксимируются числами с плавающей точкой, а областью опреде­ления Q являются рациональные числа, т.е. дроби, состоящие из двух целых чисел. Они могут использоваться в качестве другого способа аппроксимации действитель­ных чисел. Область определения Q может иметь преимущество над областью опреде­ления R (представленной с помощью чисел с плавающей точкой) в том, что решения некоторых арифметических ограничений могут быть определены в виде дробей точ­но, а числа с плавающей точкой позволяют получить лишь приближенные значения. Соответствующий пример приведен ниже.

?- ( X=2*Y, Y=l-X }.

Процедура решения CLP(Q) дает следующий ответ: X = 2/3, Y = 1/3. Процедура решения CLP{R) сообщает приблизительно такой ответ: X = 0.666666666, Y = 0.333333333.

Упражнение

14,3.Покажите, как при выполнении запроса "?-fib( N, 4; .", приведенного вы­ше в качестве примера, процедура решения задач в ограничениях позволяет обнаружить, что накопленные ограничения не могут быть удовлетворены.

Планирование с помощью метода CLP

Задачи составления расписаний, которые рассматриваются в этом разделе, состо­ят из перечисленных ниже элементов.

• Множество задач7;, ...,Т_:..

• Продолжительности Di........ D_n задач.

• Ограничения предшествования, заданные как отношения, следующим образом:

prec( Ti, ?,!

Такое ограничение указывает, что выполнение задания Т. должно закончиться до того времени, как может начаться выполнение задания Tj.

• Множество процессоров::., которые могут применяться для выполнения заданий.

• Ограничения на ресурсы: какие задания могут выполняться теми или иными процессорами (какие процессоры являются подходящими для выполнения конкретного задания).

Задача состоит в том, чтобы составить расписание, время завершения которого
является минимальным. В расписании назначается процессор для каждого задания и
задается время начала выполнения каждого задания. Безусловно, расписание должно
удовлетворять всем ограничениям предшествования и распределения ресурсов: каж­
дое задание должно быть выполнено подходящим процессором, причем ни один про­
цессор не может выполнять два задания одновременно. В соответствующей формули­
ровке CLPзадачи составления расписания применяются следующие переменные:
значение времени начала, S1, ..., Sn, и имена процессоров, назначенных для каждого
задания, Р1........ Рп.

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

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

любого задания. Таким образом, достаточно добиться удовлетворения ограничений, соответствующих отношениям предшествования между заданиями. Как уже было показано во вступительном разделе данной главы, подобная задача может быть сформулирована очень просто. Предположим, что имеется следующее ограничение предшествования, касающееся заданий а и Ь, — prec ( a, b). Допустим, что про­должительность задания а равна Da, а значения времени начала выполнения заданий а и b равны Sa и Sb. Чтобы было удовлетворено ограничение предшествования, зна­чения Sa и sb должны соответствовать следующему ограничению: { За + Da -< Sb }

Кроме того, требуется обеспечить, чтобы ни одно задание Т. не могло начаться до времени 0, а все задания должны быть выполнены ко времени завершения расписа­ния FinTime следующим образом: { Si >- 0, Si + Di =< FinTime }

Для определения конкретной задачи составления расписания введем следующие предикаты: tasksC [Taskl/Durationl, Task2/Duration2, ...])

Приведенный ниже предикат задает список всех имен заданий и значений их продолжительности. prec( Taskl, Task2)

Этот предикат определяет отношение предшествования между заданиями Taskl и Тазк2. resource! Task, [ Procl, Proc2, ...])

Данный предикат указывает, что задание Task может быть выполнено любым из

процессоров Procl, Proc2................. Обратите внимание на то, что это - спецификация

задачи составления расписания, аналогичная используемой в главе 12 (раздел 12.3), где для составления наилучшего расписания применялся эвристический поиск по за­данному критерию. Но фактически применяемая здесь формулировка является не­много более общей. В главе 12 ограничения на ресурсы заключались лишь в том, что лимитировалось количество процессоров, но все эти процессоры считались пригод­ными для выполнения любого задания.

Вначале рассмотрим простой случай без ограничений на ресурсы. Один из спосо­бов решения задачи планирования такого рода см. в разделе 14.1. Программа, приве­денная в листинге 14.1, является более общей реализацией той же идеи. В этой про­грамме подразумевается использование некоторого определения конкретной задачи планирования с использованием представления, описанного выше. Основным преди­катом является schedule! Schedule, FinTime)

где Schedule — наилучшее расписание для задачи, которая определена с помощью предикатов tasks и prec, a FinTime — время завершения расписания. Расписание имеет следующее представление:

Schedule = [ Taskl/Startl/Durationl, Task2 /Start2/Duration2, ...]

Листинг 14.1. Планирование с учетом ограничений предшествования и без учета ограничений на ресурсы

I Планирование с помощью метода ■.::.■..' С неограниченными ресурсами

scheduler Schedule, FinTime) :-tasks С TasksDurs), precedence_constr{ TasksDurs, Schedule, FinTime), % Сформировать отношения

% предшествования minimize! FinTime).

precedence_constr( [1, [], FinTime).

Глава 14. Логическое программирование в ограничениях

precedence_constr( [T/D ] TDs], [T/Start/D | Rest], FinTime) :-

{ Start >- 0, % Выполнение должно начаться не раньше времени О

Start + D =< FinTime}, % Временем завершения должно быть FinTime precedence_constr( TDs, Rest, FinTime), prec_constr( T/Start/D, Rest).

pzec_constx [ _, []) .

prec_constr( T/S/D, [T1/S1/D1I Rest]) :-

( prec( T, Tl;, !, t S+D -< SI}

s precl Tl, T) , ! , { Sl + Dl =< S)

true ),

prec_constr( T/S/D, Rest).

% Список заданий, подлежащих планированию

tasks; [ tl/5, t2/7, t3/10,t4/2, t5/9L>.

% Ограничения предшествования

prec[ tl, t2). prec( tl,t-4) . prec ( t2, t3). prec i t4, t5).

Процедура schedule, по сути, выполняет описанные ниже действия.

1. Формирует ограничения неравенства между значениями времени начала в рас­писании, соответствующие отношениям предшествования между заданиями.

2. Минимизирует время завершения с учетом сформированных ограничений не­равенства,

Поскольку все ограничения являются линейными неравенствами, данная задача сводится к задаче линейной оптимизации, для решения которой в системе CLP(R) предусмотрены встроенные средства.

Предикат pracedeiice_constr« TasksDuraticns, Schedule, FinTime)

формирует ограничения между значениями времени начала заданий в расписании Schedule и значением времени завершения расписания FinTime. Предикат prec_constr[ Task/Start/Duration, RestOfSchedule)

формирует ограничения между значением времени начала Start задания Task и значениями времени начала заданий в списке RestOfSchedule таким образом, что­бы эти ограничения на значения времени начала соответствовали ограничениям предшествования между заданиями.

В программе, приведенной в листинге 14.1, содержится также определение про­стой задачи составления расписания с пятью заданиями. Эта программа-планировщик вызывается на выполнение с помощью следующего вопроса:

?- schedule; Schedule, FinTime) .

FinTime = 22,

Schedule = [tl/0/5, t2/5/7, t3/12/10,t4/S4/2,t5/S5/9],

(SS =< 13)

{S4 >= 5}

(S4-S5 =< -2)

Для заданий t4 и t5 предусмотрена определенная степень свободы в отношении времени их начала. При всех значениях времени начала 3 4 и S5 для заданий t4 и t5 в пределах указанных интервалов достигается оптимальное время завершения распи­сания. Три другие задания (tl, t2 и t3) находятся на критическом пути, и время их начала не может сдвигаться.

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

Теперь рассмотрим задачи планирования более сложного типа — с ограничениями на ресурсы. Например, в задаче планирования, приведенной в главе 12 (см. раздел 12.3, рис. 12.6), имеются всего три процессора. Хотя любой из процессоров может выполнять какое угодно задание, это ограничение означает, что одновременно могут обрабатываться не больше трех заданий.

На этот раз приходится иметь дело с ограничениями следующих двух типов.

1. Отношения предшествования между заданиями.

2. Ограничения на ресурсы.

Ограничения предшествования могут обрабатываться таким же образом, как и в программе, приведенной в листинге 14.1. Теперь рассмотрим ограничения на ресур­сы. Для удовлетворения ограничений на ресурсы необходимо решить задачу назна­чения некоторого процессора для каждого задания. Такую задачу можно решить, введя для каждого задания Ti еще одну переменную, Pi, возможными значениями которой являются имена процессоров. В соответствии с этим необходимо немного расширить представление расписания:

Schedule = [ Taskl/Frocl/Startl/Durl, Task2/Proc2/Start2/Dur2, ...]

где Procl — процессор, назначенный заданию Taskl, Startl — время начала зада­ния Taskl и Durl — его продолжительность. Теперь с использованием такого пред­ставления расписания можно разработать программу, приведенную в листинге 14.2, как расширение программы из листинга 14.1. Основным предикатом снова является schedule ( BestSchedule, BestTime)

Этот предикат позволяет составить расписание с минимальным временем завер­шения BestTime. Ограничения неравенства, налагаемые на значения времени начала с учетом отношений предшествования между заданиями, снова формируются с по­мощью следующего предиката:

precedence^onstr ( TasksDurations, Schedule, FinTime!

Листинг 14.2. Программа составления расписания CLP(R)для задач с ограничениями предшествования и ограничениями на ресурсы

& Планирование с помощью метода CLP с ограниченными ресурсами

schedule ( BestSchedule, EestTime) :-tasks{ TasksDurs), precedence_constr{ TasksDurs, Schedule, FinTime), % Задать неравенства,

\ обозначающие отношения предшествования
initialise bound, % Инициализировать предельное

% значение времени завершения
assign_processors{ Schedule, FinTime), '--. Назначить процессоры для заданий
minimize( FinTime),
update_bound( Schedule, FinTime),
fail \ Выполнить перебор с возвратами, чтобы найти другие расписания

bestsofar( BestSchedule, EestTime) . % Наилучшее к этому времени расписание

% precedence_constr { TasksDurs, Schedule, FinTime):

% На основании исходных данных, которые представляй^ собой задания и значения

их продолжительности, сформировать структуру Schedule, состоящую -^:
% переменных, которые представляют время начала выполнения заданий.

% Значения этих переменных и времени завершения FinTime определяются

Щ с учетом ограничений предшествования, сформулированных в виде неравенств

precedence_constr{ [], [], FinTime).

precedenee_constr ( [T/D | TDs), [T/Proc/Start/D [ Rest], FinTime) :-

{ Start >- 0, % Выполнение должно начаться не раньше времени 0

Start + D =< FinTime } , % Временем завершения должно быть FinTime

precedence_Constr( TDs, Rest, FinTime;,

Глава 14. Логическое программирование в ограничениях

prec_Constr( T/Proc/Start/D, Rest) .

prec_constr( _, [}) .

prec_constr[ T/P/S/D, [T1/P1/S1/D1 I Rest]) :-( ~prec( T, 11) , 1 , { S+D =< SI}

precf Tl, T) , i, { Sl+Dl =< S}

true ) , prec_constr ( T/P/S/D, Rest) .

I assign_prccessors( Schedule, FinTime}:

% назначить процессоры заданиям в расписании Schedule

assign^processors I [] , FinTime).

assign_processors { [T/P/S/D | Rest], FinTime} :-

assign_Drocessors( Rest, FinTime),

resource; T, Processors), % Задание Т может быть выполнено любым

4 процессором из списка Processors
member( p, Processors), % Выбрать один из подходящих процессоров

resource_constr ( T/P/S/D, Rest}, % Учесть ограничения на ресурсы
bestsofarf _, BestTimeSoFarj,
( FinTime < BestTimeSoFar} . % Новое расписание лучше любого

% найденного к этому времени

% resource__coristr ( ScheduledTask, TaskList) :

сформировать ограничения так, чтобы гарантировалось отсутствие I противоречивых назначений ресурсов в списках ScheduledTasJc и TaskList

resource_constr( _, []) .

resource COnetr< Task, [Taskl I Rest]) • ;-

no_conflict( Task, Taskl), resource_constr ( Task, Rest).

no_conflict[ T/P/S/D, T1/P1/S1/D1)

P \« PI, ! % Разные процессоры

prec{ T, Tl) , ! % Ограничения уже учтены

prec{ Tl, T) , ! % Ограничения уже учтены

( -S+D =< 51 % Тот же процессор,- перекрытие по времени отсутствует

Sl+Dl =< S} . initialise_bound : -retract (feestsefar (_,_}>, fail

assert! bestsofarf dummy_schedule, 9999) ) . % Предполагается, что время Ч завершения ни при каких условиях не превышает 9999

% update_bound[ Schedule, FinTime):

* обновить определение наилучшего расписания и значение времени

update_bound( Schedule, FinTime) :-retract ( bestsofar[_,_)), ! , assert( bestsofar( Schedule, FinTime]).

% Список заданий, которые должны быть включены в расписание

tasks! [tl/4,t2/2,t3/2, t4/20, t5/20, t6/ll, t7/ll]) .

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

- Ограничения предшествования

ргес[ tl, t4), prec( tl, t5). precC t2, t4). prec( t2, t5). prect t2, t6). prec( t3, t5). prect t3, t«>. prec< t3, tl).

i resource) Task, Processors):

% любой процессор из списка Processors, пригодный для выполнения задания Task

resource) _, [1,2,3]). % Три процессора, причем любой из них пригоден

% для выполнения любого задания

Данная программа почти аналогична приведенной в листинге 14.1. Единственное небольшое различие между ними связано с разными представлениями расписания.

Теперь рассмотрим ограничения на ресурсы. Задачу составления расписания с учетом этих ограничений нельзя решить столь же эффективно, как и с учетом огра­ничений предшествования. Чтобы удовлетворить ограничения на ресурсы, необходи­мо найти оптимальное распределение процессоров но заданиям. Для этого требуется выполнить поиск среди возможных вариантов назначения, а общего способа выпол­нения такого поиска за время, измеряемое некоторым полиномом, не существует. В программе, приведенной в листинге 14.2, такой поиск выполняется с помощью .метода ветвей и границ, который можно кратко описать следующим образом. С по­мощью недетерминированного способа один за другим формируются варианты распи­сания (этот способ состоит в том, что формируется расписание и вызывается цель fail). Наилучшее расписание из всех составленных до сих пор вносится в базу дан­ных как факт. После составления каждого нового расписания в базе данных обнов­ляется расписание, наилучшее к этому времени (которое обозначается как bestsofar). При составлении нового расписания наилучшее к этому моменту время завершения используется в качестве верхней границы для времени завершения ново­го расписания. Как только обнаруживается, что новое частично сформированное рас­писание не позволяет достичь сокращения времени завершения по сравнению с наи­лучшим к данному моменту, происходит отказ от дальнейшей работы над этим рас­писанием.

Эта идея реализована в программе, приведенной в листинге 14.2, следующим об­разом. Процедура assign_processors недетерминированно назначает заданиям один за другим подходящие процессоры. Назначение процессора заданию приводит к появлению дополнительных ограничений на значения времени начала, поскольку не­обходимо обеспечить, чтобы не перекрывалось время между заданиями, назначенны­ми одному и тому же процессору. Поэтому после каждого назначения процессора за­данию частично составленное расписание улучшается. После каждого такого улуч­шения частично составленного расписания оно проверяется для определения того, есть ли какая-либо возможность улучшить расписание, которое к данному времени является наилучшим. Для того чтобы текущее частично составленное расписание предоставляло хотя бы малейшую такую возможность, его значение FinTime должно быть меньше по сравнению с наилучшим временем, достигнутым до сих пор. В про­грамме это условие учитывается с помощью следующего ограничения: ( FinTime < BestTimeSoFar }

Если это ограничение несовместимо с другими текущими ограничениями, то дан­ное частично составленное расписание не дает ни малейшей возможности для улуч­шения. А поскольку для окончательного составления этого расписания необходимо удовлетворить еще больше ограничений на ресурсы, то фактически время его завер­шения может в конечном итоге стать еще хуже. Поэтому, если ограничение FinTime < BestTimeSoFar удовлетворить невозможно, то работа над текущим частично со­ставленным расписанием прекращается; в противном случае процессору назначается другое задание и т.д. После составления каждого полного расписания можно гаран­тировать, что время его завершения меньше по сравнению с наилучшим временем завершения, найденным до сих пор. Поэтому обновляется расписание, наилучшее к

Глава 14. Логическое программирование в ограничениях

данному моменту. Наконец, если характеристики, наилучшие к данному моменту, ' нельзя улучшить, поиск останавливается. Безусловно, этот алгоритм вырабатывает только одно из многих возможных наилучших расписаний.

Следует отметить, что этот процесс является комбинаторно сложным из-за экспо­ненциального количества возможных вариантов назначения процессоров заданиям. Но благодаря тому, что характеристики текущего частично составленного расписа­ния контролируются с помощью значения BestTimeSoFar, удается отказаться от це­лых групп некачественных расписаний еще до их полного составления. Количество времени вычисления, которое экономится благодаря этому, зависит от того, насколь­ко удачно выбрана эта верхняя граница. Если верхняя граница не оставляет воз­можностей для маневра, то некачественные расписания распознаются и отбрасыва­ются на ранних этапах их создания, что позволяет экономить много времени. Поэто­му, чем быстрее удается найти какой-то качественное расписание, тем скорее начинает применяться жестко заданная верхняя граница и тем большая часть про­странства поиска исключается из рассмотрения.

В листинге 14.2 содержится также спецификация задачи составления расписания (см. рис. 12.6), которая подготовлена в соответствии с принятыми соглашениями по оформлению условий задачи. Вопрос, с помощью которого может быть составлено расписание, соответствующее условиям этой задачи, приведен ниже. ?- schedule Schedule, FiiiTime] . FinTime = 24

Schedule = t tl/3/0/4,12/2/0/2,13/1/0/2, t4/3/4/20, t5/2/4/20, 16/1/2/11,17/1/13/11]

Задача 11 выполняется процессором З, начиная со времени О, задача t2 выполня­ется процессором 2, начиная со времени 0 и т.д. В этой задаче планирования пред­ставляет интерес еще один нюанс. Все три доступных процессора являются эквива­лентными, поэтому перестановка списков назначений процессоров заданиям не при­водит к каким-либо изменениям. Таким образом, нет смысла выполнять поиск по всем подобным перестановкам, так как они должны давать одинаковые результаты. Чтобы избежать таких бесполезных перестановок, можно, например, закрепить про­цессор 1 за заданием t7 и ограничить выбор процессора для задания t6 только про­цессорами 1 и 2. Такое решение можно легко реализовать, изменив предикат resource. Тем не менее, хотя в целом это — неплохая идея, как оказалось, ее нет смысла реализовывать в данном конкретном примере. Несмотря на то что при этом количество возможных вариантов назначения могло бы сократиться в б раз, эконо­мия времени является незначительной, что на первый взгляд кажется необъясни­мым, Но причина этого состоит в том, что после обнаружения оптимального распи­сания устанавливается жесткая верхняя граница выбора времени завершения, по­этому в дальнейшем отказ от других возможных назначений процессора происходит очень быстро.

Упражнения

14.4. Проведите эксперименты с программой, приведенной в листинге 14.1. Попро­буйте применить разные спецификации ресурсов, предназначенные для ис­ключения бесполезных перестановок, и проведите измерения продолжительно­сти времени выполнения программы. В чем состоят достигнутые улучшения?

14.5. В программе, приведенной в листинге 14.2, верхняя граница значений време­ни завершения (best sofa г) инициализируется большим числовым значением, которое намного превосходит все возможные значения времени завершения. Это позволяет гарантировать, что оптимальное расписание будет находиться в пределах установленной границы и будет обнаружено программой. Такой под­ход, хотя и безопасный, является неэффективным, поскольку подобная верх­няя граница, оставляющая большую свободу для маневра, не позволяет доста­точно качественно ограничивать поиск. Рассмотрите другие подходы к ини­циализации и корректировке верхней границы, например, при которых работа

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

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