Листинг 12.1. Программа поиска по заданному критерию

I bestfiratt Start, Solution):

Ч Решение Solution. - зто путь от узла Start до целевого узла

bestfirst) Start, Solution):-

expand([], 1(Start, 3/0), SS99, _, yes, Solution).

Ь Предполагается, что любое f-значение не превышает 9999

% expand! Path_r Tree, Bound, Treel, Solved, Solution):

Глава 12. Эвристический поиск но заданному критерию

Path — это путь между начальным узлом поиска и поддеревом. Tree 1 — дерево

Tree, развернутое в пределах Bound; если цель найдена, то Solution — путь. решения и Solved = yes

к Случай 1. Y.fiT.v.

лист-узел, сформировать путь поиска yes, [HIP]):-

 

expand (р, 1 (S, _), goal(Hi.

\ Случай 2. Лист-узел; f-значение меньше чем Bound. Сформировать
\ узлы-преемники к развернуть ше в пределах 3ound

expand! P, 1(N,F/G), Bound, Treel, Solved, Sol):-F -< Bound, (bagoft М/С, [s(N,M,C}, not member (M, P)), Succ),

!, % Узел Ы имеет преемников

succlist(G, Succ, Ts), % Создать поддеревья Ts

bestf{ Ts, Fit, % f-значение лучшего преемника

expand! P, t(N,Fl/G,Ts), Bound, Treel, Solved, Sol)

)

Solved

% Узел не имеет преемников — тупиковый конец*

Случай 3. Не лис-.-у-ол; f-значение меньше чем Bound. Развернуть наиболее перспективное поддерево; в зависимости от результатов процедура continue примет решение в отношении дальнейших действий

expand! P, t(N, F/G, [T[Ts]), Bound, Treel, Solved, Sol):-F =< Bound,

bestf (Ts, BF!, mint Bound, BF, Boundl), %. Boundl - min (Bound, BF] expandt [H|F], T, Boundl, Tl, Solvedl, Sol), continue(P, t(N,F/G, [Tl|Ts]), Bound, Treel, Solvedl, Solved, Sol).

....-; 4... ■.•■-..;...'.: с пустыми поддеревьями. Это Б котором не может Быть найдено решение

тупиковое направление,

expand; _, t(_,_, []), _, _, never, _):-!.

I Случай 5. Получено f-значение больше чем Bound. Дерево больше не может расти'

expand С _, Tree, Bound, Tree, no, _):-ft Tree, F), F > Bound.

«continue; Path, Tree, Bound, HewTree, SubtreeSolved, TreeSolved, Solution)

continue; _, _, _, _, yes, yes, Sol).

continue; P, t(N,F/G,[Tl|Ts]), Bound, Treel, no, Solved, Sol):-insert; Tl, Ts, NTs), bestf; NTs, Fl), expand! P, t[N,Fl/G,NTS), Bound, Treel, Solved, Sol).

continue! P, t(N,F/G,1_ITs]), Bound, Treel, never, Solved, Sol):-bestf; Ts, Fl), expand!' P, t (Ы, Fl/G, Ts), Bound, Treel, Solved, Sol).

% succlist(GO, [ Nodel/Costl,...],! 1(BestHode,BestF/G),...)!: 't упорядочить список листьев поиска по их F-значенинм

succlist(

[], []) -

 

succlistС GO, [Ы/С i NCs], Ts) G is GO + C,

: -

252 Часть II. Применение языка Prolog в области искусственного интеллекта

ht Я, н), % Эвристический терм h(N)

F is G + H,

succlist(GO, NCs, Tsl),

insert! 1{H,F/G), Tsl, Ts i.

% Вставить дерево Т Е СПИСОК деревьев Ts с сохранением упорядоченности; по отношению к f-значениям

insert; T, Ts, [Т | Ts]):-f(Т, F), bestf! Ts, Fl),

F =< Fl,!.

insert; T, [Tl | Ts], [Ti | Tsl]):-

insert (T, Ts, Tsl).

% Извлечь f-значение

