2. Стратегии поиска в пространстве состояний

1. Запись на языке графов

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

Граф состоит из множества (не обязательно конечного) вершин. Опреде­ленные пары вершины соединены дугами, и эти дуги направлены от одного элемента пары к другому. Такой граф называется направленным. Для на­ших целей вершины помечены базами данных, а дуги — правилами. Если дуга направлена от вершины п* — к вершине nj, то говорят, что вершина по­является преемником вершины п*, а п* — родителем вершины nj. В гра­фах, представляющих для нас интерес, у любой вершины может быть лишь конечное число преемников. (У наших систем продукций имеется лишь ко­нечное число применимых правил.) Обе вершины в паре одновременно могут быть преемниками друг друга; в этом случае пара направленных дуг иногда заменяется ребром.

Дерево — частный случай графа, в котором каждая вершина имеет не более одного родителя. Вершина дерева, не имеющая родителя, называется корневой, а не имеющая преемников — концевой. Мы говорим, что корневой вершине соответствует глубина, равная нулю. Глубина любой другой верши­ны дерева определяется как глубина предшествующей вершины плюс 1.

Последовательность вершин n_il , n_i2 ,щ₃,..., n_ik, где каждая n_ij является преемником n_ij_₁ для j = 2,... ,k, называется путем длиной k от n_i1 к n_ik. Если существует путь от вершины n_i к вершине nj, то говорят, что вер­шина nj достижима из вершины n_i. В этом случае nj является потомком вершины n_i и n_i — предком вершины nj.

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

Часто оказывается удобным приписать положительные стоимости ду­гам, чтобы отразить таким образом стоимость применения соответствующего правила. Мы используем обозначение c(n_i,n_j-) для стоимости дуги, направ­ленной от вершины n_i к вершине nj. (Для некоторых дальнейших рассмот­рений важно, чтобы все они были больше некоторого произвольно малого положительного числа e.) Стоимость пути между двумя вершинами равна сумме стоимостей всех дуг, соединяющих вершины, лежащие на этом пути. В некоторых задачах мы хотим найти путь между двумя вершинами, имеющий минимальную стоимость.

В задаче простейшего типа ищем путь (возможно, имеющий минималь­ную стоимость) между вершиной s, представляющей исходное состояние ра­бочей памяти, и известной вершиной t, представляющей другое состояние. Чаще, однако, встречается ситуация, где требуется найти путь между вер­шиной s и любой вершиной из множества {t_i}, представляющего состояния рабочей памяти, удовлетворяющие терминальному условию. Это множество {t_i} называют целевым и каждую вершину t в {t_i} — целевой.

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

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

2. Представление задачи в пространстве состояний

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

Пространство состояний — это четверка {N, A, S, GD}, где N есть мно­жество вершин графа или состояний в процессе решения задачи, A есть мно­жество дуг между вершинами, соответствующих шагам в процессе решения задачи, S есть непустое множество начальных состояний задачи, GD есть непустое подмножество N, состоящее из целевых состояний. Эти состояния могут быть описаны одним из следующих способов:

• измеряемыми свойствами состояний, встречающихся в процессе поиска;

• свойствами путей, возникающих в процессе поиска, например, стоимо­стью перемещения по дугам пути.

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

Пример 2. Рассмотрим в качестве примера систему продукций, множе­ства правил которой приведено в табл. 3.

Таблица 3

Правило	Условие	Следствие
R1	b	d
R2	а	b
R3	а	с
R4	с	x

Пусть начальное состояние рабочей памяти Start содержит утвер­ждение а. Граф пространства состояний для такой системы продукций приведен на рис. 5.

3. Стратегия с возвращением

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

Рис. 5. Граф пространства состояний

пройденных вершин и исследует все ее вершины-братья, спускаясь по одной из ветвей.

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

1. SL (State List) —список исследованных состояний рассматриваемого пу­ти. Если цель уже найдена, то SL содержит список состояний пути ре­шения.

2. NSL (New State List) —список новых состояний, он содержит вершины, подлежащие рассмотрению, т.е. список вершин, потомки которых еще не были порождены и рассмотрены.

3. DE (Dead Ends)—список тупиков, т.е. список вершин, потомки которых уже были исследованы, но не привели к цели. Если состояние из этого списка снова встречается в процессе поиска, то оно обнаруживается в списке DE и исключается из рассмотрения.

