4511
правок
Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Локальный поиск для задачи о k-медианах и задачи о размещении объектов (посмотреть исходный код)
Версия от 12:21, 17 апреля 2018
, 17 апреля 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 32: | Строка 32: | ||
== Основные результаты == | == Основные результаты == | ||
Основным методом решения задач k-медиан и размещения объектов является класс эвристик локального поиска, выполняющихся посредством поэтапных «локальных улучшений». На каждом этапе t эвристика поддерживает множество центров | Основным методом решения задач 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> называется «разрывом локальности» эвристики. | ||