f(1 (_, f/_;, F). % f-значение jthcts

f(t(_/F/_,J, F). % f-значение дерева

bestf([Т|_], F):- % Лучшее f-значение в списке деревьев

ЦТ, F}.
bestfl [], 9999). % Деревья отсутствуют: неприемлемое f-значение

mini X, Y, X):-X =< Y,!.

mint X, Y, Y).

Параметры Р, Tree и Bound являются "входными" по отношению к процедуре expand; это означает, что при каждом вызове процедуры expand они уже конкрети­зированы. Процедура expand вырабатывает результаты трех типов, которые разли­чаются по значению параметра Solved, как описано ниже.

1. Solved = yes.

Solution — путь решения, найденный в результате развертывания дерева Tree в пределах Bound.

Переменная Treel является неконкретизированной.

2. Solved = no.

Treel - дерево Tree, развернутое так, что его f-значение превысило Bound

(рис. 12,3).

Переменная Solution является неконкретизированной.

3. Solved = never.

Переменные Treel и Solution являются неконкретизированными.

Последний случай показывает, что дерево Tree - это бесперспективный (тупико­вый) вариант и программе больше не следует предоставлять другого шанса на по­вторную активизацию его исследования. Такая ситуация возникает, если f-значение дерева Tree меньше или равно Bound, но дерево не может расти, поскольку в нем ни один узел больше не имеет преемника (т.е. является листом) или имеет преемника, но такого, который создает цикл.

Некоторые предложения, касающиеся отношения expand, заслуживают дополни­тельного описания. В частности, предложение, которое относится к наиболее слож­ному случаю, когда Tree имеет поддеревья, т.е. предложение Tree = t(к, F/G, [T | Ts)!

Глава 12. Эвристический поиск по заданному критерию

а, возможно, некоторое более низкое значение, в зависимости от f-значений других конкурирующих поддеревьев, Ts. Это позволяет гарантировать, что поддерево, рас­тущее в настоящее время, всегда является наиболее перспективным. Затем процесс развертывания переключается с одного поддерева на другие в соответствии с их f-эначениями. После развертывания наилучшего поддерева из всех возможных вспо­могательная процедура continue вырабатывает решение в отношении дальнейших действий; это решение зависит от типа результата, полученного на данном этапе раз­вертывания. Если найдено решение, оно возвращается, в противном случае развер­тывание продолжается. Б предложении, которое касается данной ситуации, Tree = 1С N, F/G!

вырабатываются узлы-преемники уала N наряду со значениями стоимостей дуг меж­ду N и узлами-преемниками. Процедура succlist создает список поддеревьев, исхо­дящих из данных узлов-преемников, вычисляя также их g- и f-значения (рис. 12.4), Затем результирующее дерево продолжает развертываться до тех пор, пока позволяет предел Bound. Если, с другой стороны, преемников не было, то происходит отказ от какого-либо дальнейшего использования данного листа путем конкретизации значе­ния Solved = 'never'.

начальный узел

Тгео1

Г-значекие> Bound

Рис. 12.3. Отношение expand развертывание дерева Tree до тех пор, пока {-значение не превысит Bound, приводит к созданию дерева Tree 1

Другие отношения описаны ниже.

5< Н, М_г С)

где м — узел-преемник узла К в пространстве состояний, С — стоимость дуги от N до Н.

И N, н,

где Н — эвристическая оценка стоимости наилучшего пути от узла N до целевого узла.

Часть II. Применение языка Prolog в области искусственного интеллекта

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

 

g(M) = g(N)H С

Рис: 12.4. Зависимости между g значе­нием узла ы. а также f- и щ-зчаченияни его дочерних узлов в пространстве со стояний

Алгоритм поиска называется допустимым, если он всегда вырабатывает опти­мальное решение (т.е. путь с минимальной стоимостью), при условии, что решение вообще существует. Рассматриваемая здесь реализация, в которой все решения вы­рабатываются с помощью перебора с возвратами, может считаться допустимой, ес­ли оптимальным является первое же из найденных решений. Предположим, что для каждого узла а в пространстве состояний как h* in) обозначена стоимость оп­тимального пути от г. до целевого узла. В теореме, касающейся допустимости алго­ритма А*, утверждается следующее: допустимым является любой алгоритм А*, в котором используется эвристическая функция h, такая, что для всех узлов п в про­странстве состояний справедливо следующее утверждение:

