10.1.3. Упорядоченный поиск

Хотя решение, полученное методом равных цен, оптимально, сам поиск решения не оптимален. Это было показано в примере, где на одном из шагов алгоритм рассматривал путь из Сан-Франциско в Лос-Анджелес через Портленд. Человек избежал бы этой лишней работы, пользуясь понятиями типа „север", „юг“ и „в общем направлении к...“. Такие критерии для выбора очередного шага не всегда годятся, но часто бывают полезны. Следующий алгоритм упорядоченного поиска основан на подобных идеях. Узел, который нужно раскрыть, выбирается отчасти на основе оценки длины решающего пути а не расстояния его от начальных узлов.

1. Поместить в список ОТКРЫТ в порядке возрастания оценок

2. Если список ОТКРЫТ пуст, решения нет.

3 Закрыть тот узел в ОТКРЫТ, для которого оценка минимальна.

4 Поместить в ОТКРЫТ. Если какой-то узел уже содержится в ОТКРЫТ, то пересчитать при

условии, что новая оценка, основанная на том, что узел закрыт, меньше предыдущей. При вычислении новой величины надо пересчитать также величины для всех потомков узла в списке ОТКРЫТ.

5. Перейти к шагу 2.

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

Это соответствует алгоритму перебора в ширину. Метод равных цен можно получить, полагая для всех