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