Как оказалось, более эффективным подходом является дополнение метода поиска с восхождением к вершине способностью запоминать, а не способностью выбирать следующее действие случайным образом. Основная идея состоит в том, что необходимо хранить в памяти "текущую наилучшую оценку" H{s) стоимости достижения цели из каждого состояния, которое уже было посещено. На первых порах H(s) представляет собой только эвристическую оценку h (s) и обновляется по мере того, как агент приобретает опыт в исследовании пространства состояний. На рис. 4.15 показан простой пример одномерного пространства состояний. На рис. 4.15, а показано, что агент, по-видимому, зашел в тупик, попав в плоский локальный минимум, соответствующий затененному состоянию. Вместо того чтобы оставаться там, где находится, агент должен последовать по тому пути, который может рассматриваться как наилучший путь к цели согласно текущим оценкам стоимостей для соседних состояний. Оценка стоимости достижения цели через соседнее состояние s' равна оценке стоимости достижения s', которая складывается с оценкой стоимости достижения цели из s', т.е. равна c(s,a,s')+H(s').B данном примере имеются два действия, с оценками стоимости 1 + 9 и 1+2, поэтому, по всей видимости, лучше всего двигаться вправо. После этого становится очевидно, что оценка стоимости для этого затененного состояния, равная 2, была слишком оптимистической. Поскольку стоимость наилучшего хода равна 1 и он ведет в состояние, которое находится по меньшей мере на расстоянии 2 шагов от цели, то затененное состояние должно находиться по меньшей мере на расстоянии 3 шагов от цели, поэтому его оценка я должна быть обновлена соответствующим образом, как показано на рис. 4.15, б. Продолжая этот процесс, агент перейдет вперед и назад еще дважды, каждый раз обновляя оценку я и "сглаживая" локальный минимум до тех пор, пока не вырвется из него вправо.

Рис. 4.15. Пять итераций алгоритма LRTA* в одномерном пространстве состояний. Каждое состояние обозначено значением K(s), текущей оценкой стоимости достижения цели, а каждая дуга обозначена соответствующей ей стоимостью этапа. Затененное состояние показывает местонахождение агента, а значения, обновленные после каждой итерации, обозначаются двойным кружком