Алгоритмы поиска остова во взвешенном графе: различия между версиями

Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 37: Строка 37:


Чтобы удовлетворять ограничениям 3-остова, вершина должна внести в остов вклад в размере в среднем <math>\sqrt{n}</math> дуг. Таким образом, вершины степени <math>O(\sqrt{n})</math> обработать легко, поскольку все их дуги могут быть выбраны для остова. Для вершин более высокой степени применяется схема кластеризации (группировки), основанная на доминирующих множествах.
Чтобы удовлетворять ограничениям 3-остова, вершина должна внести в остов вклад в размере в среднем <math>\sqrt{n}</math> дуг. Таким образом, вершины степени <math>O(\sqrt{n})</math> обработать легко, поскольку все их дуги могут быть выбраны для остова. Для вершин более высокой степени применяется схема кластеризации (группировки), основанная на доминирующих множествах.
Вначале имеется множество дуг E’, инициализированное равным E, и пустой остов ES. Алгоритм просматривает дуги E’, переносит некоторые из них в остов ES и отбрасывает остальные. Это происходит в два этапа.
Вначале имеется множество дуг E’, инициализированное равным E, и пустой остов E<math>_{S}</math>. Алгоритм просматривает дуги E’, переносит некоторые из них в остов E<math>_{S}</math> и отбрасывает остальные. Это происходит в два этапа.


1. Формирование кластеров:
1. Формирование кластеров:
Выборка R  V выполняется посредством независимого выбора каждой вершины с вероятностью <math>\frac{1}{\sqrt{n}}</math>. Кластеры будут сформированы вокруг этих выбранных вершин. Вначале кластеры представляют собой {{u}  u  R}. Каждая вершина u  R называется центром своего кластера. Каждая невыбранная вершина v  V – R обрабатывается следующим образом:
Выборка R  V выполняется посредством независимого выбора каждой вершины с вероятностью <math>\frac{1}{\sqrt{n}}</math>. Кластеры будут сформированы вокруг этих выбранных вершин. Вначале кластеры представляют собой {{u}  u  R}. Каждая вершина u  R называется центром своего кластера. Каждая невыбранная вершина v  V – R обрабатывается следующим образом:
(a)
 
Если v не является смежной с какой-либо выбранной вершиной, то каждая дуга, инцидентная v, перемещается в ES.
(a) Если v не является смежной с какой-либо выбранной вершиной, то каждая дуга, инцидентная v, перемещается в E<math>_{S}</math>.
(b) Если v является смежной с одной или несколькими выбранными вершинами, примем за N(v, R) ближайшего (1) к v соседа из числа выбранных вершин. Дуга (v ,N (v, R)) и каждая инцидентная v дуга с весом, меньшим, чем у этой дуги, перемещаются в ES. Затем вершина v добавляется в кластер с центром в N(v, R).
(b) Если v является смежной с одной или несколькими выбранными вершинами, примем за N(v, R) ближайшего (1) к v соседа из числа выбранных вершин. Дуга (v , N(v, R)) и каждая инцидентная v дуга с весом, меньшим, чем у этой дуги, перемещаются в E<math>_{S}</math>. Затем вершина v добавляется в кластер с центром в N(v, R).
На последнем шагу первого этапа все дуги (u, v) из E’, у которых u и v не входят в выборку и принадлежат к разным кластерам, отбрасываются.
На последнем шагу первого этапа все дуги (u, v) из E’, у которых u и v не входят в выборку и принадлежат к разным кластерам, отбрасываются.


Строка 51: Строка 52:
2. Соединение вершин с соседними кластерами:
2. Соединение вершин с соседними кластерами:
Каждая вершина v графа (V’, E’) обрабатывается следующим образом.
Каждая вершина v графа (V’, E’) обрабатывается следующим образом.
Пусть E’(v, c) – дуги из множества E’, инцидентные v, из кластера c. Для каждого кластера c, являющегося соседом v, дуга из E’(v, c) с наименьшим весом перемещается в ES; остальные дуги отбрасываются.
Пусть E’(v, c) – дуги из множества E’, инцидентные v, из кластера c. Для каждого кластера c, являющегося соседом v, дуга из E’(v, c) с наименьшим весом перемещается в E<math>_{S}</math>; остальные дуги отбрасываются.


