Нет.Простота поиска окрестности зависит от того, как определена окрестность.
Представьте себе проблему Max-2SAT : пусть U будет набором двоичных переменных x_1, ..., x_n и пусть C будет набором предложений c over U .Число литералов в каждом предложении не более двух, а вес w (c) предложения c ∈ C является положительным целым числом.Решением является присвоение x_1, ..., x_n .Предложение удовлетворяется, если хотя бы одна переменная равна 1. Цель состоит в том, чтобы найти назначение, которое максимизирует сумму весов удовлетворенных предложений.
Пусть FLIP будет окрестностьюструктура, в которой сосед r решения s получается путем переключения одного бита x_i в s .Эта окрестность имеет полиномиальный размер, и следующий лучший сосед может быть найден за полиномиальное время.
Пусть ALL будет структурой окрестности, которая содержит все возможные решения U .Эта окрестность имеет экспоненциальный размер, и для поиска следующего лучшего соседа требуется экспоненциальное время (которое в данном случае является глобальным оптимумом).Затем алгоритм локального поиска завершается после одного шага, так что на самом деле это не хороший алгоритм локального поиска, а алгоритм с экспоненциальной функцией соседства.
Существуют более сложные алгоритмы с экспоненциальной функцией соседства, например, в «Локальный поиск с экспоненциальной окрестностью для задачи балансировки нагрузки серверов »И.А. Давыдов, П.А. Кононова, Ю.А.Кочетов, 2014. Они ищут следующего соседа со смешанной целочисленной программой в наборе всех возможных подмножеств дисков на всех серверах, которые экспоненциально много возможных соседей.
Если у вас есть проблема локального поиска, для которойВы можете создать какое-то решение за полиномиальное время, рассчитать стоимость решения за полиномиальное время и найти лучшего соседа за полиномиальное время, ваша проблема находится в классе сложности PLS (см. «Насколько прост локальный поиск?» Дэвида С. Джонсона,Christos H Papadimitriou и Mihalis Yannakakis, 1988).