раньше( Здч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: граф предшествования и исходный (пустой) план в

качестве стартовой вершины.

Резюме

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

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