ь(п) < h* (л)

Этот результат имеет большое практическое значение. Даже если неизвестно точ­ное значение h*, достаточно найти нижнюю границу h* и использовать ее в качестве h в алгоритме А*. Это служит достаточной гарантией того, что алгоритм Л* вырабо­тает оптимальное решение. В частности, может рассматриваться тривиальная ниж­няя граница, а именно:

ыы - О

для всех п в пространстве состояний.

Такой вариант действительно гарантирует допустимость. Но недостаток использо­вания условия г. --■- С состоит в том, что оно но имеет эвристического потенциала и не обеспечивает какого-либо управления процессом поиска. Алгоритм А*, в котором используется h = 0, ведет себя аналогично алгоритму поиска в ширину. Мало того, он фактически сводит поиск в ширину к такому случаю, что функция стоимости дуг принимает значение.;п, п') - 1 для всех дуг (п,п') в пространстве состояний. Такое отсутствие эвристического потенциала приводит к значительному увеличению потребности в ресурсах. Поэтому желательно иметь такое значение h, которое явля­ется нижним пределом h ■ (для обеспечения допустимости), а также в максимально возможной степени приближается к h* (для обеспечения эффективности). В идеале,

Глава 12. Эвристический поиск по заданному критерию

если была бы известна стоимость h*, то в алгоритме можно было бы использовать само значение h*» поскольку алгоритм А*, в котором используется значение h*, на­ходит оптимальное решение непосредственно, вообще без какого-либо перебора с воз­вратами.

Упражнения

12.1. Определите отношения s, goal и h для задачи поиска маршрута, показанной! на рис. 12.2, с учетом особенностей рассматриваемой проблемы. Изучите пове­дение приведенной в данной главе программы А* при решении этой задачи.

12.2. Следующее утверждение на первый взгляд напоминает теорему допустимости:! "Для любой задачи поиска, если А* находит оптимальное решение, то Hi [п.) < h* (п) для всех узлов п в пространстве состояний". Является ли это утвержде- 1 ние правильным?

12.3. Предположим, что h_u h₂ и hj - три допустимые эвристические функции (h_:. £ h*), которые поочередно применяются алгоритмом А* в одном и том же про-1 странстве состояний. Объедините эти три функции еще в одну эвристическую! функцию, h, которая также допустима и направляет поиск не хуже любой из! трех функций hi, отдельно взятых.