При описании алгоритма поиска с возвратами на графах общего вида (не только для деревьев) необходимо учитывать возможность повторного появления состояний, чтобы избежать их повторного рассмотрения, а также петель, ведущих к зацикливанию алгоритма поиска пути. Это обеспечивается проверкой каждой вновь порожденной вершины на ее вхождение в один из трех вышеуказанных списков. Если новое состояние обнаружится хотя бы в одном из двух списков SL или DE, значит, оно уже рассматривалось, и его следует проигнорировать.

Обозначим CurrentState текущее состояние при поиске с возвратами. Состояние CurrentState всегда равно последнему из состояний, занесен­ных в список SL, и представляет «фронтальную» вершину на построенном в данный момент пути. Правила вывода, ходы в игре или иные соответ­ствующие операторы решения задачи упорядочиваются и применяются к CurrentState. В результате возникает упорядоченное множество новых со­стояний, потомков CurrentState. Первый из этих потомков объявляется но­вым текущим состоянием, а остальные заносятся в список новых состояний

NSL для дальнейшего изучения. Новое текущее состояние заносится в список состояний SL, и поиск продолжается. Если текущее состояние CurrentState не имеет потомков, то оно удаляется из списка состояний SL (именно в этот момент алгоритм «возвращается назад»), и исследуется какой-либо из остав­шихся потомков его предка в списке состояний SL.

function Backtrack; begin

SL := [Start]; NSL := [Start]; DE := [];

CurrentState := Start; ’инициализация

while NSL <> [ ] do ’пока существуют неисследованные состояния begin

if CurrentState = goal (или удовлетворяет описанию цели) then return SL;

’при нахождении цели вернуть список состояний пути if CurrentState не имеет потомков (исключая узлы, входящие в DE, SL и NSL) then begin while

SL не пуст и CurrentState = первый элемент списка SL do begin

добавить CurrentState в DE;

’внести состояние в список тупиков удалить первый элемент из SL; ’возврат

удалить первый элемент из NSL;

CurrentState := первый элемент NSL; end

добавить CurrentState в SL; end else begin

поместить потомок CurrentState (кроме узлов, уже содержащихся в DE, SL или NSL) в NSL;

CurrentState := первый элемент NSL; добавить CurrentState в SL end;

end; return FAIL; end.

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

• формируется список неисследованных состояний (NSL), для того чтобы иметь возможность возвратиться к любому из них;

• поддерживается список «неудачных» состояний (DE), чтобы оградить ал­горитм от проверки бесполезных путей;

• поддерживается список узлов (SL) текущего пути, который возвращается по достижении цели;

• каждое новое состояние проверяется на вхождение в эти списки, чтобы предотвратить зацикливание.

Пример 3. Продемонстрируем работу алгоритма поиска с возвратами на графе пространства состояний некоторой системы продукций, изображен­ного на рис. 6. Целевыми вершинами будем считать вершины G и H.

Рис. 6. Граф пространства состояний

Тогда работа такой системы продукций в соответствии с алгоритмом Backtrack приведена в табл. 4.

Таблица 4

Шаг	CurrentState	SL	NSL	DE
0	A	[A]	[A]	[]
1	B	[B A]	[B C A]	[]
2	D	[D B A]	[D E B C A]	[]
3	E	[E B A]	[E B C A]	[D]
4	F	[F E B A]	[F G E B C A]	[D]
5	H	[H F E B A]	[H F G E B C A]	[D]
6	goal	[H F E B A]

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

4. Поиск в ширину

Поиск в ширину осуществляется с использованием списков open и closed, позволяющих отслеживать продвижение в пространстве состояний. Список open, подобно NSL в алгоритме поиска с возвратами, содержит сгенерирован­ные состояния, потомки которых еще не были исследованы. Порядок удале­ния состояний из списка open определяет порядок поиска. В список closed заносятся уже исследованные состояния. Список closed объединяет списки DE и SL, используемые в алгоритме поиска с возвратами.

function BreadthFirstSearch;

begin

инициализация

’есть состояния

open := [Start]; closed := [ ]; while open <> [ ] do begin

удалить крайнее слева состояние из open, скажем X; if X - цель then

return SUCCESS

’цель найдена

else begin

сгенерировать потомок X;

поместить X в список closed;

исключить потомок X, если он уже в списке

проверка на цикл

open или closed;

поместить остальные потомки в правый конец списка open

end

end

