Программирование на языке Пролог для искусственного интеллекта

Братко Иван

Время окончания плана - самое последнее по времени время окончания задачи.

*/

после( Задачи1*[ _ /К | Акт1]*Кон1,

 Задачи2*Акт2*Кон2, Ст):-

 удалить( Задача/T, Задачи1, Задачи2),

% Взять ждущую задачу

 not( принадлежит( Здч1/_, Задачи2),

 раньше( ЗДЧ, Задача) ),

% Проверить предшествование

 not(

принадлежит( Здч1/К1, Акт1), К1<К2,

 раньше( К1, Задача) ), % Активные задачи

 Время is К + T,

% Время окончания работающей задачи

 встав( ЗадачаВремя, Акт1, Акт2, Кон1, Кон2),

 Ст is Кон2 - Кон1.

после( Задачи*[ _ /К | Акт1]*Кон, Задачи2*Акт2*Кон, 0):-

 вставпростой( К, Акт1, Акт2).

% Оставить процессор бездействующим

раньше( Задача1, Задача2) :-

% В соответствии с предшествованием

 предш( Задача1, Задача2).

% Задача1 раньше, чем Задача2

раньше( Здч1, Здч2) :-

 предш( Здч, Здч2),

 раньше( Здч1, Здч).

встав( Здч/А, [Здч1/В | Спис], [Здч/А, Здч1/В | Спис], К, К):-

% Список задач упорядочен

 А =< В, !.

встав( Здч/А, [Здч1/В | Спнс], [Здч1/В | Спис1], К1, К2) :-

 встав( Здч/А, Спис, Спис1, Kl, К2).

встав( Здч/А, [ ], [Здч/А], _, А).

вставпростой( А, [Здч/В | Спис], [простой/В, Здч/В | Спис]):-

% Оставить процессор бездействующим

 А < В, !. % До ближайшего времени окончания

вставпростой( А, [Здч/В | Спис], [Здч/В | Спис1]) :-

 вставпростой( А, Спис, Спис1 ).

удалить( А, [А | Спис], Спис ).

% Удалить элемент из списка

удалить( А, [В | Спис], [В | Спис1] ):-

 удалить( А, Спис, Спис1 ).

цель( [] *_*_ ). % Целевое состояние: нет ждущих задач

% Эвристическая оценка частичного плана основана на

% оптимистической оценке последнего времени окончания

% этого частичного плана,

% дополненного всеми остальными ждущими задачами.

h(

Задачи * Процессоры * Кон, H) :-

 сумвремя( Задачи, СумВремя),

% Суммарная продолжительность

% ждущих задач

 всепроц( Процессоры, КонВремя, N),

% КонВремя - сумма времен окончания

% для процессоров, N - их количество

 ОбщКон is ( СумВремя + КонВремя)/N,

 ( ОбщКон > Кон, !, H is ОбщКон - Кон; H = 0).

сумвремя( [], 0).

сумвремя( [ _ /T | Задачи], Вр) :-

 сумвремя( Задачи, Вр1),

 Вр is Bp1 + T.

всепроц( [], 0, 0).

всепроц( [ _ /T | СписПроц], КонВр, N) :-

 всепроц( СписПроц, КонВр1, N1),

 N is N1 + 1,

 КонВр is КонВр1 + T.

% Граф предшествования задач

 предш( t1, t4). предш( t1, t5). предш( t2, t4).

 предш( t2, t5). предш( t3, t5). предш( t3, t6).

 предш( t3, t7).

% Стартовая вершина

старт( [t1/4, t2/2, t3/2, t4/20, t5/20, t6/11, t7/11] *

 [простой/0, простой/0, простой/0] * 0 ).

Рис. 12.9. Отношения для задачи планирования. Даны также определения отношений для конкретной задачи планирования с рис. 12.8: граф предшествования и исходный (пустой) план в качестве стартовой вершины.

Проект

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

Резюме

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

• Эвристический принцип поиска с предпочтением направляет процесс поиска таким образом, что для продолжения поиска всегда выбирается вершина, наиболее перспективная с точки зрения эвристической оценки.

• В этой главе был запрограммирован алгоритм поиска, основанный на указанном принципе и известный в литературе как А*-алгоритм.

• Для того, чтобы решить конкретную задачу при помощи А*-алгоритма, необходимо определить пространство состояний и эвристическую функцию. Для сложных задач наиболее трудным моментом является подбор хорошей эвристической функции.