Prolog

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

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

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

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

Резюме

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

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

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

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

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

Литература