раньше( ЗДЧ, Задача) ),
% Проверить предшествование
not( принадлежит( Здч1/К1, Акт1), К1<К2,
раньше( К1, Задача) ), % Активные задачи
Время is К + Т,
% Время окончания работающей задачи
встав( ЗадачаВремя, Акт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( Задачи * Процессоры * Кон, Н) :-
сумвремя( Задачи, СумВремя),
% Суммарная продолжительность
% ждущих задач
всепроц( Процессоры, КонВремя, N),
% КонВремя - сумма времен окончания
% для процессоров, N - их количество
ОбщКон is ( СумВремя + КонВремя)/N,
( ОбщКон > Кон, !, H is ОбщКон - Кон; Н = 0).
сумвремя( [ ], 0).
сумвремя( [ _ /Т | Задачи], Вр) :-
сумвремя( Задачи, Вр1),
Вр is Bp1 + Т.
всепроц( [ ], 0, 0).
всепроц( [ _ /T | СписПроц], КонВр, N) :-
всепроц( СписПроц, КонВр1, N1),
N is N1 + 1,
КонВр is КонВр1 + Т.
% Граф предшествования задач
предш( 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: граф предшествования и исходный (пустой) план в
качестве стартовой вершины.
Резюме
Для оценки степени удаленности некоторой вершины пространства состояний от ближайшей целевой вершины можно использовать эвристическую информацию. В этой главе были рассмотрены численные эвристические оценки.
Эвристический принцип поиска с предпочтением направляет процесс поиска таким образом, что для продолжения поиска всегда выбирается вершина, наиболее перспективная с точки зрения эвристической оценки.
В этой главе был запрограммирован алгоритм поиска, основанный на указанном принципе и известный в литературе как А*-алгоритм.
Для того, чтобы решить конкретную задачу при помощи А*-алгоритма, необходимо определить пространство состояний и эвристическую функцию. Для сложных задач наиболее трудным моментом является подбор хорошей эвристической функции.
Литература