12.4. Подвижный робот перемещается на плоскости х-у между препятствиями. Все! препятствия представляют собой прямоугольники, выровненные вдоль осей у| и х. Робот может перемещаться только в направлениях з? и у и имеет такие] небольшие размеры, что может быть приближенно представлен в виде точки. Робот должен планировать пути перемещения без столкновений с препятст­виями от его текущей позиции до некоторой указанной целевой позиции. Ро-. бот стремится свести к минимуму длину пути и количество изменений на­правления движения (допустим, что стоимость одной смены направления рав­на стоимости перемещения на одну единицу длины). В роботе для поиска оптимальных путей используется алгоритм А*. Определите предикаты. s(state, NewState, Cost) и hi State, 11) для использования в програм­l ме А* в процессе решения этой задачи поиска (желательно, чтобы эти преди-' каты были допустимыми). Предположим, что целевая позиция для робота опре- ­деляется с помощью предиката goal {Xg/Yg), где Xg и Yg — координаты х и у!' целевой точки. Препятствия представлены с помощью следующего предиката:

obstacle(Xmin/Ymin, Xmax/Ymax}

где xmin/Ymin — нижний левый угол препятствия, a Xmax/Ymax — его верх­ний правый угол.

12.2. Применение поиска по заданному критерию для решения головоломки "игра в восемь"

Чтобы можно было применить программу поиска по заданному критерию, приве­денную в листинге 12.1, для решения некоторой конкретной задачи, необходимо оп­ределить отношения, характеризующие рассматриваемую проблему. Эти отношения характеризуют конкретную проблему ("правила игры"), а также воплощают в себе эвристическую информацию о том, как решить данную задачу. Такая эвристическая информация предоставляется в форме эвристической функции.

Предикаты, касающиеся конкретной проблемы, задаются в виде следующего от­ношения: s(Node, Model, Cost)

Часть II. Применение языка Prolog в области искусственного интеллекта

Это отношение является истинным, если в пространстве состояний между узлами Node и Nodel имеется дуга со стоимостью Cost. Отношение goal(Mode)

является истинным, если Node — целевой узел в пространстве состояний. А в отно­шении

h[ Node, H)

переменная Н — эвристическая оценка стоимости пути с минимальной стоимостью от узла Node до целевого узла.

В этом и следующем разделах такие отношения будут определены для двух при­меров проблемных областей: головоломка "игра в восемь" (описанная в разделе 11.1) и задача составления расписаний.

Отношения, касающиеся проблемной области для головоломки "игра в восемь", приведены в листинге 12.2. Любой из узлов в пространстве состояний представляет собой некоторую конфигурацию фишек в коробке. В данной программе эта конфигу­рация представлена в виде списка текущих положений фишек. Каждая позиция обо­значается парой координат, X/Y. Порядок элементов в списке является следующим.

1. Текущая позиция пустого квадрата.

2. Текущая позиция фишки 1.

3. Текущая позиция фишки 2.

4....

Целевая ситуация (см. рис. 11.3), в которой все фишки находятся на своих ис­ходных клетках, определяется следующим предложением:

goal! [2/2,1/3,2/3,3/3,3/2,3/1,2/1,1/1,1/2]).

Листинг 12.2. Относящиеся к проблемной области процедуры для головоломки "игра в восемь", которые должны использоваться в программе поиска по заданному критерию, приведенной в листинге 12.1

{* Относящиеся к проблемной области процедуры для головоломки "игра в восемь"

Текущая позиция представлена списком координат фишек, в котором на первом месте указаны координаты пустой клетки

Пример

		:■:	13
			[

Для представления этой позиции служит следующий список: [J2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2]

12 3

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

% s t Mode, SuccessorNode, Cost)

S([Empty I Tiles], [Tile ] Tilesl], 1):- % Стоимости всех дуг равны 1 swap* Empty, Tile, Tiles, Tilesl). % Поменять местами пустую фишку

% Empty и фишку Tile в списке Tiles

swap С Empty, Tile, [Tile [ Ts], [Empty | Ts]):-
mandist{ Empty, Tile, 1). % Манхэтгенское расстояние равно 1

Глава 12. Эвристический поиск по заданному критерию

-

% D - это манхэттенское расстояние % между двумя клетками

I D равно |А-В|

snap! Empty, Tile, [Tl I Ts], [Tl I Tsl] Swap! Empty, Tile, Ts, Tsl).

: -

mandistC X/Y, Xl/Yl, D)

dif (X, XI, Dx),

dif < Ч, Yl, Dy),

D is Dx + Dy.

dif(й, Б, D):-D is A-B, D >= 0,!

 

D is В-А.

% Эвристическая оценка h представляет собой сумму расстояний от каждой фишки 4 до ее "исходной" клетки плис утроенное значение "оценки упорядоченности"

hi [Empty I Tiles], H]:-

goal{ [Emptyl I GoalSquares]), totdist{ Tiles, GoalSquares, D), seq(Tiles, S), H is D + 3*S,

Суммарное расстояние от исходных клеток i Оценка упорядоченности

 

totdist([], [], 0).

totdistt [Tile I Tiles], [Square ] Squares], D) mandist! Tile, Square, Dl), totdistt Tiles, Squares, D2), D is Dl + D2.

