4501
правка
Алгоритмы поиска остова во взвешенном графе: различия между версиями
Материал из WEGA
Алгоритмы поиска остова во взвешенном графе (посмотреть исходный код)
Версия от 00:20, 18 декабря 2011
, 18 декабря 2011нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 23: | Строка 23: | ||
''Если расстояние между u и v в подграфе, индуцированном текущими дугами остова E<math>_{S}</math>, больше, чем t-weight(M, v), то дугу (u, v) следует добавить к to E<math>_{S}</math>, в противном случае отбросить.'' | ''Если расстояние между u и v в подграфе, индуцированном текущими дугами остова E<math>_{S}</math>, больше, чем t-weight(M, v), то дугу (u, v) следует добавить к to E<math>_{S}</math>, в противном случае отбросить.'' | ||
Из этого следует, что P<math>_{t}</math>(x, y) будет выполняться для каждой дуги E, не входящей в E<math>_{S}</math>, так что в конце концов подграф (v, E<math>_{S}</math>) будет представлять собой t-остов. Хорошо известное утверждение элементарной теории графов гласит, что граф с более чем | Из этого следует, что P<math>_{t}</math>(x, y) будет выполняться для каждой дуги E, не входящей в E<math>_{S}</math>, так что в конце концов подграф (v, E<math>_{S}</math>) будет представлять собой t-остов. Хорошо известное утверждение элементарной теории графов гласит, что граф с более чем <math>n^{1+1/k}</math> дугами должен содержать цикл длиной не более 2k. Из приведенного выше алгоритма следует, что длина любого цикла в подграфе (V, E<math>_{S}</math>) должна составлять не менее t + 1. Следовательно, для t = 2k – 1 количество дуг в подграфе (V, E<math>_{S}</math>) будет менее <math>n^{1+1/k}</math>. Таким образом, Алгоритм I вычисляет (2k–1)-остов размера O(<math>n^{1+1/k}</math>), что является оптимальным, с учетом вышеупомянутой нижней границы. | ||
Простая реализация Алгоритма I размера O(<math>mn^{1+1/k}</math>) разработана на базе алгоритма Дейкстры. Коэн [9], а впоследствии – Торуп и Цвик [18] разработали алгоритмы для (2k–1)-остова с улучшенным временем исполнения – O(<math>kmn^{1/k}</math>). Эти алгоритмы используют для вычисления расстояния несколько вызовов алгоритма Дейкстры нахождения кратчайших путей с единственным источником и в силу этого неспособны достичь линейного времени исполнения. С другой стороны, поскольку остов должен аппроксимировать расстояния между всеми парами вершин в графе, было бы сложно вычислить остов, избегая получения явной информации о расстояниях. Как ни удивительно, Алгоритм II успешно избегает каких-либо вычислений расстояния и достигает почти линейного времени исполнения. | Простая реализация Алгоритма I размера O(<math>mn^{1+1/k}</math>) разработана на базе алгоритма Дейкстры. Коэн [9], а впоследствии – Торуп и Цвик [18] разработали алгоритмы для (2k–1)-остова с улучшенным временем исполнения – O(<math>kmn^{1/k}</math>). Эти алгоритмы используют для вычисления расстояния несколько вызовов алгоритма Дейкстры нахождения кратчайших путей с единственным источником и в силу этого неспособны достичь линейного времени исполнения. С другой стороны, поскольку остов должен аппроксимировать расстояния между всеми парами вершин в графе, было бы сложно вычислить остов, избегая получения явной информации о расстояниях. Как ни удивительно, Алгоритм II успешно избегает каких-либо вычислений расстояния и достигает почти линейного времени исполнения. | ||
| Строка 29: | Строка 29: | ||
== Алгоритм II == | == Алгоритм II == | ||
Алгоритм выполняет оригинальную кластеризацию на основе сверхлокального подхода и устанавливает следующий результат для задачи нахождения остова. | Алгоритм выполняет оригинальную кластеризацию на основе сверхлокального подхода и устанавливает следующий результат для задачи нахождения остова. | ||
Пусть даны взвешенный граф G = (V, E) и целое число k > 1. Остов с коэффициентом растяжения (2k–1) и размером O(<math>kn^{1+1/k}</math>) может быть вычислен за время O(km). | Пусть даны взвешенный граф G = (V, E) и целое число k > 1. Остов с коэффициентом растяжения (2k–1) и размером O(<math>kn^{1+1/k}</math>) может быть вычислен за время O(km). | ||
Алгоритм выполняется в O(k) этапов; на каждом этапе он вычисляет список смежности для каждой вершины с целью отсечения необязательных дуг. Для доказательства простоты алгоритма далее приводятся его полная версия для нахождения 3-остова и анализ алгоритма. Алгоритм может быть легко адаптирован к другим вычислительным моделям (с параллельной, внешней или распределенной памятью) с сохранением почти оптимальной производительности (подробнее см. в [6]). | Алгоритм выполняется в O(k) этапов; на каждом этапе он вычисляет список смежности для каждой вершины с целью отсечения необязательных дуг. Для доказательства простоты алгоритма далее приводятся его полная версия для нахождения 3-остова и анализ алгоритма. Алгоритм может быть легко адаптирован к другим вычислительным моделям (с параллельной, внешней или распределенной памятью) с сохранением почти оптимальной производительности (подробнее см. в [6]). | ||
Вычисление 3-остова за линейное время | == Вычисление 3-остова за линейное время == | ||
Чтобы удовлетворять ограничениям 3-остова, вершина должна внести в остов вклад в размере в среднем | |||
Вначале имеется множество | Чтобы удовлетворять ограничениям 3-остова, вершина должна внести в остов вклад в размере в среднем <math>\sqrt{n}</math> дуг. Таким образом, вершины степени <math>O(\sqrt{n})</math> обработать легко, поскольку все их дуги могут быть выбраны для остова. Для вершин более высокой степени применяется схема кластеризации (группировки), основанная на доминирующих множествах. | ||
Вначале имеется множество дуг E’, инициализированное равным E, и пустой остов ES. Алгоритм просматривает дуги E’, переносит некоторые из них в остов ES и отбрасывает остальные. Это происходит в два этапа. | |||
1. Формирование кластеров: | 1. Формирование кластеров: | ||
Выборка R V выполняется посредством независимого выбора каждой вершины с вероятностью 1/ | Выборка R V выполняется посредством независимого выбора каждой вершины с вероятностью <math>\frac{1}{\sqrt{n}}</math>. Кластеры будут сформированы вокруг этих выбранных вершин. Вначале кластеры представляют собой {{u} u R}. Каждая вершина u R называется центром своего кластера. Каждая невыбранная вершина v V – R обрабатывается следующим образом: | ||
(a) | (a) | ||
Если v не является смежной с какой-либо выбранной вершиной, то каждая дуга, инцидентная v, перемещается в ES. | Если v не является смежной с какой-либо выбранной вершиной, то каждая дуга, инцидентная v, перемещается в ES. | ||
