4430
правок
Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями
Материал из WEGA
Локальный поиск для задачи о k-медианах и задачи о размещении объектов (посмотреть исходный код)
Версия от 12:15, 17 апреля 2018
, 17 апреля 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
Задача о размещении объектов позволяет эффективно избавиться от жесткой границы k на количество центров в методе k-медиан, заменяя его компонентом стоимости центров | Задача о размещении объектов позволяет эффективно избавиться от жесткой границы k на количество центров в методе k-медиан, заменяя его компонентом стоимости центров <math>\sum_{i \in C} r_i</math> в целевой функции и тем самым превращая задачу в лагранжеву релаксацию метода k-медиан. Заметим, что стоимость центров в данном случае может быть неоднородной. | ||
Результаты аппроксимации задачи о k-медианах и задачи о размещении объектов можно распространить на взвешенный случай, В котором каждому элементу j | Результаты аппроксимации задачи о k-медианах и задачи о размещении объектов можно распространить на взвешенный случай, В котором каждому элементу <math>j \in \mathcal{D}</math> разрешается иметь неотрицательный вес <math>w_j \;</math>. В формулировке целевой функции <math>f(C) \;</math> компонент <math>\sum_{j \in \mathcal{D}} d(j, \sigma(j))</math> заменяется на <math>\sum_{j \in \mathcal{D}} wJ \cdot d(j, \sigma(j))</math>. Взвешенный случай особенно релевантен для задачи о размещении объектов, в которой веса элементов обозначают спрос пользователей на ресурс, а центры – местоположение ресурса. Далее термины «элементы» и пользователи» будут в равной степени использоваться для обозначения членов множества <math>\mathcal{D}</math>. | ||
== Основные результаты == | == Основные результаты == | ||