Количество дуг, добавленных к остову ES за время исполнения описанных этапов алгоритма, можно ограничить следующим образом. Заметим, что множество выборки R формируется путем случайного и независимого выбора каждой вершины с вероятностью 1/n. Из элементарной вероятности следует, что для каждой вершины v  V ожидаемое количество инцидентных ей дуг с весами меньше, чем у (v, N (v, R)), не превосходит n. Таким образом, ожидаемое количество дуг, вносимых в остов каждой вершиной на первом этапе алгоритма, не превосходит n. Количество дуг, добавленных к остову на второй фазе, составляет O(nR). Поскольку ожидаемый размер выборки R равен n, следовательно, ожидаемое количество дуг, добавленных к остову на второй фазе, составляет не более n3/2. Следовательно, ожидаемый размер остова ES по окончании работы Алгоритма II в вышеописанном виде не превосходит 2n3/2. Алгоритм выполняется повторно, если размер остова превосходит 3n3/2. Из неравенства Маркова следует, что ожидаемое количество таких повторений будет составлять O(1).
Количество дуг, добавленных к остову E<math>_{S}</math> за время исполнения описанных этапов алгоритма, можно ограничить следующим образом. Заметим, что множество выборки R формируется путем случайного и независимого выбора каждой вершины с вероятностью 1/n. Из элементарной вероятности следует, что для каждой вершины v  V ожидаемое количество инцидентных ей дуг с весами меньше, чем у (v, N (v, R)), не превосходит n. Таким образом, ожидаемое количество дуг, вносимых в остов каждой вершиной на первом этапе алгоритма, не превосходит n. Количество дуг, добавленных к остову на второй фазе, составляет O(nR). Поскольку ожидаемый размер выборки R равен n, следовательно, ожидаемое количество дуг, добавленных к остову на второй фазе, составляет не более n3/2. Следовательно, ожидаемый размер остова E<math>_{S}</math> по окончании работы Алгоритма II в вышеописанном виде не превосходит 2n3/2. Алгоритм выполняется повторно, если размер остова превосходит 3n3/2. Из неравенства Маркова следует, что ожидаемое количество таких повторений будет составлять O(1).


Установим теперь, что ES является 3-остовом. Заметим, что для каждой дуги edge (u. v)  ES, вершины u и v на первом этапе принадлежат к одному кластеру. Теперь имеет место один из двух случаев.
Установим теперь, что E<math>_{S}</math> является 3-остовом. Заметим, что для каждой дуги edge (u, v)  E<math>_{S}</math>, вершины u и v на первом этапе принадлежат к одному кластеру. Теперь имеет место один из двух случаев.


Случай 1: (u и v принадлежат к одному кластеру)
Случай 1: (u и v принадлежат к одному кластеру)
Строка 63: Строка 64:
Очевидно, что дуга (u, v) была удалена из E’ на этапе 2; предположим, что она была удалена при обработке вершины u. Пусть вершина v входит в кластер с центром x  R.
Очевидно, что дуга (u, v) была удалена из E’ на этапе 2; предположим, что она была удалена при обработке вершины u. Пусть вершина v входит в кластер с центром x  R.