-

% seq(TilePositions, Score): оценка упорядоченности

seq([First I OtherTiles], s):-

seq([First I OtherTiles ], First, 3).

seq([Tilel, Tile2 I Tiles], First, S):-score(Tilel, Tile2, El), seq([Tile2 t Tiles), First, £2), S is SI + $ 2.

seq([Last], First, S}:-score(Last, First, SJ.

1.

score) 2/2, _, 1)

score! 1/3, 2/3, 0!

score! 2/3, 3/3, 0)

score! 3/3, 3/2, 0)

score! 3/2, 3/1, 0)

score! 3/1, 2/1, Q)

score! 2/1, 1/1, 0)
score(1/1,1/2,0)

scoreC 1/2, 1/3, G)

: -

 

: -	!.
: -	!.
: -	!.
: -	[,
: -	!.
: -	!.
: -	!.

% Оценка фишки, стоящей в центре, равна 1

% Оценка фишки, за которой следует % допустимый преемник, равна 0

score! _, _, 2). Ч Оценка фишкк, за которой следует

% недопустимый преемник, равна 2 goal С [2/2,1/3,2/3,3/3,3/2,3/1,2/1,1/1,1/2]). % Исходные клетки для фишек

Ч Показать путь решения как список позиций на доске

showsolC []).

showsol([P I L] showsol(L),

)

-

258 Часть II. Применение языка Prolog в области искусственного интеллекта

al, _writ_e('------- '),

showpost P]. i Показать позицию на доске

Showposf [S0,S1,S2,S3,S4,S5,S6,S7,S8]):-

member; Y, [3,2,1) >, % Последовательность координат Y

nl, member[ X, [1,2,3)), % Последовательность коордкнат х

member! Tile-X/Y, % Фишка в клетке XY

[■ '-S0,1-S1,2-S2,3-S3,4-S4,5-S5,6-S6,7-S7,8-S8] (, write! Tile),

fail I Выполнить перебор с возвратом к следующей клетке

true, % Обработка всех клеток закончена

* Начальные позиции для некоторых задач

stactll [2/2,1/3,3/2,2/3,3/3,3/1,2/1,1/1,1/2]). I Требует 4 хода

start2(£2/1,1/2,1/3,3/3,3/2,3/1,2/2,1/1,2/3]). % Требует 5 ходов

Start3([2/2,2/3,1/3,3/1,1/2,2/1,3/3,1/1,3/2]). % Требует 19 кодов

% Пример^запроса:?- вТГгТГPos), beetHHt[ Pos, Sol), rtowsel t'Sol)..............................

При определении этих отношений применяется следующее вспомогательное от­ношение:

mandist(SI, 52, D).

где D — манхэттенскоерасстояние между клетками S1 и S2; оно измеряется как сумма расстояний между S1 и S2 в горизонтальном и вертикальном направлениях.

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

	л	Л
	и

 

	а

 

		У.

a) fi] в)

Рис, 12,5. Три начальные позиции для голово­ломки "игра е восемь": а) требует. 4 хода; б) требует. 5 ходов; в) требует 18 ходов

Эвристическая функция h определяется в программе следующим образом: hi Роз, К) где Pos — позиция на доске, Н — сочетание двух описанных ниже критериев,

1. totdist. Суммарное расстояние восьми фишек в позиции Роз от тех клеток, называемых исходными, в которых должны находиться фишки после решения головоломки. Например, в начальной позиции головоломки, приведенной на рис. 12.5, о, totdist = 4.

2. seq. Оценка упорядоченности, определяющая ту степень, в какой фишки, стоящие в текущей позиции, уже упорядочены по отношению к той последова­тельности, которая должна быть достигнута в целевой конфигурации. Значе-

Глэва 12. Эвристический поиск по заданному критерию 259

ние seq вычисляется как сумма оценок для каждой фишки в соответствии со следующими правилами:

• фишка в центре имеет оценку 1;

