Иван Братко - Программирование на языке Пролог для искусственного интеллекта Страница 62

/* Отношения для задачи планирования.

Вершины пространства состояний - частичные планы,

записываемые как

 [ Задача1/Т1, Задача2/Т2, ...]*

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

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

Время окончания плана - самое последнее по времени время окончания задачи.

*/

после( Задачи1*[ _ /К | Акт1]*Кон1,

 Задачи2*Акт2*Кон2, Ст):-

 удалить( Задача/T, Задачи1, Задачи2),

  % Взять ждущую задачу

 not( принадлежит( Здч1/_, Задачи2),

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

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

 not( принадлежит( Здч1/К1, Акт1), К1<К2,

 раньше( К1, Задача) ),    % Активные задачи

 Время is К + T,

  % Время окончания работающей задачи

 встав( ЗадачаВремя, Акт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( Задачи * Процессоры * Кон, 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) впервые изложен поиск с предпочтением, управляемый оценкой расстояния до цели.

Головоломка "игра в восемь" использовалась многими исследователями в области искусственного интеллекта в качестве тестовой задачи при изучении эвристических принципов (см., например, Doran and Michie (1966), Michie and Ross (1970) и Gaschnig (1979)).

Задача планирования, рассмотренная в настоящей главе, также как и многие ее разновидности, возникает во многих прикладных областях в ситуации, когда необходимо спланировать обслуживание запросов на ресурсы. Один из примеров — операционные системы вычислительных машин. Задача планирования со ссылкой на это конкретное приложение изложена в книге Coffman and Denning (1973).

Найти хорошую эвристику — дело важное и трудное, поэтому изучение эвристик — одна из центральных тем в искусственном интеллекте. Существуют, однако, некоторые границы, за которые невозможно выйти, двигаясь в направлении улучшения качества эвристик. Казалось бы, все, что необходимо для эффективного решения комбинаторной задачи — это найти мощную эвристику. Однако есть задачи (в том числе многие задачи планирования), для которых не существует универсальной эвристики, обеспечивающей во всех случаях как эффективность, так и допустимость. Многие теоретические результаты, имеющие отношение к этому ограничению, собраны в работе Garey and Johnson (1979).

Coffman E.G. and Denning P.J. (1973). Operating Systems Theory. Prentice-Hall.

Doran J. and Michie D. (1966). Experiments with the graph traverser program. Proc. Royal Socieiy of London 294(A): 235-259.

Garey M. R. and Johnson D. S. (1979). Computers and Intractability. W. H. Freeman. [Имеется перевод: Гэри M., Джонсон Д. С- Вычислительные машины и труднорешаемые задачи. — M.: Мир, 1982.]

Gaschnig J. (1979). Performance measurement and analysis of certain search algorithms. Carnegie-Mellon University: Computer Science Department-Technical Report CMU-CS-79-124 (Ph. D. Thesis).

Hart P.E., Nilsson N.J. and Raphael B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Sciences and Cybernetics SSC-4(2):100-107

Michie D. and Ross R. (1970). Experiments with the adaptive graph traverser. Machine Intelligence 5: 301–308.

Nilsson N.J. (1971). Problem — Solving Methods in Artificial Intelligence. McGraw-Hill. [Имеется перевод: Нильсон H. Искусственный интеллект. Методы поиска решений. — M: Мир, 1973.]

Nilsson N. J. (1980). Principles of Artificial Intelligence. Tioga; also Springer-Verlag.

Pearl J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.

Winston P. H. (1984). Artificial Intelligence (second edition). Addison-Wesley. [Имеется перевод первого издания: Уинстон П. Искусственный интеллект. — M.: Мир, 1980.]

Глава 13

Сведение задач к подзадачам. И/ИЛИ-Графы

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