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

Основным методом решения задач k-медиан и размещения объектов является класс эвристик локального поиска, выполняющихся посредством поэтапных «локальных улучшений». На каждом этапе t эвристика поддерживает множество центров <math>C_t \;</math>. В задаче о k-медианах эта совокупность удовлетворяет условию <math>|C_t| = k \;</math>. На этапе локального улучшения вначале генерируется совокупность решений <math>\mathcal{E}_{t+1}</math> из <math>C_t \;</math>. Это выполняется таким образом, что <math>|\mathcal{E}_{t+1}|</math> оказывается полиномиальным относительно размера входных данных. Кроме того, в задаче о k-медианах каждый элемент <math>C \in \mathcal{E}_{t+1}</math> удовлетворяет условию <math>|C| = k \;</math>. На этапе улучшения полагаем <math>C_{t+1} = argmin_{C \in \mathcal{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_0 \;</math> и построение <math>\mathcal{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> называется «разрывом локальности» эвристики.

Вышеописанное обозначает простую замену не более чем p центров из <math>C_t \;</math> тем же количеством центров из <math>\mathcal{F} \backslash C_t</math>. Вспомним, что <math>|\mathcal{D}| = n</math> и <math>|\mathcal{F}| = m</math>. Очевидно, <math>|\mathcal{E}_t+1| \le (k(m - k))^p \le (km)^p</math>. Начальное множество <math>C_0 \;</math> выбирается произвольным образом. Значение p является параметром, от которого зависят время выполнения и коэффициент аппроксимации. Он выбирается константным, так что <math>|\mathcal{E}t|</math> является полиномом от m.