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

Размещение центров

Голосование: 9, 1

Введение

Рассмотрим несколько задач на графах.

  1. В небольшом городе строится пожарная часть. Каким образом выбрать место для строительства, что бы время, за которое пожарники доедут в самый дальний от части район города, было минимальным?
  2. Где установить сетевой хаб, чтобы длина самого длинного провода была минимальна?
  3. Как создать в городе сеть ресторанов, что бы из любой точки города можно было приехать в один из таких ресторанов менее чем за десять минут? (Ответом на данную задачу будет минимальное число ресторанов и места их расположения)
  4. Как наиболее оптимально разместить 5 служб доставки пиццы на дом, что максимальное время пути курьера до любого дома было минимально.

Заметим, что все эти задачи можно свести к поиску некоторой точки (или точек) в графе, где вершины соответствуют районам города (или компьютерам в сети), а ребра — дороги (или провода). Во всех этих задачах требуется оптимизировать "наихудший вариант", т. е., к примеру, найти такое место для хаба, что бы длина самого длинного провода была минимальна. Такие задачи часто встречаются при размещении аварийных служб, бомбоубежищ, станций метро, автомастерских и т. п. Цель таких задач — разместить некоторый(ые) объект(ы) так, чтобы минимизировать максимальное из расстояний (или время проезда) от этого объекта до какого-то здания (района, компьютера и т. п.). Именно поэтому этот класс задач принято называть минимаксными задачами размещения. Если же в задаче требуется минимизировать максимальную сумму расстояний (или суммарное время) от объекта и обратно, то эта задача относится к другому классу задач — минисуммным задачам размещения.

Договоренности

Договоримся, что будем всегда рассматривать ориентированные сильно связные графы, если не оговорено обратного. Граф G задается двумя множествами: множеством вершин V и множеством ребер E.

Каждому ребру соответствуют некоторое неотрицательное число, которое имеет смысл длины этого ребра (или времени проезда по нему). Расстояние от вершины xi до вершины xj обозначается d(xi,xj) = dij и равняется минимальной из сумм длин ребер всех путей между этими вершинами. Будем считать, что длина ребра обладает аддитивностью. Это означает, что если поделить ребро некоторой точкой, то сумма длин получившихся отрезков равна длине ребра.

Каждой вершине xi сопоставим некоторое положительное число vi, которое имеет смысл важности или приоритета. Тогда взвешенным расстоянием между двумя вершинами xi и xj будем называть число lij = l(xi,xj) := vjd(xi,xj) = vjdij. Заметим, что взвешенное расстояние не симметрично даже в случае неориентированного графа, т. е. lij ≠ lji. Точно так же определяется взвешенный путь между некоторой точкой eij, лежащей на ребре (xi,xj) и вершиной xk: l(xi,xj) :=vkd(eij, xk). Будем говорить, что точка y2 достижима из точки y1 не более чем за λ, если l(y1, y2) ≤ λ. В дальнейшем всегда будем говорить о взвешенном расстоянии, дополнительно это не оговаривая.

Разделения

Рассмотрим некоторый граф G=(V,E). Введем два множества:

Rλo(xi) := {xj | lij ≤ λ, xj ∈ V},
Rλt(xi) := {xj | lji ≤ λ, xj ∈ V}.

Rλo(xi) — это множество всех вершин, расстояние от xi до которых не больше λ, а Rλt(xi) — множество всех вершин, расстояние от которых до xi не больше λ. Очевидно, что существуют такие λ, что эти множества не пусты (конечно, если в графе больше одной вершины).

Для каждой вершины определим два числа:

so(xi) := max(lij), xj ∈ V,
st(xi) := max(lji), xj ∈ V.

so(xi) и st(xi) называют соответственно внешним и внутренним разделением для вершины xi.

Пусть λo — наименьшая λ такая, что для некоторой xi

Rλo(xi) = V,