• фишка, стоящая на нецентральной клетке, имеет оценку О, если за ней в направлении по часовой стрелке следует соответствующий ей преемник (например, если за фишкой 1 следует фишка 2);

• такая фишка имеет оценку 2, если за ней не следует соответствующий ей преемник.

Например, для начальной позиции головоломки, приведенной на рис. 12.5, а, seq = 6.

Эвристическая оценка, Н, вычисляется как К = totdist + 3 * seq.

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

h=4 + 3*6-22, Ъ* = 4

С другой стороны, допустимым является отдельно взятый критерий "суммарного расстояния", поскольку для всех позиций имеет место следующее:

totdist <_ h*

Допустимость этого отношения можно легко проверить с помощью таких рассуж­дений: если условия этой головоломки будут упрощены таким образом, что фишки можно будет переносить друг над другом, то каждая фишка сможет переходить к своей исходной клетке по траектории, длина которой точно равна манхэттенскому расстоянию между начальной клеткой фишки и ее исходной клеткой. Поэтому опти­мальное решение в упрощенной головоломке будет точно равно длине totdist. Но в первоначальном варианте задачи фишки могут мешать друг другу и одна из них мо­жет находиться на пути другой, что препятствует движению фишек по кратчайшим траекториям, а это гарантирует, что длина оптимального решения равна или больше чем totdj sj-.

Упражнение

12.5. Модифицируйте программу поиска по заданному критерию, приведенную в листинге 12.1, таким образом, чтобы в ней подсчитывал ось количество узлов, выработанных в процессе поиска. Один из простых способов состоит в том, чтобы текущее значение количества узлов вносилось в базу данных как факт и обновлялось с помощью предикатов retract и assert после каждой выработ­ки новых узлов. Проведите эксперименты с различными эвристическими функциями для головоломки "игра в восемь" для оценки их эвристического потенциала, который характеризуется количеством выработанных узлов.

260 Часть II. Применение языка Prolog в области искусственного интеллекта

Применение поиска по заданному критерию при планировании

Рассмотрим следующую проблему планирования заданий. Предположим, что дано множество заданий, tj, tj,..., и соответствующих им значений продолжительности выполнения, Dj, D;,.... Задания предназначены для выполнения множеством иден­тичных процессоров тт.. Любое задание может быть выполнено любым процессором, ко каждый процессор способен одновременно выполнять только одно задание. Между заданиями определено отношение предшествования, которое указывает, какие зада­ния, если они имеются, должны быть завершены, прежде чем можно будет начать выполнение какого-то другого задания. Проблема планирования состоит в распреде­лении заданий по процессорам таким образом, чтобы не нарушалось отношение предшествования и все задания в целом были обработаны за кратчайшее возможное время. Время окончания последнего задания в расписании называется временем за­вершения расписания. Среди всех возможных расписаний необходимо найти такое, при котором время завершения становится минимальным.

На рис. 12.6 показана такая задача планирования заданий и приведены два до­пустимых расписания, одно из которых является оптимальным. Этот пример демон­стрирует интересное свойство оптимальных расписаний, которое состоит в том, что они могут включать время простоя для процессоров. В оптимальном расписании, приведенном на рис, 12.6, процессор 2 после выполнения задания -„,■ ожидает в тече­ние двух единиц времени, хотя он мог бы сразу же начать выполнение задания t-?.

/7/П

 

Время

 

s	4 13	24 33
fJ	h	и
ч	ч
h	и	'■ШШ

а

о

 

,	! 1	\
и	h
^	it Про-j	Г;	■ ■ ■■
h	и	Щ ■■:.: ■ i

Рис. 12.6. Задача планирования заданий, в условия которой входят сечь заданий и три процессора, В верхней части, этого рисунка показаны отношение предшество­вания заданий и продолжительность заданий. Например, для задания £, требуется 20 единиц времени и его выполнение может качаться только после завершения трех других заданий, t_L. t₂ и £з. Показаны два допустимых расписания: оптималь­ное, с временем завершения 24, и неоптимальное, с временем завершения 33. При решении данной- задачи любое оптимальное расписание должно включать время про­стоя (см, [34], с. 86), Этот рисунок адаптирован и включен е настоящую книгу с разрешения издательства Prentice Hall, Englewood Cliffs, New Jersey