return FAIL

’очередь

’состояний не осталось

end.

Дочерние состояния генерируются правилами вывода, допустимыми хо­дами игры, или другими операциями перехода состояний. На каждой ите­рации генерируются все дочерние вершины состояния X и записываются в open. Заметим, что список open действует как очередь и обрабатывает дан­ные в порядке поступления (или «первым поступил — первым обслужен»). Это структура данных FIFO (first-in—first-out). Состояния добавляются в список справа, а удаляются слева. Таким образом, в поиске участвуют со­стояния, которые находятся в списке open дольше всего, обеспечивая поиск в ширину. Дочерние состояния, которые были уже записаны в списки open или closed, отбрасываются. Если алгоритм завершается из-за невыполне­ния условия цикла while (open = [ ]), то можно заключить, что весь граф исследован, а желаемая цель не достигнута. Следовательно, поиск потерпел неудачу.

Пример 4. Проследим путь алгоритма BreadthFirstSearch поиска в ши­рину на системе продукций из примера 2. Обозначим вершины графа про­странства состояний этой системы продукций так, как показано на рис. 7.

Целевыми вершинами будем считать те, которые содержат утвер­ждение x, т.е. вершины 6, 8 и 9. Работа алгоритма BreadthFirstSearch приведена в табл. 5.

Поскольку при поиске в ширину узлы графа рассматриваются по уров­ням, сначала исследуются те состояния, пути к которым короче. Поиск в ши­рину, таким образом, гарантирует нахождение кратчайшего пути от началь­ного состояния к цели. Более того, поскольку вначале исследуются состоя­ния, найденные по кратчайшему пути, при повторном проходе это состояние отбрасывается. Иногда помимо имен состояний в open и closed необходимо хранить дополнительную информацию. Например, заметим, что алгоритм поиска в ширину не поддерживает список состояний на текущем пути к це­ли, как это делалось при поиске с возвратами (Backtrack) в списке SL. Все посещенные состояния хранятся в closed. Если путь является решением,

Рис. 7. Граф пространства состояний из примера 2

то он возвращается алгоритмом. Это может быть сделано путем накопления информации о предках для каждого состояния. Состояние хранится вместе с записью родительского состояния, т.е. в виде пары (состояние, родитель). Ко­гда цель найдена, алгоритм может восстановить путь решения, прослеживая его в обратном направлении от цели к начальному состоянию по родитель­ским состояниям. Заметим, что состояние A имеет родителя nil (нуль), т.е. является начальным состоянием. Это служит сигналом прекращения восста­новления пути.

Таблица 5

Шаг	open	closed
1	[1]	[]
2	[2 3]	[1]
3	[3 4 5]	[2 1]
4	[4 5 6]	[3 2 1]
5	[5 6 7]	[4 3 2 1]
6	[6 7 8]	[5 4 3 2 1]
7	SUCSESS

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

5. Поиск в глубину

Опишем алгоритм поиска в глубину — упрощенный алгоритм поиска с воз­вратами, уже представленный ранее. В этом алгоритме состояния-потомки добавляются и удаляются с левого конца списка open, т.е. список open ре­ализован как стек магазинного типа или структура LIFO (last-in-first-out, «последним пришел — первым обслужен»). При организации списка open в виде стека предпочтение отдается самым «молодым» (недавно сгенерирован­ным состояниям), т.е. осуществляется принцип поиска в глубину.

function DepthFirstSearch; begin

open := [Start]; 'инициализация

closed := [ ];

while open <> [ ] do 'есть состояния

begin

удалить крайнее слева состояние из open, скажем X; if X - цель then return SUCCESS 'цель достигнута

else begin

сгенерировать потомок X; поместить X в список closed;

исключить потомок X, если он уже в open или closed;

'проверка цикла поместить остальные потомки в левый конец списка open

'стек

end

end;

return FAIL 'состояний не осталось

end.

Пример 5. Проследим путь алгоритма DepthFirstSearch поиска в глуби­ну на графе, изображенном на рис. 7. Целевыми вершинами будем считать те, которые содержат утверждение х, т.е. вершины 6, 8, 9. Работа ал­горитма DepthFirstSearch приведена в табл. 6.

Таблица 6

Шаг	open	closed
1	[1]	[]
2	[2 3]	[1]
3	[4 5 3]	[2 1]
4	[7 5 3]	[4 2 1]
5	[9 5 3]	[7 4 2 1]
7	SUCCESS

