Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями

Основным методом решения задач k-медиан и размещения объектов является класс эвристик локального поиска, выполняющихся посредством поэтапных «локальных улучшений». На каждом этапе t эвристика поддерживает множество центров <math>C_t \;</math>. В задаче о k-медианах эта совокупность удовлетворяет условию <math>|C_t| = k \;</math>. На этапе локального улучшения вначале генерируется совокупность решений <math>\mathbb{E}_{t+1}</math> из <math>C_t \;</math>. Это выполняется таким образом, что <math>|\mathbb{E}_{t+1}|</math> оказывается полиномиальным относительно размера входных данных. Кроме того, в задаче о k-медианах каждый элемент <math>C \in \mathbb{E}_{t+1}</math> удовлетворяет условию |C| = k. На этапе улучшения полагаем <math>C_{t+1} = argmin_{C \in \mathbb{E}_{t+1}} f(C)</math>. Для предварительно заданного параметра <math>\varepsilon > 0 \;</math> итерации улучшений останавливаются на первом этапе T, для которого выполняется <math>f(C_T) \ge (1 - \varepsilon) f(C_{T - 1}) \;</math>.

Основными проблемами разработки являются конкретизация начального множества <math>C' \;</math> и построение <math>\mathbb{E}_{t+1}</math> из <math>C_t \;</math>. Основными проблемами анализа являются ограничение количества этапов T до завершения работы алгоритма и качество финального решения <math>f(C_T) \;</math> по отношению к оптимальному решению <math>f(C^*) \;</math>. Соотношение <math>(f(C_T))/( f(C^*)) \;</math> называется «разрывом локальности» эвристики.

Поскольку каждый этап улучшения уменьшает значение решения по меньшей мере на коэффициент (1 _ "), время выполнения в пересчете на этапы улучшения задается следующим выражением (здесь D – отношение между самым большим и самым маленьким расстояниями в метрическом пространстве над D [ F).

T _ log1/(1_") _ f (C0)

являющееся полиномиальным относительно размера входных данных. На каждом этапе улучшения требуется вычисление <math>f(C) \;</math> для <math>C \in \mathbb{E}_t</math>. Оно является полиномиальным относительно размера входных данных, поскольку <math>|\mathbb{E}_t|</math> предполагается полиномиальным.