т. е. длина пути до любой вершины графа не превосходит λo. Тогда so(xi) = λo (напрямую следует из определений Rλo(xi) и so(xi)).

Аналогично, λt — наименьшая λ такая, что для некоторой xi

Rλt(xi) = V,

т. е. длина пути от любой вершины графа до xi не превосходит λt. Тогда st(xi) = λt.

Стоит заметить, что если бы граф не был сильно связан, то хотя бы одно из чисел λo, λt равнялось ∞.

Центр графа

Определения

Вершина x*o такая, что

so(x*o) = min[so(xi)], xiV

называется внешним центром графа G. Аналогично, вершина x*t такая, что

st(x*t) = min[st(xi)], xiV

называется внутренним центром.

Значения so(x*o) и st(x*t) называются соответственно внешним и внутренним радиусами графа G. Обозначаются ρo и ρt.

Можно так же определить внешне-внутренние разделение:

sot(xi) = max{vj [d(xi,xj) + d(xj,xi)]}, xj ∈ V,

и внешне-внутренний центр, как вершину, на которой достигается минимум внешне-внутреннего разделения.

Можно интерпретировать внешний центр как пожарный участок (минимально время на дорогу от участка к месту пожара), внутренний как бомбоубежище (человеку требуется минимальное время на дорогу туда), внешне-внутренний как служба скорой помощи (минимально время на путь туда и обратно).

Алгоритм поиска

Так как поиск центра графа — это задача, которую нужно решить единожды, то трудоемкость алгоритма не должна нас особенно волновать. Важно только, чтобы задача решалась за разумное время.

Приведем алгоритм поиска внешнего центра.

  1. Для начала построим матрицу An×n (n — мощность множества V), где aij=lij. По сути, это матрица кратчайших путей. Для ее построения можно воспользоваться алгоритмом Флойда-Уоршала или Дейкстры.
  2. Тогда внешнее разделение для вершины с номером i — это максимальное значение в i-ой строчке матрицы A. Посчитаем максимум в каждой строчке. Т. о. получим массив длины n, где i-ый элемент — внешнее разделение i-ой вершины.
  3. Найдем наименьший элемент в этом массиве. Это будет наименьшее из внешних разделений. Вершина с таким разделением и есть внешний центр. В том случае, если вершин с таким разделением несколько, то все они — внешние центры.

Алгоритм поиска внутреннего центра отличается лишь на первом шаге: aij=lji.

Абсолютный центр графа

Определения

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

so(y) := max[vid(y,xi)], xi ∈ V, y ∈ G

Используя это расширенное определения разделений, определим абсолютный внешний и внутренний центры. Абсолютный внешний центр — это такая точка y*o ∈ G, у которой внешнее разделение минимально. Аналогично, абсолютный внутренний центр — это такая точка y*t ∈ G, у которой внутреннее разделение минимально.

Абсолютные радиусы определяются как значения разделений соответствующих абсолютных центров. Обозначаются ro и rt.

Алгоритм поиска

Отметим, что приведенный выше алгоритм поиска центра здесь использовать невозможно, т. к. количество "потенциальных абсолютных центров" бесконечно, а следовательно невозможно посчитать разделение каждой такой точки.

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

Имеет смысл рассмотреть два принципиально разных алгоритма.

Метод Хакими

Этот алгоритм позволяет найти точное расположение абсолютного центра и значение его разделения (радиус). Он состоит всего из двух шагов.

  1. Для каждого ребра найти точку с наименьшим разделением.
  2. Из всех этих точек выбрать точку с наименьшим разделением — она и будет абсолютным центром.

Второй шаг алгоритма очевиден. Первый же на порядок сложнее. Он осуществляется следующим образом.

Возьмем ребро eij. Для любой точки y ∈ eij верно следующее

s(y) = max[vkd(y,xk)] = max[vkmin{d(y,xi)+d(xi,xk), d(y,xj)+d(xj,xk)}]

Построим на одном графике 2 зависимости vk{d(y,xi)+d(xi,xk)} и vk{d(y,xj)+d(xj,xk)} от положения точки y на ребре. Нижняя огибающая этих графиков — это график зависимости vkd(y,xk) от положения точки y. Если построить на этом же графике такие зависимости для вcех остальных xk ∈ V, то верхняя огибающая этих графиков будет графиком зависимости s(y) от положения точки y. В общем случае это кусочно-линейная функция. Ее абсолютный минимум (или минимумы) — точка(и) c наименьшим разделением на данном ребре.

Алгоритм Хакими можно значительно оптимизировать. Идея состоит в том, чтобы заранее оценить значение абсолютного радиуса и не рассматривать те ребра, на которых, исходя из этих оценок, абсолютного центра быть не может.

Предположим, что абсолютный центр графа лежит на ребре eij, тогда значение абсолютного радиуса не меньше, чем

pij = max[vkmin{d(xi,xk), d(xj,xk)}], xk ∈ V.

Следовательно,

P = min(pij), eij ∈ E

— обоснованная нижняя оценка для абсолютного радиуса.

Пусть теперь абсолютный центр лежит в середине ребра eij, тогда абсолютный радиус

r = pij + v*kd(xi,xj)/2,

где v*k — вес той вершины, в которой достигается max[vkmin{d(xi,xk), d(xj,xk)}] (т.е. той, которая определяет значение pij). Исходя из этого,

H = min[pij + v*kd(xi,xj)/2]

— обоснованная верхняя оценка для абсолютного радиуса.

Таким образом, всякое ребро eij ∈ E, для которого pij ≥ H, можно не рассматривать. Визуализатор оптимизированного алгоритма Хакими можно посмотреть здесь.

Итерационный алгоритм

Этот алгоритм не дает точное расположение абсолютного центра и значение абсолютного радиуса. Результат его работы — некоторая область, в которой лежит абсолютный центр и, соответственно, примерное значение абсолютного радиуса.

Его суть состоит в следующем.

  1. Выбираем некоторое δ > 0. Пусть λ изначально равна δ.
  2. Найдем пересечение всех таких областей
    Qλ(xi) = {y ∈ G: l(y,xi) ≤ λ}.
  3. Если это пересечение непустое, то центр находится в нем. Если же оно пустое, то увеличим λ на δ и вернемся к шагу 2.

Заметим, что размер полученной области зависит от δ. Другими словами, чем меньше мы возьмем δ, тем будет больше точность полученного результата. Если все же нужно точное значение, то можно совместить этот алгоритм с методом Хакими: сначала найти область, в которой лежит центр, а потом рассмотреть только те ребра, части которых лежат в этой области.

Кратные центры (p-центры)

Определения

В том случае, когда нам нужно разместить несколько объектов (как в задачи номер 3, приведенной в начале статьи), то можно рассматривать некоторое обобщение центра графа: не одну точку, а некоторое множество Xp состоящее из p точек, называемое кратным центром (p-центром). Тогда

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

Исходя из этого, дадим следующие определения: внешнее разделение множества вершин Xp

so(Xp) = min[d(Xp,xi)], xi ∈ V,

аналогично, внутреннее разделение множества вершин Xp

st(Xp) = min[d(xi,Xp)], xiV.

Множество вершин X*po такое, что

so(X*po) = min[so(Xp)], Xp ⊆ V.

называется внешним p-центром. Аналогично определяется внутренний p-центр.

Алгоритм поиска

Отметим, что здесь можно было бы воспользоваться алгоритмом, который перебирает все возможные множества из p вершин и сравнивает их. Но такой алгоритм потребовал бы от нас p(n-p)Cnp операций, что при n=100 и p=5 примерно 3,6*1020. Такое решение потребует очень много времени и больших вычислительных мощностей. Поэтому здесь лучше использовать итерационный алгоритм. Он будет приведен далее для абсолютных p-центров.

