4511
правок
Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
Локальный поиск для задачи о k-медианах и задачи о размещении объектов (посмотреть исходный код)
Версия от 10:59, 27 апреля 2018
, 27 апреля 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 47: | Строка 47: | ||
'''Задача о k-медианах''' | '''Задача о k-медианах''' | ||
Первую эвристику локального поиска с доказуемой гарантией эффективности предложили Арья и др. [1]. Это естественная эвристика с p заменами: пусть имеется текущее множество центров <math>C_t \;</math> размера k; множество <math>\mathcal{E}_{t+1}</math> определяется следующим образом: | Первую эвристику локального поиска с доказуемой гарантией эффективности предложили Арья и др. [1]. Это «''естественная эвристика с p заменами''»: пусть имеется текущее множество центров <math>C_t \;</math> размера k; множество <math>\mathcal{E}_{t+1}</math> определяется следующим образом: | ||
<math>\mathcal{E}_{t+1} = \{ (C_t \backslash \mathcal{A}) \cup \mathcal{B}</math>, где <math>\mathcal{A} \subseteq C_t, \mathcal{B} \subseteq \mathcal{F} \backslash C_t, |\mathcal{A}| = |\mathcal{B}| \le p \}</math>. | <math>\mathcal{E}_{t+1} = \{ (C_t \backslash \mathcal{A}) \cup \mathcal{B}</math>, где <math>\mathcal{A} \subseteq C_t, \mathcal{B} \subseteq \mathcal{F} \backslash C_t, |\mathcal{A}| = |\mathcal{B}| \le p \}</math>. | ||
| Строка 68: | Строка 68: | ||
Эвристика «''добавление, удаление и замена''», предложенная Кюном и Хамбургером [10], добавляет центр в <math>C_t \;</math>, исключает центр из <math>C_t \;</math> либо заменяет центр из <math>C_t \;</math> центром из <math>\mathcal{F} \backslash C_t</math>. Начальное множество <math>C_0 \;</math> также выбирается произвольно. | Эвристика «''добавление, удаление и замена''», предложенная Кюном и Хамбургером [10], добавляет центр в <math>C_t \;</math>, исключает центр из <math>C_t \;</math> либо заменяет центр из <math>C_t \;</math> центром из <math>\mathcal{F} \backslash C_t</math>. Начальное множество <math>C_0 \;</math> также выбирается произвольно. | ||
<math>\mathcal{E}_{t + 1} = \{(C_t \backslash \mathcal{A}) \cup \mathcal{B},</math> где <math>\mathcal{A} \subseteq C_t, \mathcal{B} \subseteq \mathcal{F} \backslash C_t, |\mathcal{A}| = 0, |\mathcal{B}| = 1,</math> либо <math>|\mathcal{A}| = 1, |\mathcal{B}| = 0,</math> либо <math>|\mathcal{A}| = 0, |\mathcal{B}| = 1 \}.</math> | |||