Глава 12. Эвристический поиск по заданному критерию

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

• состояния представляют собой частично составленные расписания;

• состояние-преемник некоторого частично составленного расписания можно по­лучить, введя в это расписание еще не запланированное задание; еще одна возможность состоит в том, что процессор, который выполнил свое текущее задание, может быть оставлен в состоянии простоя;

• начальным состоянием является пустое расписание;

• целевым состоянием является любое расписание, которое включает все зада­ния, рассматриваемые в данной задаче;

• стоимость решения (которая должна быть минимизирована) представляет со­бой время завершения целевого расписания;

• согласно этим условиям, стоимость перехода между двумя (частично состав­ленными) расписаниями, время завершения которых соответственно равно Fi и Ег, представляет собой разность Г₂ - W\.

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

Теперь необходимо выбрать способ представления проблемных ситуаций, т.е. час­тично составленных расписаний. Для решения задачи составления расписания тре­буется следующая информация.

1. Список ожидающих заданий и значений времени их выполнения.

2. Текущие назначения процессоров.

Кроме того, для удобства можно также учитывать следующую информацию.

3. Время завершения (частично составленного) расписания, другими словами, по­
следнее значение времени окончания обработки работы процессорами текущих
назначений.

Список ожидающих заданий и значений времени их выполнения будет представ­лен в программе в виде списка в следующей форме:

[ Taskl/Dl, Task2/D2,... ]

Текущие назначения процессоров представляются в виде списка заданий, обраба­тываемых в настоящее время; это означает, что должны использоваться пары с опре­делением заданий и времени их завершения в следующей форме:

Task/FinishingTime

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

262 Часть II. Применение языка Prolog в области искусственного интеллекта

ется в отсортированном виде в соответствии с возрастающими значениями времени завершения. Три компонента частично составленного расписания (ожидающие зада­ния, текущие назначения и время завершения) объединяются в программе в одно выражение: WaitingList * ActiveTasks * FinisbingTime

Кроме этой информации, имеется ограничение предшествования, которое задано в программе в виде отношения: prec(TaskX, TaskY)

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

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

1. Удалено ограничение предшествования.

2. Принято (нереальное) допущение, что задание может выполняться в режиме распределения по нескольким процессорам и что сумма значений времени вы­полнения этого задания всеми соответствующими процессорами равна первона­чально заданному времени выполнения данного задания на одном процессоре.

Предположим, что значения времени выполнения ожидающих в настоящее время заданий равны Di, Dv,..., а значения времени завершения текущих назначений про­цессоров равны Fi, F»... Такая оптимистическая оценка времени завершения, Finall, позволяющего выполнить все активные в настоящее время и все ожидающие задания, определяется по следующей формуле:

Finall = У t!i £лЩ)/т
i J

где m — количество процессоров. Предположим, что время завершения текущего час­тично составленного расписания определяется выражением: Fin = так (F-)]

В таком случае эвристическая оценка К (дополнительное время, требуемое для дополнения частично составленного расписания ожидающими заданиями) может быть определена следующим образом: если Finall > Fin, тс Н - Finall - Fin, иначе н = О

Полная программа, в которой в соответствии с описанными выше условиями дано определение отношений пространства состояний для задачи планирования заданий, приведена в листинге 12.3. Кроме того, в этом листинге имеется спецификация кон­кретной задачи составления расписания, показанной на рис. 12.6. Эти определения могут также использоваться в программе поиска по заданному критерию, приведен­ной в листинге 12.1. Одним из оптимальных решений, сформированных с помощью поиска по заданному критерию в проблемной области, определенной таким образом, является оптимальное расписание, показанное на рис. 12.6.

Глава 12. Эвристический поиск по заданному критерию

