Алгоритм RBFS [840], [841] фактически является лишь немного более сложным по сравнению с алгоритмом, приведенным в листинге 4.1. Последний вариант ближе к независимо разработанному алгоритму, получившему название алгоритма итеративного развертывания, или сокращенно IE (Iterative Expansion) [1324]. В алгоритме RBFS используется не только верхняя, но и нижняя граница; эти два алгоритма при использовании допустимых эвристических функций ведут себя одинаково, но RBFS развертывает узлы в порядке первого наилучшего совпадения даже при наличии недопустимой эвристической функции. Идея отслеживания наилучшего альтернативного пути появилась еще раньше в изящной реализации алгоритма А* на языке Prolog, предложенной Братко [174], и в алгоритме DTA* [1332]. В последней работе обсуждаются также метауровневые пространства состояний и метау-ровневое обучение.

Алгоритм МА* впервые опубликован в [229]. Появление алгоритм SMA*, или Simplified MA*, стало результатом попытки реализовать МА* в качестве алгоритма сравнения для метода IE [1324]. Кайндл и Корсанд [763] применили алгоритм SMA* для создания алгоритма двунаправленного поиска, который функционирует значительно быстрее по сравнению с предшествующими алгоритмами. В [845] описан подход по принципу "разделяй и властвуй", а в [1645] представлен алгоритм А* поиска в графе с ограничением памяти. Обзор методов поиска с ограничением памяти приведен в [842].

Идея о том, что допустимые эвристические функции могут быть получены с помощью ослабления условий задачи, впервые опубликована в оригинальной статье [645], авторы которой использовали эвристику на основе минимального связующего дерева для решения задачи TSP (см. упр. 4.8).

Автоматизация процесса ослабления условий задачи была успешно осуществлена Придитисом [1237] на основе его более ранней совместной работы с Мостоу [1092]. Использование баз данных шаблонов для составления допустимых эвристических функций предложено в [313] и [523]; базы данных с непересекающимися шаблонами описаны в [844]. Вероятностная интерпретация эвристических функций глубоко исследована в [616] и [1188].

Безусловно, наиболее исчерпывающим источником сведений об эвристических функциях и алгоритмах эвристического поиска является книга Перла Heuristics [1188]. В этой книге приведено особенно хорошее описание широкого разнообразия версий и вариантов алгоритма А*, включая строгие доказательства их формальных свойств. В работе Канала и Кумара представлена антология важных статей по эвристическому поиску [767]. Результаты новейших исследований в области алгоритмов поиска регулярно публикуются в журнале Artificial Intelligence.