Русская Википедия:Приближённый алгоритм поиска p-медиан
Эвристический метод для нахождения p-медианы состоит в следующем: случайным образом выбираются <math> p </math> вершин, они образуют начальное множество <math> S </math>, аппроксимирующее p-медианное множество <math> X_p^* </math>. Затем выясняется, может ли некоторая вершина <math> x_j \in X \setminus S </math> заменить вершину <math> x_i \in S </math> (как медианная вершина), для чего строят новое множество <math> S^* = (S \cup {x_j}) \setminus {x_i} </math> и сравнивают передаточные числа <math> \sigma(S^*)</math> и <math> \sigma(S)</math>. Если <math> \sigma(S^*) < \sigma(S)</math>, то <math> S </math> заменяют на <math> S^* </math>, которое лучше аппроксимирует p-медианное множество <math> X_p^* </math>. Затем аналогично исследуется множество <math> S^* </math> и т. д., пока не будет построено множество <math>S</math>', которое нельзя будет изменить по вышеуказанному принципу.
Алгоритм
Шаг 1. Выбрать некоторое множество <math>S</math> из p вершин в качестве начального приближения к p-медиане. И назовём все вершины <math> x_i \notin S </math> «неопробованными».
Шаг 2. Взять произвольную «неопробованную» вершину и для каждой вершины <math> x_i \in S </math> вычислить «приращение» Δij, соответствующие замене вершины <math> x_i </math> вершиной <math> x_j </math>, то есть вычислить <math> \Delta_{ij} = \sigma(S) - \sigma ((S \cup {x_j}) \setminus {x_i}) </math>.
Шаг 3. Найти <math> \Delta _{i^{1}j} = max [ \Delta_{ij} ]</math> по всем <math>x_i \in S </math>.
а) Если <math>\Delta_{i^{1}j} \le 0 </math>, то назвать вершину <math>x_j </math> «опробованной» и перейти к шагу 2.
б) Если <math>\Delta_{i^{i}j} \ge 0</math>, то <math> S \gets (S \cup {x_j}) \setminus {x_i} </math>, назвать вершину <math>x_j</math> «опробованной» и перейти к шагу 2.
Шаг 4. Повторять шаги 2 и 3 до тех пор, пока все вершины из <math>X \setminus S</math> не будут опробованы. Эта процедура оформляется как цикл. Если при выполнении последнего цикла совсем не будет замещений вершин на шаге 3(a), то перейти к шагу 5. В противном случае, то есть если осуществлено некоторое замещение, назвать все вершины «неопробованными» и вернуться к шагу 2.
Шаг 5. Стоп. Текущее множество <math>S</math> является подходящей аппроксимацией p-медианного множества <math>X_p^*</math>.
Пример
Легко заметить, что приведённый выше алгоритм не во всех случаях даёт оптимальный ответ. Рассмотрим пример (числа, стоящие около рёбер, равны соответствующим рёберным стоимостям, все вершины одинакового единичного веса):
Если искать 2-медиану и в качестве начального множества S взять {x3, x6} с передаточным числом <math>\sigma(S) = 8</math>, то никакое замещение только одной вершины не приводит к множеству с меньшим передаточным числом. Однако множество {x3, x6} не является 2-медианой данного графа, так как существуют два 2-медианных множества с передаточным числом 7: {x1, x4} и {x2, x5}.
Литература
Ссылки