Листинг 12.3. Отношения, касающиеся рассматриваемой проблемной области, для задачи планирования заданий. Конкретная задача составления расписания, приведенная на рис. 12.6, определена также с помощью ее графа предшествования и начального (пустого) расписания, применяемого в качестве начального узла для поиска

/* Отношения, касающиеся рассматриваемой проблемной области, для задачи планирования заданий

Узлы в этом пространстве состояний представляют собой частичные расписания, заданные следующим образом:

[ WaitingTaskl/Dl_r WaitingTask2/D2,...] * К [ Taskl/Fl, Task2/F2,...] * FinTime

Первый лист определяет ожидающие задания и значения их продолжительности; второй список определяет задания, выполняемые в настоящее время, и значения времени их завершения, упорядоченные так, что Fl =< F2, F2 =< F3... Fintime — это самое последнее время завершения при текущем назначении процессоров */

4 s(Mode, SuccessorNode, Cost)

s{ Tasksl * (_/F I Activel] * Finl, Tasks2 * Active2 * Fin2, Cost):-

del(Task/D, Tasksl, Tasks2), % Выбрать ожидающую задачу

not (member! T/_, Tasks2], before(T, Task] }, % проверить правильность

% упорядочения, not (member! Tl/Fl, Activel), F < Fl, befoxet Tl, Task}), % в том числе

% активных задач Time is F + D, % Время завершения активных задач insert(Task/Time, Activel, Active2, Flnl, Fin2), Cost is Fln2 - Flnl.

s(Tasks *!_/F I Activel] * Fin, Tasks * Actlve2 * Fin, 0):-

insertidle (F, Activel, Active2}. % Оставить процессор в состоянии простоя

before! Tl, 12): - % Согласно правилам упорядочения задание

% Т1 предшествует заданию Т2 prec(Tl, T2).

before! Tl, 12):- prec(T, T2), before { Tl, T).

Insert,- S/A, [T/B j L], [S/A, Т/Б I L], F, F):- % Списки заданий упорядочены A =< В,!.

insert t S/A, [T/B I L], [T/B | LI], Fl, Г2):-

insert f S/A, L, U, Fl, F2).

insert t s/A, [], [s/A], _, A).

insertidle(A, [T/B I L], [idle/B, T/B I L]):- % Оставить процессор в
A < В,!, % состоянии простоя до наступления

% следующего, очередного времени завершения

lnsertldle(A, [T/B L], [Т/В 1 L1]):-insertidle (A, L, L1).

del (А, [А | Ь], LI. % Удалить элемент из списка

del(А, [3 [ L], [Б I L1]):-del(A, L, L1).

goal { [] * *_), % Целевое состояние ~ ни одно из заданий не находится % в состоянии ожидания

264 Часть И. Применение языка Prolog в области искусственного интеллекта

% Эвристическая оценка частичного расписания основана на оптимистической оценке % последнего времени завершения данного частично составленного расписания, % дополненного всеми ожидающими заданиями

Ъ{ Tasks * Processors * Fin,- HJ:-

totaltimeC Tasks, Tottime), % Общая продолжительность ожидающих заданий sumriumC Processors, Ftime, К), % Ftime - сумма значений времени завершения

% для всех процессоров, N - количество этих значений Finall is (Tottime + Ftime)/N, (Finall > Fin,!, H is Finall - Fin

H = 0

).

totaltime([], 0).

totaltime([_/D | Tasks], T):-totaltiraet Tasks, Tl), T is II + D.

sumnurti([], 0, 0}.

suamum([_/T I Procs], FT, N):-sumrmrM Procs, FTl_r Hit, II is HI + 1,

FT is FT1 + T.

% Граф предшествования заданий

prec(tl, t4). prec{ tl, t5).prec(tZ, t4). prec(t2, tS). prect t3, t5]. prec(t3, t6). prec(t3_r t7>.

* Начальный узел

start([tl/4, t2/2, t3/2, t4/20, t5/20, t6/ll, t7/ll] * [idle/0, idle/0, idle/0] * 0).

% Пример запроса: start! Problem), bestfirst (Problem, Sol).

Проект

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