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


           

Проект



Проект

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

line();

/* Отношения для задачи планирования.
Вершины пространства состояний - частичные планы,
записываемые как

[ Задача1/Т1, Задача2/Т2, ...]*
        [ Задача1/К1, Задача2/К2, ...]* ВремяОкончания

В первом списке указываются ждущие задачи и продолжительности их выполнения; во втором - текущие решаемые задачи и их времена окончания, упорядоченные так, чтобы выполнялись неравенства K1<=K2, K2<=K3, ... . Время окончания плана - самое последнее по времени время окончания задачи.
*/

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

                                                            % Взять ждущую задачу
                not( принадлежит( Здч1/_, Задачи2),
                        раньше( ЗДЧ, Задача) ),

                                                           % Проверить предшествование
                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 ).

line();



Содержание  Назад  Вперед






Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий