Первая страница / Теория / Графы. Задачи размещения /

Размещение медиан

Голосование: 12, 2

Введение

Рассмотрим некоторую задачу на графе

Пускай необходимо выбрать место для размещения телефонного коммутатора, электроподстанции, баз снабжения в сети дорог или отдела сортировки в почтовой связи. Во всех этих задачах о размещении пункта обслуживания требуется так расположить этот пункт, чтобы сумма кратчайших расстояний от этого пункта до вершин графа была минимально возможной. Оптимальное в указанном смысле место расположения пункта называется медианой графа. Под вершинами графа понимается, например, расположение телефонов в задаче о размещении телефонного комутатора (надеюсь, что в остальных примерах читателю интуитивно понятно появление графа). Исходя из природы целевой функции, такие задачи называются минисуммными задачами размещения.

В данной работе мы будем рассматривать минисуммные задачи размещения. В частности рассмотрим задачу о нахождении p-медианы данного графа G; это задача о размещении заданного числа (скажем, p) пунктов обслуживания, при которых сумма кратчайших расстояний от вершин графа G до ближайших пунктов принимает минимально возможное значение.

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

Задача о p-медиане может быть несколько обобщена, если каждой вершине xj сопоставить некоторый вес vj (представляющий, например, ее размер и важность); тогда целевой функцией, подлежащей минимизации, станет сумма «взвешенных» расстояний.

Пусть дан граф G = (X, Γ). Для каждой вершины xiX (здесь и далее суммирование ведется по всем xiX)

σo(xi) = ∑ vj d(xi, xj) — внешнее передаточное число,
σt(xi) = ∑ vj d(xj, xi) — внутреннее передаточное число,

где d(xi, xj) — кратчайшее расстояние от вершины xi до вершины xj.

Вершина xo*, для которой σo(xo* ) = min [ σo(xi) ], называется внешней медианой графа G, а вершина xt*, для которой σt(xt*) = min [ σt(xi) ], называется внутренней медианой графа G.

Выбор места для склада

Вернемся к нашей задаче о снабжении ряда потребителей товарами, поступающими с одного склада. Потребителей можно объединить в группы таким образом, чтобы каждую группу обслуживало целое число грузовиков. Группы потребителей можно представить в виде вершин графа, а сеть — его дугами. На практике каждой группе потребителей присваивается вес vj, представляющий ее «важность» (например, vj может быть числом, пропорциональным годовому потреблению).

В этом случае задача сводится к нахождению места для такого склада, чтобы расстояние, проходимое транспортом, было минимальным. Таким образом, возвращаясь к обозначениям, введенным выше, необходимо найти такую вершину xo,t*, чтобы сумма внешних и внутренних передаточных чисел была наименьшей. Тогда вершина xo,t* может быть названа внешне-внутренней медианой. Далее будет показано, что точка xo,t* является оптимальной, т. е. для любой другой точки графа (вершины или произвольной точки дуги) общее расстояние, покрываемое транспортом, при условии, что в этой точке будет располагаться склад, будет не меньше, чем для вершины xo,t*.

P-медиана графа

Обобщим понятие медианы, определив p-медиану.

Пусть Xp — подмножество множества вершин X графа G = (X, Γ), и положим, что Xp содержит p вершин. Переопределим следующие обозначения:

d(Xp, xj) = min [ d(xi, xj) ]

и

d(xj, Xp) = min [ d(xj, xi) ],

где минимум ищется по всем xiX.

Если xi′ — вершина из Xp, на которой достигается минимум в предыдущих формулах, то говорят, что вершина xj прикреплена xi′. Передаточные же числа множества вершин Xp определяются аналогично передаточным числам одиночной вершины:

σo(xi) = ∑ vj d(Xp, xj) — внешнее передаточное число,
σt(xi) = ∑ vj d(xj, Xp) — внутреннее передаточное число.

Множество же Xo*, для которого σo(Xo*) = min [ σo(xi) ] (минимум ищется по всем XpX), называется внешней p-медианой графа G, аналогично определяется внутренняя p-медиана.

Понятно, что нахождение p-медианы используя непосредственно вышеуказанные формулы нецелесообразно с вычислительной точки зрения. Алгоритм построения p-медиан будет показан позже.

