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

Перейти к навигации Перейти к поиску
Строка 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> также выбирается произвольно.


Et+1 = f(Ct nA) [ B; где A jAj = 0; jBj = 1 или jAj = 1; jBj = 0; или jAj = 1; jBj = 1g
<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>




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