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

Алгоритм

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

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

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

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

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

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

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

Пример

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

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

Литература

• Кристофидес Н. Теория графов. Алгоритмический подход. — М. : Мир, 1978.
• Э. Майника. Алгоритмы оптимизации на сетях и графах. — М. : Мир, 1981. — 324 с.

Ссылки

• Медиана графа