Очевидным примером допустимой эвристической функции является функция определения расстояния по прямой, которая уже использовалась в данной главе для поиска пути в Бухарест. Расстояние по прямой является допустимым, поскольку кратчайший путь между любыми двумя точками лежит на прямой; это означает, что длина прямого пути по определению не может представлять собой переоценку длины пути. На рис. 4.2 показан процесс поиска А* пути в Бухарест с помощью дерева. Значения д вычисляются на основании стоимостей этапов, показанных на рис. 3.1, а значения приведены в табл. 4.1. Следует, в частности, отметить, что узел Bucharest впервые появляется в периферии на этапе, показанном на рис. 4.2, д, но не выбирается для развертывания, поскольку его f-стоимость (450) выше, чем стоимость узла Pitesti (417). Иными словами эту ситуацию можно описать так, что может существовать решение, при котором путь проходит через город Питешти со стоимостью, достигающей 417, поэтому алгоритм не останавливается на решении со стоимостью 450. Данный пример может служить общим свидетельством того, что <^= поиск А* с использованием алгоритма Tree-Search является оптимальным, если функция h(n) допустима. Предположим, что на периферии поиска появился неоптимальный целевой узел G2, а стоимость оптимального решения равна С*. В таком случае, поскольку узел G2 неоптимален, a h(G2) =0 (это выражение справедливо для любого целевого узла), можно вывести следующую формулу:

Теперь рассмотрим периферийный узел л, который находится в оптимальном пути решения, например узел Pi testi в примере, приведенном в предыдущем абзаце. (Если решение существует, то всегда должен быть такой узел.) Если функция h(n) не переоценивает стоимость завершения этого пути решения, то справедлива следующая формула:

Таким образом, доказано, что ., поэтому узел G2 не развертывается и поиск А* должен вернуть оптимальное решение.