Пусть в начале второго этапа (u, v’)  E’ будет дугой с наименьшим весом среди всех дуг, инцидентных u, от вершин кластера с центром в x. Таким образом, должно выполняться weight(u, v’) ≤ weight(u, v). Обработка вершины u на втором этапе алгоритма гарантирует, что дуга (u, v’) добавляется в ES. Следовательно, существует путь ΠUV = u – v’ – x – v между u и v в остове ES, и его вес ограничен weight(Πuv) = weight(u, v’) + weight(v’, x) + weight(x, v). Поскольку (v’, x) и (v, x) были выбраны на первом этапе, должно выполняться weight(v’, x) ≤ weight(u, v’) и weight(x, v) ≤ weight(u, v). Отсюда следует, что остов (v, ES) имеет коэффициент растяжения 3. Кроме того, обе фазы алгоритма могут быть исполнены за время O(m) с использованием элементарных структур данных и блочной сортировки.
Пусть в начале второго этапа (u, v’)  E’ будет дугой с наименьшим весом среди всех дуг, инцидентных u, от вершин кластера с центром в x. Таким образом, должно выполняться weight(u, v’) ≤ weight(u, v). Обработка вершины u на втором этапе алгоритма гарантирует, что дуга (u, v’) добавляется в E<math>_{S}</math>. Следовательно, существует путь ΠUV = u – v’ – x – v между u и v в остове E<math>_{S}</math>, и его вес ограничен weight(Πuv) = weight(u, v’) + weight(v’, x) + weight(x, v). Поскольку (v’, x) и (v, x) были выбраны на первом этапе, должно выполняться weight(v’, x) ≤ weight(u, v’) и weight(x, v) ≤ weight(u, v). Отсюда следует, что остов (v, E<math>_{S}</math>) имеет коэффициент растяжения 3. Кроме того, обе фазы алгоритма могут быть исполнены за время O(m) с использованием элементарных структур данных и блочной сортировки.
Алгоритм вычисления (2k–1)-остова исполняет k итераций, причем каждая итерация напоминает первый этап алгоритма нахождения 3-остова. Детали и формальное доказательство можно найти в [6].
Алгоритм вычисления (2k–1)-остова исполняет k итераций, причем каждая итерация напоминает первый этап алгоритма нахождения 3-остова. Детали и формальное доказательство можно найти в [6].


Родственные работы
== Родственные работы ==
 
Понятие остова в обобщенном виде исследовалось во многих работах.
Понятие остова в обобщенном виде исследовалось во многих работах.
Аддитивные остовы: описанный выше t-остов аппроксимирует попарные расстояния с мультипликативной ошибкой; его мы будем называть мультипликативным остовом. Аналогичным образом можно определить остов, аппроксимирующий попарные расстояния с аддитивной ошибкой. Такой остов называется аддитивным остовом, а соответствующая ошибка носит название избытка. Эйнгворт и коллеги [1] представили первый аддитивный остов размера O(n3/2 log n) с избытком 2. Босуана и коллеги [7] представили алгоритм построения аддитивного остова размера O(n4/3) с избытком 6. До сих пор остается открытым вопрос, существуют ли более разреженные аддитивные остовы.
Аддитивные остовы: описанный выше t-остов аппроксимирует попарные расстояния с мультипликативной ошибкой; его мы будем называть мультипликативным остовом. Аналогичным образом можно определить остов, аппроксимирующий попарные расстояния с аддитивной ошибкой. Такой остов называется аддитивным остовом, а соответствующая ошибка носит название избытка. Эйнгворт и коллеги [1] представили первый аддитивный остов размера O(n3/2 log n) с избытком 2. Босуана и коллеги [7] представили алгоритм построения аддитивного остова размера O(n4/3) с избытком 6. До сих пор остается открытым вопрос, существуют ли более разреженные аддитивные остовы.
Строка 73: Строка 75:
В дополнение к вышеупомянутым исследованиям по остовам общего вида было проведена большая работа по вычислению остовов для специальных классов графов – к примеру, хордальных графов, невзвешенных графов и евклидовых графов. Для хордальных графов Пелег и Шеффер [14] разработали алгоритм, вычисляющий 2-остов размера O(n3/2) и 3-остов размера O(nlogn). Для невзвешенных графов Халперин и Цвик [13] создали алгоритм с временем исполнения O(m). Салоу [17] представил алгоритм для вычисления (1+ε)-остова d-мерного полного евклидова графа за время O(n log n + n/εd) . Однако ни один из алгоритмов для таких специальных случаев не подходит для работы с взвешенными неориентированными графами общего вида.
В дополнение к вышеупомянутым исследованиям по остовам общего вида было проведена большая работа по вычислению остовов для специальных классов графов – к примеру, хордальных графов, невзвешенных графов и евклидовых графов. Для хордальных графов Пелег и Шеффер [14] разработали алгоритм, вычисляющий 2-остов размера O(n3/2) и 3-остов размера O(nlogn). Для невзвешенных графов Халперин и Цвик [13] создали алгоритм с временем исполнения O(m). Салоу [17] представил алгоритм для вычисления (1+ε)-остова d-мерного полного евклидова графа за время O(n log n + n/εd) . Однако ни один из алгоритмов для таких специальных случаев не подходит для работы с взвешенными неориентированными графами общего вида.


