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

Перейти к навигации Перейти к поиску
Строка 32: Строка 32:


== Основные результаты ==
== Основные результаты ==
Основным методом решения задач k-медиан и размещения объектов является класс эвристик локального поиска, выполняющихся посредством поэтапных «локальных улучшений». На каждом этапе t эвристика поддерживает множество центров Ct. В задаче о k-медианах эта совокупность удовлетворяет условию |Ct| = k. На этапе локального улучшения вначале генерируется совокупность решений Et+1 из Ct . Это выполняется таким образом, что |Et+1| оказывается полиномиальным относительно размера входных данных. Кроме того, в задаче о k-медианах каждый элемент C 2 Et+1 удовлетворяет условию |C| = k. На этапе улучшения полагаем Ct+1 = argminC2Et+1 f (C). Для предварительно заданного параметра " > 0 итерации улучшений останавливаются на первом этапе T, для которого выполняется f (CT) _ (1 _ ") f (CT_1).
Основным методом решения задач 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>.




Основными проблемами разработки являются конкретизация начального множества C0 и построение Et+1 из Ct . Основными проблемами анализа являются ограничение количества этапов T до завершения работы алгоритма и качество финального решения f(CT) по отношению к оптимальному решению f (C_). Соотношение ( f (CT ))/( f (C_)) называется «разрывом локальности» эвристики.
Основными проблемами разработки являются конкретизация начального множества <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> называется «разрывом локальности» эвристики.




Источник — http://pco.iis.nsk.su/wega/index.php/Локальный_поиск_для_задачи_о_k-медианах_и_задачи_о_размещении_объектов