Иван Братко - Программирование на языке Пролог для искусственного интеллекта
/* Отношения для задачи планирования.
Вершины пространства состояний - частичные планы,
записываемые как
[ Задача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
Сведение задач к подзадачам. И/ИЛИ-Графы
Представление в виде И/ИЛИ-графов наиболее хорошо приспособлено для задач, которые естественным образом разбиваются на взаимно независимые подзадачи. Примерами таких задач могут служить поиск маршрута, символическое интегрирование, а также игровые задачи, доказательство теорем и т.п. В этой главе мы разработаем программы для поиска в И/ИЛИ-графах, в том числе программу поиска с предпочтением, управляемого эвристиками.
