4551
правка
Алгоритмы поиска остова во взвешенном графе: различия между версиями
Материал из WEGA
Алгоритмы поиска остова во взвешенном графе (посмотреть исходный код)
Версия от 00:16, 19 февраля 2012
, 19 февраля 2012→Алгоритм I
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) м (→Алгоритм I) |
||
| Строка 15: | Строка 15: | ||
== Алгоритм I == | == Алгоритм I == | ||
Этот алгоритм выбирает дуги для остова по принципу жадности; он напоминает алгоритм Крускала для вычисления минимального остовного дерева. Дуги графа обрабатываются в порядке возрастания их весов. Начиная с остова <math>E_{S} = \varnothing</math>, алгоритм последовательно добавляет дуги. Решение о том, добавлять ли некоторую дугу (скажем, (u, v)) к | Этот алгоритм выбирает дуги для остова по принципу жадности; он напоминает алгоритм Крускала для вычисления минимального остовного дерева. Дуги графа обрабатываются в порядке возрастания их весов. Начиная с остова <math>E_{S} = \varnothing</math>, алгоритм последовательно добавляет дуги. Решение о том, добавлять ли некоторую дугу (скажем, <math>(u, v) \, </math>) к <math>E_{S} \, </math> или нет, принимается на основе следующего соображения: | ||
''Если расстояние между u и v в подграфе, индуцированном текущими дугами остова | ''Если расстояние между u и v в подграфе, индуцированном текущими дугами остова <math>E_{S} \, </math>, больше, чем t-weight(M, v), то дугу (u, v) следует добавить к to <math>E_{S} \, </math>, в противном случае отбросить.'' | ||
Из этого следует, что <math>P_{t}(x, y) \, </math> будет выполняться для каждой дуги E, не входящей в <math>E_{S} \, </math>, так что в конце концов подграф <math>(v, E_{S}) \, </math> будет представлять собой t-остов. Хорошо известное утверждение элементарной теории графов гласит, что граф с более чем <math>n^{1+\frac{1}{k}}</math> дугами должен содержать цикл длиной не более 2k. Из приведенного выше алгоритма следует, что длина любого цикла в подграфе <math>(V, E_{S}) \, </math> должна составлять не менее t + 1. Следовательно, для t = 2k – 1 количество дуг в подграфе <math>(V, E_{S}) \, </math> будет менее <math>n^{1+\frac{1}{k}}</math>. Таким образом, Алгоритм I вычисляет (2k–1)-остов размера <math>O(n^{1+\frac{1}{k}})</math>, что является оптимальным, с учетом вышеупомянутой нижней границы. | |||
Простая реализация Алгоритма I размера <math>O(mn^{1+\frac{1}{k}})</math> разработана на базе алгоритма Дейкстры. Коэн [9], а впоследствии – Торуп и Цвик [18] разработали алгоритмы для (2k–1)-остова с улучшенным временем исполнения – <math>O(kmn^{\frac{1}{k}})</math>. Эти алгоритмы используют для вычисления расстояния несколько вызовов алгоритма Дейкстры нахождения кратчайших путей с единственным источником и в силу этого неспособны достичь линейного времени исполнения. С другой стороны, поскольку остов должен аппроксимировать расстояния между всеми парами вершин в графе, было бы сложно вычислить остов, избегая получения явной информации о расстояниях. Как ни удивительно, Алгоритм II успешно избегает каких-либо вычислений расстояния и достигает почти линейного времени исполнения. | Простая реализация Алгоритма I размера <math>O(mn^{1+\frac{1}{k}})</math> разработана на базе алгоритма Дейкстры. Коэн [9], а впоследствии – Торуп и Цвик [18] разработали алгоритмы для (2k–1)-остова с улучшенным временем исполнения – <math>O(kmn^{\frac{1}{k}})</math>. Эти алгоритмы используют для вычисления расстояния несколько вызовов алгоритма Дейкстры нахождения кратчайших путей с единственным источником и в силу этого неспособны достичь линейного времени исполнения. С другой стороны, поскольку остов должен аппроксимировать расстояния между всеми парами вершин в графе, было бы сложно вычислить остов, избегая получения явной информации о расстояниях. Как ни удивительно, Алгоритм II успешно избегает каких-либо вычислений расстояния и достигает почти линейного времени исполнения. | ||