Абсолютные p-медианы

Для упрощения задачи будем далее рассматривать неориентированный граф G. Т. о. индексы t и o будут отсутствовать, т. к. внешние и внутренние передаточные числа будут совпадать. Точку графа (вершина или точка дуги), для которой передаточное число будет принимать наименьшее значение, будем называть абсолютной медианой графа G. Вернемся к вопросу о существовании точки, лучшей в смысле поставленной задачи, чем p-медиана графа. Для начала ограничимся случаем 1-медианы.

Теорема 1

Какова бы не была точка y графа G = (X, Γ), в ней найдется по крайней мере одна вершина x, для которой σ(x)≤σ(y).

Доказательство. Пусть y — точка ребра (xa, xb), расположенная на расстоянии ξ от xa. Тогда

d(y, xj) = min [ ξ + d(xa, xj), cab − ξ + d(xb, xj) ],

где cab — длина ребра (xa, xb).

Пусть Xa — множество тех вершин xj, для которых первый член предыдущего равенства не больше второго, а Xb — множество вершин, для которых второй член меньше первого. Тогда можно написать:

σ(y) = ∑ vj d(y, xj) = ∑ vj [ ξ + d(xa, xj) ] + ∑ vj [ cab − ξ + d(xb, xj) ],  (1)

где первая сумма берется по всем xjXa, а вторая по всем xiXb.

Поскольку из неравенства треугольника следует, что

d(xa, xj) ≤ cab + d(xb, xj),

то, заменяя cab + d(xb, xj) на d(xa, xj) в (1) имеем:

σ(y) ≥ ∑ vj [ ξ + d(xa, xj) ] + ∑ vj [ d(xa, xj) − ξ ]  (2)

И так как XaXb = X, то, сделав перегруппировку в (2), имеем:

σ(y) ≥ ∑ vj d(xa, xj) + ξ [∑ vj − ∑ vj],  (3)

где первая сумма берется по всем xjX, вторая xjXa и третья xjXb.

И т. к. для любого ребра (xa, xb) мы вправе сами решать, какую вершину называть xa и какую xb, то всегда можем добиться того, чтобы второе слагаемое из неравенства (3) было положительным, из чего и будет вытекать требуемое:

σ(y) ≥ σ(xa).

Данная теорема просто обобщается на случай p-медиан:

Теорема 2

Каково бы ни было множество Yp, состоящее из p точек графа G = (X, Γ), т. е. из p точек ребер и вершин, найдется по крайней мере одно подмножество XpX, содержащее p вершин, для которого σ(Xp) ≤ σ(Yp).

Из этих двух теорем следует, что понятие абсолютной медианы не представляет особого интереса при решении поставленной нами задачи.

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

Тейц и Барт предложили эвристический метод для нахождения p-медианы. Метод состоит в следующем: случайным образом выбираются p вершин, они образуют начальное множество S, аппроксимирующее p-медианное множество Xp*. Затем выясняется, может ли некоторая вершина xjX \ S заменить вершину xiS (как медианная вершина), для чего строят новое множество S* = (S ∪ {xj}) \ {xi} и сравнивают передаточные числа σ(S*) и σ(S). Если σ(S*) < σ(S), то S заменяют на S*, которое лучше аппроксимирует p-медианное множество Xp*. Затем аналогично исследуется множество S* и т. д., пока не будет построено множество S^, которое нельзя будет изменить по вышеуказанному принципу.

Опишем данный алгоритм.

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

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

Δij = σ(S) − σ((S ∪ {xj}) \ {xi}).

Шаг 3. Найти Δij = max [ Δij ] по всем xiS.

  1. Если Δi'j ≤ 0, то назвать вершину xj «опробованной» и перейти к шагу 2.
  2. Если Δi'j ≥ 0, то S ← (S ∪ {xj}) \ {xi}, назвать вершину xj «опробованной» и перейти к шагу 2.

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

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

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

Граф

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

Более подробно о данной задаче можно почитать в [1, глава  6]. В книге [2] можно посмотреть немного другой теоретический подход к данной проблеме.

Литература

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

Визуализаторы

  1. Зарубин А. Р-медианы (2002)

Александр Хвастунов


Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий