Prolog

Неизвестно

% КонВремя - сумма времен окончания

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

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

Резюме

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

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

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

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

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

Литература

Программа поиска с предпочтением, представленная в настоящей главе, - это один из многих вариантов похожих друг на друга программ, из которых А*-алгоритм наиболее популярен. Общее описание А*-алгоритма можно найти в книгах 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.]