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

Тот факт, что f-стоимости вдоль любого пути являются неубывающими, означает также, что могут быть очерчены контуры равных f-стоимостей в пространстве состояний, полностью аналогичные контурам равных высот на топографической карте. Пример подобной схемы приведен на рис. 4.3. Внутри контура, обозначенного как 400, все узлы имеют значения f(n), меньшие или равные 400, и т.д. В таком случае, поскольку в поиске А* развертывается периферийный узел с наименьшей f-стоимостью, можно видеть, как поиск А* распространяется из начального узла, добавляя узлы в виде концентрических полос с возрастающей f-стоимостью.

Рис. 4.3. Карта Румынии, на которой показаны контуры, соответствующие f=380, f = 400 и f =420, притом что Arad является начальным состоянием. Узлы в пределах данного конкретного контура имеют f-стоимости, меньшие или равные значению стоимости контура

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

•    в поиске А* развертываются все узлы со значениями f(n)<c*;

•    поэтому в поиске А* могут развертываться некоторые дополнительные узлы, находящиеся непосредственно на "целевом контуре" (где f(n) =C*), прежде чем будет выбран целевой узел.

На интуитивном уровне представляется очевидным, что первое найденное решение должно быть оптимальным, поскольку целевые узлы во всех последующих контурах будут иметь более высокое значение f-стоимости и поэтому более высокое значение g-стоимости (поскольку все целевые узлы имеют значения h(n) = 0). Кроме того, на интуитивном уровне также очевидно, что поиск А* является полным. По мере добавления полос с возрастающими значениями f мы должны в конечном итоге достичь полосы, в которой значение f будет равно стоимости пути к целевому состоянию.

Следует отметить, что в поиске А* узлы со значением f (n) >С* не развертываются; например, как показано на рис. 4.2, не развертывается узел Timisoara, даже несмотря на то, что является дочерним узлом корневого узла. Эту ситуацию принято обозначать так, что происходит отсечение поддерева, находящегося ниже узла