Абсолютные p-центры

Определения

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

Тогда

d(Xp,xi) = min[d(yj,xi)], yj ∈ Xp
d(xi,Xp) = min[d(xi,yj)], yj ∈ Xp

Отсюда, внешнее разделение множества точек Xp

so(Xp) = min[d(Xp,xi)], xiV,

аналогично, внутреннее разделение множества точек Xp

st(Xp) = min[d(xi,Xp)], xi ∈ V.

Множество точек X*po такое, что

so(X*po) = min[so(Xp)], Xp ⊆ G.

называется абсолютным внешним p-центром. Аналогично определяется абсолютным внутренний p-центр.

Алгоритм поиска

Решение задачи о поиске абсолютного p-центра намного сложнее, чем задача о поиске абсолютного центра. Метод Хакими, предложенный выше, невозможно обобщить на случай абсолютных p-центров. Существует эвристический метод Сингера, дающий точное решение, но мы остановимся на итерационном алгоритме.

Итерационный алгоритм

Рассмотрим итерационный алгоритм поиска абсолютных p-центров. Как и ранее будем рассматривать неориентированный граф. Идея этого алгоритма состоит в построении специальных областей Φλ(Vk), где Vk ∈ V — множество из k вершин, таких, что любая вершина vi ∈ Vk достижима из любой точки этой области путем, длина которого не привосходит λ, а если vi ∉ Vk, то ни для какой точки Φλ(Vk) это не выполняется (другими словами области не пересекаются).

Любая точка графа попадает в некоторую область Φλ(Ø) = {y ∈ G: ∀X ⊆ V y ∉Φλ(X)} — область, из которой ни одна вершина не доступна путем не превосходящим λ.

Для того, что бы построить эти области, сначала строят множества Qλ(xi) = {y ∈ G: l(y,xi) ≤ λ}, т. е. множество всех точек, из которых xi достижима не более чем за λ. Тогда Φλ(Vk) можно выразить как через Qλ(xi) следующим образом

Φλ(Vk) = (∩Qλ(xi)) \ (∪Qλ(xj)),

где xi ∈ Vk, а xj ∉ Vk.

  1. Выберем некоторое δ > 0. Положим λ = δ.
  2. Построим множества Qλ(xi) для всех xi.
  3. При помощи Qλ(xi) построим области Φλ(Vk).
  4. Построим двудольный граф G′ = (V′ ∪ V, E′), где V′ — множество вершин, каждая из которых соответствует некоторой области Φλ(Vk), а E′ — множество дуг, такое, что дуга между вершиной-областью и вершиной xi существует тогда и только тогда, когда xi может быть достигнута из этой области.
  5. Найти наименьшее доминирующее множество графа G′.
  6. Если число областей в этом множестве больше, чем p, то увеличить λ на δ и вернуться к шагу 2; в противном случае остановиться. Области этого множества образуют абсолютный p-центр графа G, а λ является абсолютным p-радиусом.

Погрешность в определении центра и соответствующей λ линейно зависит от δ. В процессе работы этого алгоритма будут также найдены абсолютные (n-1)-, (n-2)- и т. д. центры.

Определим множества Qλ(xi) как множества вершин, из которых xi достижима не более чем за λ, а области Φλ(Vk) как множество вершин такое, что любая вершина из Vk достигается из любой вершины Φλ(Vk) не более чем за λ, и нет такой вершины xj ∈Φλ(Vk), из которой достижима менее чем за λ вершина не принадлежащая Vk. Тогда результатом работы данного алгоритма будет обычный (не абсолютный) p-центр.

Заметим, что подобным алгоритмом можно решать сходную задачу: по заданному λ найти абсолютный кратный центр с наименьшим p.

О некоторых вычислительных аспектах данного алгоритма, которые могут помочь в его программировании, можно прочитать в [1, глава 5, § 8.2].

Литература

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

Александр Смаль


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