Применение
== Применение ==
 
Остовы исключительно полезны для многих приложений в таких областях, как распределенные системы и коммуникационные сети. В этих приложениях остовы являются основной графовой структурой. Для построения компактных таблиц маршрутизации [16] многие существующие алгоритмы маршрутизации используют дуги разреженного остова для маршрутизации сообщений. В распределенных системах остовы играют важную роль при разработке синхронизаторов. Авербух [3] и Пелег и Ульман [15] показали, что качество остова (выражаемое в терминах коэффициента растяжения и количества дуг остова) тесно связано с временем и вычислительной сложностью любого синхронизатора сети. Остовы также могут неявно использоваться во множестве алгоритмов для вычисления всех пар аппроксимированных кратчайших путей [5, 9, 18]. Примеры других приложений можно найти в работах [2, 3, 14, 16].
Остовы исключительно полезны для многих приложений в таких областях, как распределенные системы и коммуникационные сети. В этих приложениях остовы являются основной графовой структурой. Для построения компактных таблиц маршрутизации [16] многие существующие алгоритмы маршрутизации используют дуги разреженного остова для маршрутизации сообщений. В распределенных системах остовы играют важную роль при разработке синхронизаторов. Авербух [3] и Пелег и Ульман [15] показали, что качество остова (выражаемое в терминах коэффициента растяжения и количества дуг остова) тесно связано с временем и вычислительной сложностью любого синхронизатора сети. Остовы также могут неявно использоваться во множестве алгоритмов для вычисления всех пар аппроксимированных кратчайших путей [5, 9, 18]. Примеры других приложений можно найти в работах [2, 3, 14, 16].


Открытые проблемы
== Открытые проблемы ==
 
Время исполнения и размер (2k–1)-остова, вычисляемого Алгоритмом II, отличаются в k раз от соответствующих нижних границ для худшего случая. Для любого константного значения k оба эти параметра являются оптимальными. Однако для экстремального значения k, а именно – для k = log n, имеется отклонение с коэффициентом log n. Возможно ли избавиться от этого мультипликативного множителя k ко времени исполнения алгоритма и/или размеру вычисляемого (2k–1)-остова? Представляется, что для решения этой задачи могут быть полезны более тщательный анализ и передовые теоретико-вероятностные инструменты.
Время исполнения и размер (2k–1)-остова, вычисляемого Алгоритмом II, отличаются в k раз от соответствующих нижних границ для худшего случая. Для любого константного значения k оба эти параметра являются оптимальными. Однако для экстремального значения k, а именно – для k = log n, имеется отклонение с коэффициентом log n. Возможно ли избавиться от этого мультипликативного множителя k ко времени исполнения алгоритма и/или размеру вычисляемого (2k–1)-остова? Представляется, что для решения этой задачи могут быть полезны более тщательный анализ и передовые теоретико-вероятностные инструменты.


Recommended Reading
== Литература ==
1. Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28,1167-1181 (1999)
1. Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28,1167-1181 (1999)
2. Althofer, I., Das, G., Dobkin, D.P.,Joseph, D., Soares J.:On sparse  spanners of weighted graphs. Discret. Comput. Geom. 9, 81-100(1993)
2. Althofer, I., Das, G., Dobkin, D.P.,Joseph, D., Soares J.:On sparse  spanners of weighted graphs. Discret. Comput. Geom. 9, 81-100(1993)
3. Awerbuch, B.: Complexity of network synchronization. J. Assoc.
3. Awerbuch, B.: Complexity of network synchronization. J. Assoc.
Источник — http://pco.iis.nsk.su/wega/index.php/Алгоритмы_поиска_остова_во_взвешенном_графе