6. Эвристические процедуры поиска на графе Использование эвристик

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

Для многих задач имеется возможность использовать некоторую инфор­мацию, относящуюся к рассматриваемой задаче, чтобы содействовать сокра­щению поиска. Информацию такого рода обычно называют эвристической, а процедуры поиска, использующие ее, — методами эвристического поиска. Часто можно определить эвристики, уменьшающие затраты на поиск (по сравнению, например, с методом поиска в ширину), но не ценой лишения гарантии того, что путь с минимальной длиной будет найден. Некоторые эв­ристики очень существенно уменьшают затраты на поиск, но не гарантируют нахождения пути минимальной стоимости. В большинстве практических за­дач мы стремимся к тому, чтобы минимизировать некоторую комбинацию стоимости пути к цели и стоимости поиска, необходимого для нахождения этого пути. Более того, нас обычно интересуют такие методы поиска, кото­рые минимизируют эту комбинацию, усредненную по всем ожидаемым за­дачам. Если усредненная стоимость комбинации для первого метода поиска меньше, чем для второго, то говорят, что первый метод поиска имеет боль­шую эвристическую силу, чем второй. Заметим, что из нашего определения не следует, что метод поиска, обладающий большей эвристической силой, гарантирует нахождение пути минимальной стоимости.

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

«Жадный» алгоритм поиска

Наиболее простой путь эвристического поиска — это применение процедуры поиска экстремума (hill climbing). Стратегии, основанные на поиске экстре­мума, оценивают не только текущее состояние поиска, но и его потомков. Для дальнейшего поиска выбирается наилучший потомок; при этом о его братьях и родителях просто забывают. Поиск прекращается, когда достига­ется состояние, которое лучше чем любой из его наследников. Так как в этой стратегии данные о предыдущих состояниях не сохраняются, то алгоритм не может быть восстановлен из точки, которая привела к «неудаче». Основная проблема стратегий поиска экстремума — это их тенденция останавливать­ся в локальном максимуме. Другими словами, как только они достигают состояния, имеющего лучшую оценку, чем его потомки, алгоритм заверша­ется. Если это состояние является не решением задачи, а только локальным максимумом, то такой алгоритм неприемлем для данной задачи. Это зна­чит, что решение может быть оптимальным на ограниченном множестве, но из-за формы всего пространства, возможно, никогда не будет выбрано наилучшее решение. Дело в том, что «лучший» не означает «идеальный». Методы поиска без механизмов возврата или других приемов восстановле­ния не могут отличить локальный максимум от глобального. Существуют методы приближенного решения этой проблемы, например, случайное воз­мущение оценки. Однако гарантированно решать задачи с использованием техники поиска экстремума нельзя. Несмотря на эти ограничения, алгоритм поиска экстремума может быть достаточно эффективным, если оцениваю­щая функция позволяет избежать локального максимума и зацикливания алгоритма. В общем, однако, эвристический поиск требует более гибкого ме­тода, предусмотренного в «жадном» алгоритме поиска, где при использо­вании приоритетной очереди возможно восстановление алгоритма из точки локального максимума. Подобно алгоритмам поиска в глубину и алгорит­мам поиска в ширину, «жадный» алгоритм поиска использует списки сохра­ненных состояний: список open отслеживает текущее состояние поиска, а в closed записываются уже проверенные состояния. На каждом шаге алго­ритм записывает в список open состояние с учетом некоторой эвристической оценки его «близости к цели». Таким образом, на каждой итерации рассмат­риваются наиболее перспективные состояния из списка open. Псевдокод для функции, реализующей «жадный» алгоритм поиска, приведен ниже.

function BestFirstSearch; begin

open := [Start]; ’инициализация

closed := [ ];

while open <> [ ] do ’оставшиеся состояния

begin

удалить первое состояние X из списка open; if X = goal, return путь от Start к X else begin

сгенерировать потомок X; for каждого потомка X do case

потомок не содержится в списке open или closed: begin

присвоить потомку эвристическое значение; добавить потомок в список open end;

потомок уже содержится в списке open:

if потомок был достигнут по кратчайшему пути then записать это состояние в список open потомок уже содержится в списке closed:

if потомок был достигнут по кратчайшему пути then begin

удалить состояние из списка closed; добавить потомок в список open end;

end; ’ конец case

