8. Алгоритм нахождения абсолютных p-центров

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

Пусть множество всех точек у на графе из которых вершина достижима в пределах расстояния при заданном значении Множества определяются с помощью соотношения (5.14) из разд. 5.2. Эти множества весьма легко можно построить, применяя алгоритм, подобный алгоритму Дейкстра [4] (позволяющему находить кратчайшие пути в графе, см. гл. 8).

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

Рис. 5.7. Области, образованные при

Область 1. Точка а (единственная точка, из которой в пределах расстояния, равного 3, достижимы вершины

Область 2. Отрезок ребра от с- (Из любой точки этой области достижимы вершины и

Область 3. Отрезки и соответствующих ребер (из точек этой области достижима только вершина

Область 4. Отрезки и соответствующих ребер (из каждой точки этой области достижима только

Область 5. Отрезки и (из точек этой области достижима только

Область 6. Отрезок ребра от до (из точек этой области не достижима никакая вершина).

В общем случае все области можно следующим образом построить из достижимых множеств

Области, из которых не достижимы никакие вершины, описываются соотношением

где второй член исключает все области графа из которых можно достигнуть хотя бы одну вершину

Области, из которых можно достигнуть ровно вершин (для любого определяются

следующим выражением:

где второй член исключает такие области, из которых достижимы вершины и еще хотя бы одна из оставшихся вершин графа.

С первого взгляда кажется, что число областей из соотношения (5.23) может быть очень велико. Однако на практике пересечения множеств, входящие в выражение (5.23), становятся пустыми уже для небольших значений Это приводит к вполне обозримому множеству областей. Эффективные (с вычислительной точки зрения) методы построения областей, а также дальнейшего уменьшения числа необходимых областей приводятся в настоящем разделе несколько позже.

8.1. Описание алгоритма

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

Шаг 1. Положить

Шаг 2. Увеличить на небольшую величину

Шаг 3. Построить множества для всех и найти области

Шаг 4. Образовать двудольный граф , где X — множество вершин, каждая из которых соответствует некоторой области множество дуг, такое, что дуга между областью-вершиной и вершиной существует тогда и только тогда, когда может быть достигнута из этой области.

Шаг 5. Найти наименьшее доминирующее множество графа (см. гл. 3).

Шаг 6. Если число областей в приведенном выше множестве больше, чем то вернуться к шагу 2; в противном случае остановиться. Области этого множества образуют абсолютный -центр исходного графа

Следует отметить (см. гл. 3), что число областей в наименьшем доминирующем множестве представляет (по определению) наименьшее число точек в из которых достигаются все вершины графа в пределах расстояния проникновения используемого в данной итерации. Надо также отметить, что в процессе построения абсолютного -центра по указанному выше алгоритму можно заодно получить абсолютные центры. Таким образом, если в конце некоторой итерации (продолжающейся с шага 2 до шага 6) число областей в наименьшем доминирующем

множестве уменьшается с некоторого уровня I до то области этого нового множества образуют абсолютный -центр, а величина взятая для этой итерации, будет «абсолютным -радиусом», т. е. она является «критическим» значением при меньших значениях не существуют -центры, из которых в пределах взвешенного расстояния достижима каждая вершина графа.

Если нужно найти такое наименьшее значение что каждая вершина достижима из некоторого центра в пределах заданного критического расстояния (задача из разд. 7), то шаги с 3 по в приведенном выше алгоритме следует выполнять при равном этому «критическому» значению. Соответствующее число областей в наименьшем доминирующем множестве является тогда требуемым значением для и области этого множества образуют искомый -центр.

8.2. Вычислительные аспекты

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

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

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

Представление области бинарным вектором не содержит никакой информации о месте ее расположения на графе. Однако такое представление выгодно с вычислительной точки зрения: оно не

предъявляет больших требований к памяти машины и позволяет уменьшить время вычисления, особенно при выполнении шага

5 алгоритма. Если абсолютный -центр описан «на языке строгих пересечений», то дальнейшая процедура осуществляется чрезвычайно просто: надо лишь выяснить, какие участки ребер соответствуют этим строгим пересечениям.

На шаге 4 алгоритма надо строить двудольный граф , у которого вершины из X представляют области Это может привести к графу больших размеров, что сильно увеличит время вычисления на шаге 5. Однако с помощью приводимой ниже теоремы удается уменьшить размеры графа исключаются те области, которые не влияют на получаемое оптимальное решение (но если существует больше одного оптимального решения, то при такой процедуре некоторые из них можно потерять). Другие пути, позволяющие достичь определенных упрощений, описаны в разд. 4.2 гл. 3.

Теорема 1. При заданной величине для получения некоторого минимального доминирующего множества графа можно предварительно исключить из множества все вершины, соответствующие тем над которыми доминируют другие в Мы говорим, что доминирует над если где означает булевское произведение.

Доказательство этой теоремы очевидно.

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

8.3. Пример

Рассмотрим граф изображенный на рис. 5.8. Число, стоящее около любого ребра, задает его длину; вес каждой вершины графа равен единице. Требуется найти абсолютный -центр с минимально возможной величиной параметра и такой, чтобы каждая вершина графа отстояла хотя бы от одного из этих центров на расстоянии, не превосходящем 3,5 единиц.

Для на рис. 5.9 показаны метки, определяющие множества Они расставлялись сразу же в процессе последовательного «прохождения» ребер. Числа в кружках, стоящие около произвольной метки, указывают «номера» вершин, которым эта метка ооответствует. Так, кружок на ребре (2,3) означает, что

Рис. 5.8. Граф из примера 8.3. Номера вершин подчеркнуты.

Все другие числа являются длинами ребер.

только отмеченная точка достижима из вершин 1 и 3 в пределах расстояния 3,5. На рис. 5.9 точками около ребер показано достижимое множество соответствующее вершине 5. Всего в данном примере существует 33 участка ребер, включая пустой участок (из которого ни одна вершина не может достигаться в пределах расстояния 3,5 единиц). Пустой участок расположен между метками 4 и 5 на ребре (4,5). Некоторые из этих 33 участков имеют

Рис. 5.9. Метки для достижимых множеств. Множество отмечено точками.

одинаковые существует всего 18 областей со следующими

Так, например, участок между метками 1 и 6 на ребре (1,5) принадлежит области с равным 100011, поскольку лишь из точек графа, лежащих между этими двумя метками, можно достигнуть вершины 1, 5 и 6 (и никакие другие) в пределах расстояния

После исключения тех которые доминируются другими остается только 7 областей (с номерами от 12 до 18).

Рис. 5.10. Граф из примера 8.3. Области в наименьшем доминирующем множестве.

Граф после выполнения шага 4 алгоритма выглядит так, как показано на рис. 5.10. Для нахождения наименьшего доминирующего множества этого графа можно воспользоваться алгоритмом, описанным в гл. 3 и предназначенным для решения задачи о наименьшем покрытии. Однако в нашем (простом) примере наименьшее множество легко строится с помощью прямого

последовательного перебора; оно «порождается» с номерами 16 и 18 в приведенном выше списке. Область, соответствующая с номером 16, состоит из одной точки, расположенной на ребре (2,3) в том месте, где находится кружок На рис. 5.9 эта точка обозначена буквой А. Область, соответствующая с номером 18, представляет собой участок ребра (1,5) между метками 6 и 1; на рис. 5.9 она обозначена буквой В.

Таким образом, при требуется два центра; один расположен в точке А, а другой — в любой точке области В. Поскольку область А является точкой, то два указанных центра образуют также абсолютный -центр и является минимально возможным критическим расстоянием для существования -центра. Поэтому при область А исчезнет совсем, и тогда уже нужно строить -центр.

8.4. Результаты вычислений

Алгоритм построения абсолютного -центра был опробован на ЭВМ CDC 6600. Каждый бинарный вектор, задающий хранится в одном слове, так что можно использовать булевские функции для более удобного выполнения теоретико-множественных операций. Поскольку длина слова в вычислительной машине равна 60 битам, то граф, содержащий не более 60 вершин, можно было непосредственно задавать в машинном коде.

В некоторых задачах, в частности, когда число областей в искомом абсолютном -центре (т. е. число велико, шаг 5 алгоритма, описанного в разд. 8.1, требует значительную часть всего времени, затрачиваемого на решение задачи. В табл. 5.1 время, необходимое для выполнения этого шага, приведено отдельно от полного времени решения задачи. В этой таблице представлены времена вычисления (в секундах) и числа итераций, требуемые при построении абсолютных 1-, 2-, 3-, 4- и -центров для некоторых графов. Здесь мы под числом итераций понимаем число повторений шагов алгоритма с 3 по 6 (для различных значений всех тех повторений, которые необходимо осуществить для получения абсолютного -центра с заданной точностью. Графы, которые были использованы при составлении табл. 5.1, выбирались случайным образом и являются связными и неориентированными. Требуемая точность во всех случаях принималась равной 1% от средней длины ребер рассматриваемого графа.

Как видно из табл. 5.1, алгоритм, приведенный в разд. 8.1., можно весьма эффективно использовать при нахождении абсолютных -центров достаточно больших графов.

(см. скан)

8.5. Применение общего алгоритма для поиска p-центров

Алгоритм из разд. 8.1 можно, очевидно, использовать при решении более узкой задачи, приведенной в разд. 6, т. е. при нахождении -центра. Для этого надо только изменить шаг 6 настоящего алгоритма (см. разд. 8.1) таким образом, чтобы «контролировалось» не число областей в наименьшем доминирующем множестве, найденном на шаге 5, а число вершин графа содержащихся в этих областях. Если полученное число вершин больше то нужно возвратиться к шагу 2. В противном случае алгоритм заканчивает работу, и -центром графа будет множество вершин, содержащихся во всех тех областях, которые образуют доминирующее множество.

Поскольку в этом случае необходимы только вершины, содержащиеся в областях, задаваемых соотношениями (5.22) и (5.23), то алгоритм из разд. 8.1 можно без изменений применять для нахождения -центров, если области на шаге 3 строить с помощью соотношений (5.22) и (5.23), используя вместо множеств множества Более того, если все расстояний в матрице расстояний с самого начала расположить в строку в порядке неубывания то на шаге 2 алгоритма значения для параметра должны выбираться лишь из этой строки, и их не надо увеличивать на произвольно малую величину в каждой итерации. Поиск начинается с а затем продолжается при в соответствии с указанным выше упорядочением. Следует заметить, что здесь, очевидно, было бы весьма кстати бинарное представление семейства

9. Задачи

(см. скан)

(см. скан)

(см. скан)

10. Список литературы

(см. скан)