Алгоритм поиска с восхождением к вершине показан в листинге 4.2. Он представляет собой обычный цикл, в котором постоянно происходит перемещение в направлении возрастания некоторого значения, т.е. подъем. Работа этого алгоритма заканчивается после достижения "пика", в котором ни одно из соседних состояний не имеет более высокого значения. В данном алгоритме не предусмотрено сопровождение дерева поиска, поэтому в структуре данных текущего узла необходимо регистрировать только состояние и соответствующее ему значение целевой функции. В алгоритме с восхождением к вершине не осуществляется прогнозирование за пределами состояний, которые являются непосредственно соседними по отношению к текущему состоянию. Это напоминает попытку альпиниста, страдающего от амнезии, найти вершину горы Эверест в густом тумане.

Листинг 4.2. Алгоритм поиска с восхождением к вершине (версия с наиболее крутым подъемом), который представляет собой самый фундаментальный метод локального поиска. На каждом этапе текущий узел заменяется наилучшим соседним узлом; в данной версии таковым является узел с максимальным значением Value, но если используется эвристическая оценка стоимости h, то может быть предусмотрен поиск соседнего узла с минимальным значением h

Для иллюстрации поиска с восхождением к вершине воспользуемся задачей с восемью ферзями, которая представлена на с. 118. В алгоритмах локального поиска обычно применяется формулировка полного состояния, в которой в каждом состоянии на доске имеется восемь ферзей, по одному ферзю в каждом столбце. Функция определения преемника возвращает все возможные состояния, формируемые путем перемещения отдельного ферзя в другую клетку одного и того же столбца (поэтому каждое состояние имеет 8x7 = 5 6 преемников). Эвристическая функция стоимости h определяет количество пар ферзей, которые атакуют друг друга либо прямо, либо косвенно (атака называется косвенной, если на одной горизонтали, вертикали или диагонали стоят больше двух ферзей). Глобальный минимум этой функции становится равным нулю, и это происходит только в идеальных решениях. На рис. 4.8, а показано состояние со значением h=17. На этом рисунке также показаны значения всех преемников данного состояния, притом что наилучшие преемники имеют значение h=12. Алгоритмы с восхождением к вершине обычно предусматривают случайный выбор в множестве наилучших преемников, если количество преемников больше одного.