поместить X в список closed; переупорядочить состояния в списке open в соответствии с эвристикой (лучшие слева)

end;

return FAIL ’список OPEN пуст

end.

На каждой итерации функция BestFirstSearch удаляет первый элемент из списка open. Достигнув цели, алгоритм возвращает путь, который ве­дет к решению. Заметим, что каждое состояние сохраняет информацию о предшествующем состоянии, чтобы впоследствии восстановить его и позво­лить алгоритму найти кратчайший путь к решению. Если первый элемент в списке open не является решением, то алгоритм использует продукцион­ные правила проверки соответствия и операции, чтобы сгенерировать все возможные потомки данного элемента. Если потомок уже находится в спис­ке open или closed, то алгоритм выбирает кратчайший из двух возможных путей достижения этого состояния. Затем функция BestFirstSearch вычис­ляет эвристическую оценку состояний в списке open и сортирует список в соответствии с этими эвристическими значениями. При этом «лучшие» со­стояния ставятся в начало списка.

Применение оценочных функций

Эвристическую информацию можно использовать для упорядочения вершин в списке open таким образом, что процесс поиска будет распространяться по тем участкам границы, которые представляются наиболее перспективными. Чтобы применить такую процедуру упорядочения, нужен метод вычисле­ния «перспективности» вершины. В одном из таких методов используется функция, принимающая на вершинах действительные значения и называе­мая оценочной. В основе оценочных функций могут лежать самые разнооб­разные идеи: можно определить вероятность того, что некоторая вершина принадлежит наилучшему пути; можно вводить меры расстояния или раз­личия между произвольной вершиной и целевым множеством; кроме того, в настольных играх или головоломках для рассматриваемой конфигурации часто подсчитывается число очков — на основании тех ее особенностей, ко­торые, видимо, связаны с ее перспективностью.

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

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

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

Алгоритм А

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

Перед тем как продемонстрировать некоторые свойства этой оценочной функции, введем ряд полезных обозначений. Пусть функция k(ni,nj) выра­жает реальную стоимость пути минимальной стоимости между двумя произ­вольными вершинами n_i и nj. (Функция k не определена для вершин, меж­ду которыми нет пути.) Стоимость такого пути от вершины n к некоторой конкретной целевой вершине n_i в этом случае равна k(n,t_i). Пусть h*(n) — минимум всех значений k(n, t_i) на полном множестве целевых узлов {t_i}. Та­ким образом, h*(n) — стоимость пути минимальной стоимости от вершины n к целевой вершине и любой путь от вершины n к целевой, для которой до­стигается h*(n), является оптимальным путем от n к цели. (Функция h* не определена для любой вершины n, не имеющей доступа ни к одной целевой вершине.)

Часто нас интересует стоимость k(s, n) оптимального пути от заданной исходной вершины s к некоторой произвольной вершине n. Чтобы несколько упростить наши обозначения, введем новую функцию g*(n) = k(s,n) для всех n, доступных из s.

Далее, определим функцию f * так, чтобы ее значение f *(n) для любой вершины n было бы реальной стоимостью оптимального пути от вершины s к вершине n плюс стоимость оптимального пути от вершины n к целевой:

f *(n) = g *(n) + h*(n).

Функция f *(n), следовательно, равна стоимости оптимального пути при усло­вии, что он проходит через вершину n. (Заметим, что f *(s) = h*(s) — это ре­альная стоимость оптимального пути от s к цели в отсутствие ограничений.)

Мы хотим, чтобы наша оценочная функция f была оценкой f *. Эта оцен­ка дается соотношением

^{f (n)} = g⁽ⁿ⁾ + ^h(n), где g — оценка g* и h — оценка h*. Очевидно, в качестве g(n) можно выбрать стоимость пути на дереве поиска от s к n, которая получается в результате суммирования стоимостей дуг, вычисленных при отслеживании указателей от n к s. (Этот путь является путем самой меньшей стоимости от s к n, найденным до сих пор алгоритмом поиска. Значение g(n) для некоторых вершин можно уменьшить, если дерево поиска видоизменяется на шаге 7.) Заметим, что такое определение подразумевает g(n) > g*(n). При установле­нии h(n) — оценки h*(n) — исходим из эвристической информации об области задачи. Назовем h эвристической функцией. Итак, пусть в качестве оценоч­ной функции имеем

^{f (n)} = g⁽ⁿ⁾ + ^h(n).

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