Поиск восхождением к вершине

Поиск восхождением к вершине (далее в статье просто восхождение) — это техника математической оптимизации, принадлежащая семейству алгоритмов локального поиска. Алгоритм является методом итерации, который начинается с произвольного решения задачи, а затем пытается найти лучшее решение путём пошагового изменения одного из элементов решения. Если решение даёт лучшее решение, делается приращение для получения нового решения и оно делается, пока не достигнем момента, в котором улучшение найти не удаётся.

Например, восхождение можно использовать для решения задачи коммивояжёра. Легко найти начальное решение, в котором коммивояжёр посещает все пункты, но которое, скорее всего, будет очень плохим по сравнению с оптимальным решением. Алгоритм начинается с этого решения и делает маленькие изменения в решении, при которых меняется порядок посещения двух пунктов. В конечном счёте, скорее всего, будет найден существенно более короткий маршрут.

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

Относительная простота алгоритма делает алгоритм популярным среди оптимизационных алгоритмов. Он широко используется в теории искусственного интеллекта для достижения целевого состояния из начальной точки. Метод выбора следующей точки и начальной точки может меняться, давая ряд связанных алгоритмов. Хотя более продвинутые алгоритмы, такие как алгоритм имитации отжига или поиск с запретами могут давать результаты лучше, в некоторых ситуациях восхождение работает с тем же успехом. Восхождение часто даёт лучший результат по сравнению с другими алгоритмами, когда ограничено время на осуществление поиска, что важно в системах реального времени, при условии, что малое число шагов сходится к хорошему решению (к оптимальному, либо близкому к нему). Другой экстремальный случай, сортировка пузырьком, может рассматриваться как алгоритм восхождения (каждая перестановка соседних элементов уменьшает число неупорядоченных пар), и такой подход далёк от оптимального даже при малых N, поскольку число перестановок растёт квадратично.

Восхождение является алгоритмом с отсечением по времени — он возвращает допустимое решение, даже если прерывается в любой момент времени.

Источник: Википедия