Приближённый алгоритм поиска p-медиан

Эвристический метод для нахождения p-медианы состоит в следующем: случайным образом выбираются $p$ вершин, они образуют начальное множество $S$, аппроксимирующее p-медианное множество $X_p^{*}$. Затем выясняется, может ли некоторая вершина $x_j\in X\setminus S$ заменить вершину $x_i\in S$ (как медианная вершина), для чего строят новое множество $S^{*}=(S\cup x_j)\setminus x_i$ и сравнивают передаточные числа $\sigma (S^{*})$ и $\sigma (S)$. Если $\sigma (S^{*})<\sigma (S)$, то $S$ заменяют на $S^{*}$, которое лучше аппроксимирует p-медианное множество $X_p^{*}$. Затем аналогично исследуется множество $S^{*}$ и т. д., пока не будет построено множество $S$', которое нельзя будет изменить по вышеуказанному принципу.

Алгоритм

Шаг 1. Выбрать некоторое множество $S$ из p вершин в качестве начального приближения к p-медиане. И назовём все вершины $x_i\notin S$ «неопробованными».

Шаг 2. Взять произвольную «неопробованную» вершину и для каждой вершины $x_i\in S$ вычислить «приращение» Δij, соответствующие замене вершины $x_i$ вершиной $x_j$, то есть вычислить ${\mathrm{\Delta }}_{ij}=\sigma (S)-\sigma ((S\cup x_j)\setminus x_i)$.

Шаг 3. Найти ${\mathrm{\Delta }}_{i^{1}j}=max[{\mathrm{\Delta }}_{ij}]$ по всем $x_i\in S$.

а) Если ${\mathrm{\Delta }}_{i^{1}j}\le 0$, то назвать вершину $x_j$ «опробованной» и перейти к шагу 2.

б) Если ${\mathrm{\Delta }}_{i^{i}j}\ge 0$, то $S\leftarrow (S\cup x_j)\setminus x_i$, назвать вершину $x_j$ «опробованной» и перейти к шагу 2.

Шаг 4. Повторять шаги 2 и 3 до тех пор, пока все вершины из $X\setminus S$ не будут опробованы. Эта процедура оформляется как цикл. Если при выполнении последнего цикла совсем не будет замещений вершин на шаге 3(a), то перейти к шагу 5. В противном случае, то есть если осуществлено некоторое замещение, назвать все вершины «неопробованными» и вернуться к шагу 2.

Шаг 5. Стоп. Текущее множество $S$ является подходящей аппроксимацией p-медианного множества $X_p^{*}$.

Пример

Легко заметить, что приведённый выше алгоритм не во всех случаях даёт оптимальный ответ. Рассмотрим пример (числа, стоящие около рёбер, равны соответствующим рёберным стоимостям, все вершины одинакового единичного веса):

Если искать 2-медиану и в качестве начального множества S взять {x3, x6} с передаточным числом $\sigma (S)=8$, то никакое замещение только одной вершины не приводит к множеству с меньшим передаточным числом. Однако множество {x3, x6} не является 2-медианой данного графа, так как существуют два 2-медианных множества с передаточным числом 7: {x1, x4} и {x2, x5}.

Литература

• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Медиана графа
• Визуализатор
• Размещение медиан