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

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

Проект

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

Резюме

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

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

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

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

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

Литература

Программа поиска с предпочтением, представленная в настоящей главе, — это один из многих вариантов похожих друг на друга программ, из которых А*-алгоритм наиболее популярен. Общее описание А*-алгоритма можно найти в книгах Nillson (1971, 1980) или Winston (1984). Теорема о допустимости впервые доказана авторами статьи Hart, Nilsson, and Raphael (1968). Превосходное и строгое изложение многих разновидностей алгоритмов поиска с предпочтением и связанных с ними математических результатов дано в книге Pearl (1984). В статье Doran and Michie (1966) впервые изложен поиск с предпочтением, управляемый оценкой расстояния до цели.