Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Программа 22.7. Двудольное сочетание через приведение к алгоритму вычисления максимального потока
|
|
Этот клиент считывает задачу о двудольном сочетании со стандартного ввода, затем строит транспортную сеть, соответствующую этой задаче двудольного сочетания, находит максимальный поток и использует полученное решение для распечатки максимального двудольного сочетания.
#include " GRAPHbasic.cc" #include " MAXFLOW.cc" int main(int argc, char *argv[]) { int s, t, N = atoi(argv[1]); GRAPH< EDGE> G(2*N+2); for (int i = 0; i < N; i++)
G.insert(new EDGE(2*N, i, 1)); while (cin» s» t)
G.insert(new EDGE(s, t, 1)); for (int i = N; i < 2*N; i++)
G.insert(new EDGE(i, 2*N+1, 1)); MAXFLOW< GRAPH< EDGE>, EDGE> (G, 2*N, 2*N+1); for (int i = 0; i < N; i++)
GRAPH< EDGE>:: adj Iterator A(G, i);
for (EDGE* e = A.beg();! A.end(); e = A.nxt()) if (e-> flow() == 1 & & e-> from(i)) cout «e-> v() «" -" «e-> w() «endl; }
Часть 5. Алгоритмы на графах
Следствие. Время, которое требуется для вычисления сочетания на максимальном числе элементов некоторого двудольного графа, есть 0(VE).
Доказательство: Непосредственно следует из свойства 22.6. ■
Работу алгоритмов аугментальных путей на двудольной сети с единичной пропускной способностью ребер описать нетрудно. Каждый аугментальный путь наполняет одно ребро, ведущее из истока, и одно ребро, ведущее в сток. Эта ребра никогда не используются как обратные, следовательно, существуют не более V аугментальных путей. Для каждого алгоритма, который находит аугментальные пути за время, пропорциональное Е, действительна верхняя граница, пропорциональная VE.
В таблице 22.3 показаны значения производительности методов решения задач двудольного сочетания с использованием различных алгоритмов вычисления аугментальных путей. Из этой таблицы следует, что фактические значения времени решения этой задачи ближе к границе V Е для худшего случая, чем к оптимальному (линейному) времени. Благодаря разумному выбору и соответствующей настройке реализации, вычисляющей максимальный поток, можно увеличить быстродействие этого метода в √ V раз (см. упражнения 22.91 и 22.92).
Таблица 22.3. Эмпирические исследования двудольного сочетания_______________
В эту таблицу сведены показатели производительности (число добавленных вершин и число затронутых узлов списков смежных вершин) для случаев использования различных алгоритмов вычисления максимального потока методом аугментальных путей при вычислении двудольного сочетания для графов с 2000 парами вершин и 500 ребрами (вверху), а также 4000 ребер (внизу). Для решения этой задачей наиболее эффективным показал себя поиск в глубину.
Эта задача характерна для ситуаций, с которыми мы чаще сталкиваемся, когда изучаем новые задачи и более общие модели решения задач, демонстрирующие эффективность применения на практического сведения как инструментального средства решения задач. Если мы сможем найти сведение к более известной общей задаче, к такой как, например, задача о максимальном потоке, мы обычно рассматриваем это как существенное продвижение на пути к практическому решению, ибо оно, по меньшей мере, не только указывает на то, что задача решаемая, но и на то, что существуют многочисленные эффективные алгоритмы решения рассматриваемой задачи. Во многих ситуациях целесо-