Методы локального поиска имеют долгую историю в математике и компьютерных науках. Безусловно, как очень эффективный метод локального поиска в непрерывных пространствах, в которых доступна информация о градиенте, может рассматриваться метод Ньютона-Рафсона [1132], [1266]. В [182] можно найти классический справочник по алгоритмам оптимизации, для которых не требуется такая информация. Алгоритм лучевого поиска, представленный в данной книге как алгоритм локального поиска, впервые появился в виде одного из вариантов методов динамического программирования с ограничением по ширине, предназначенного для распознавания речи, в системе Harpy [952]. Еще один алгоритм подобного типа был глубоко проанализирован Перлом [1188] (глава 5).

В последние годы снова пробудился интерес к теме локального поиска под влиянием исключительно качественных результатов, полученных при решении таких крупных задач удовлетворения ограничений, как задача с п-ферзями [1058] и задача формирования логических рассуждений [1382], а также под влиянием успешного включения в алгоритмы методов рандомизации, методов множественного одновременного поиска и других усовершенствований. Это возрождение интереса к алгоритмам, названным Кристосом Пападимитриу алгоритмами "новой эры", вызвало также повышенный интерес теоретиков в области компьютерных наук [13], [848]. В области исследования операций завоевал широкую популярность один из вариантов поиска с восхождением к вершине, получивший название поиска с запретами [563], [564]. В этом алгоритме, основанном на моделях ограниченной кратковременной памяти человека, ведется список запретов, состоящий из к ранее посещенных состояний, которые нельзя посещать повторно; это позволяет данному алгоритму не только выполнять поиск в графах более эффективно, но и выходить из некоторых локальных минимумов. Еще одним полезным усовершенствованием алгоритма поиска с восхождением к вершине является алгоритм Stage [163]. Идея этого алгоритма состоит в том, что для получения представления об общей форме ландшафта должны использоваться локальные максимумы, найденные в результате восхождения к вершине с перезапуском случайным образом. Данный алгоритм согласует гладкую поверхность с множеством локальных максимумов, а затем аналитическим путем вычисляет глобальный максимум этой поверхности. Полученный глобальный максимум становится новой точкой перезапуска. Успешное функционирование этого алгоритма было испытано на практике при решении трудных задач. В [573] показано, что распределения времени выполнения алгоритмов, в которых систематически применяются возвраты, часто имеют форму распределений с широким хвостом (heavy-tailed distribution), а это означает, что вероятность очень продолжительного времени выполнения выше, чем можно было бы предположить в случае нормального распределения значений времени выполнения. Данные результаты могут служить теоретическим обоснованием применимости алгоритмов с перезапуском случайным образом.