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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Эвристический метод для нахождения p-медианы состоит в следующем: случайным образом выбираются вершин, они образуют начальное множество , аппроксимирующее p-медианное множество . Затем выясняется, может ли некоторая вершина заменить вершину (как медианная вершина), для чего строят новое множество и сравнивают передаточные числа и . Если , то заменяют на , которое лучше аппроксимирует p-медианное множество . Затем аналогично исследуется множество и т. д., пока не будет построено множество ', которое нельзя будет изменить по вышеуказанному принципу.

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

Шаг 2. Взять произвольную «неопробованную» вершину и для каждой вершины вычислить «приращение» Δij, соответствующие замене вершины вершиной , то есть вычислить .

Шаг 3. Найти по всем .

а) Если , то назвать вершину «опробованной» и перейти к шагу 2.

б) Если , то , назвать вершину «опробованной» и перейти к шагу 2.

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

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

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

Числа, стоящие около рёбер, равны соответствующим рёберным стоимостям, все вершины одинакового единичного веса

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

Литература

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