Пространство состояний, которое не следует смешивать с графом
образуется следующим способом если в Я существует дуга
причем вершина
не принадлежит подпоследовательности
то имеется дуга, направленная из состояния
в состояние
Слагаемое
при
есть сумма стоимостей
Слагаемое
вычисляется следующим способом для каждой вершины, не принадлежащей подпоследовательности
берется наименьшая стоимость для всех дуг, входящих в эту вершину, тогда величина
является суммой таких наименьших стоимостей Данный член
конечно, является нижней оценкой в смысле определения алгоритмов А. В результате такого расчета оценочной функции получаем маршрут с минимальной стоимостью
Рассмотрим пример, изображенный на рис 5.1,а. На рис. 5.1, б показаны результаты расчета минимальной стоимости дуг, входящих в каждую вершину, а на рис 5 1, в изображен граф поиска, полученный на момент останова программы, реализующей вышеупомянутый алгоритм. Определенное таким образом конечное состояние имеет вид
а его стоимость равна 11. Отметим, что в случае равенства оценок среди всех состояний с наименьшей оценкой выбирается для раскрытия самое глубинное состояние в графе поиска, т. е. принятое правило работает по принципу «больше влево».
На рис. 5.1, в для каждого состояния
отмечено значение оценочной функции
Кроме того, в рамке отмечен порядковый номер раскрытия различных состояний. Таким образом, раскрытию
был присвоен ранг 5 (но в этом случае нельзя было достичь никакого состояния-потомка) Раскрытие состояний
или
могло бы обеспечить другие оптимальные решения. Читатель может убедиться, что в данном примере этого не происходит