![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Данная функция находит подходящее ребро минимальной приведенной стоимости. Это простая реализация производит обход всех ребер в сети.
int costR(Edge *e, int v) { int R * e-> cost() + phi[e-> w()] - phi[e-> v()]; return e-> from(v)? R: -R; } Edge *besteligible() { Edge *x = 0; for (int v = 0, min = C*G.V(); v < G.V(); v++) { typename Graph:: adjIterator A(G, v); for (Edge* e = A.beg();! A.end(); e = A.nxt()) if (e-> capRto(e-> other(v)) > 0) if (e-> capRto(v) == 0) if (costR(e, v) < min) { x = в; min = costR(e, v); } } return x; }
Глава 22, Потоки в сетях мы замечания, сделанные нами в адрес реализации с вычеркиванием циклов (программа 22.9), а именно: это хорошо, что такая небольшая порция программных кодов обладает достаточной мощью, чтобы обеспечить получение полезных решений в контексте общей модели решения задач, которая позволяет решать задачи о потоках минимальной стоимости. Таблица 22.14. Сетевой симплексный алгоритм (базовая реализация)
template < class Graph, class Edge> class MINCOST { const Graph & G; int s, t; int valid; vector< Edge *> st; vector< int> mark, phi; void dfsR(Edge); int ST(int); int phiR(int); int lсa(int, int); Edge *augment(Edge *); bool onpath(int, int, int); void reverse(int, int); void update (Edge *, Edge *); int costR(Edge *, int); Edge *besteligible(); public: MINCOST(Graph & G, int s, int t): G(G), s(s), t(t) st(G.V()), marfc(G.V(), -1), phi(G.V()) { Edge *z = new EDGE(s, t, M*G.V(), C*G.V()); G.insert(z); z-> addflowto(t, z-> cap()); dfsR(z); for (valid = 1;; valid++) { phi[t] = z-> costRto(s); mark[t] = valid; for (int v = 0; v < G.V(); v++) if (v! = t) phi[v] = phiR(v); Edge *x = besteligible(); if (costR(x, x-> v()) == 0) break; update(augment(x), x); } G.remove(z); delete z; }
Часть 5. Алгоритмы на графах
В свете всех этих соображений существует множество вариантов улучшения производительности рассматриваемых алгоритмов. Например, программа 22.15 является еще одной реализацией сетевого симплексного алгоритма. Прямолинейная реализация в программе 22.14 всегда требует времени, пропорционального V, на обновление потенциалов дерева, и всегда затрачивает время, пропорциональное Е, на обнаружение подходящего ребра с максимальной приведенной стоимостью. Реализация программы 22.15 имеет целью ликвидировать упомянутые выше затраты в типовых сетях. Программа 22.15. Сетевой симплексный алгоритм (усовершенствованная реализация) Замена ссылок на phi обращениями к phiR в функции R и замена цикла for в конструкторе программы 22.14 данным программным кодом позволяет получить реализацию сетевого симплексного алгоритма, которая обеспечивает экономию времени на каждой итерации за счет того, что потенциалы вычисляются, когда это необходимо, и за счет выбора первого обнаруженного ею подходящего ребра. int old = 0; for (valid = 1; valid! = old;) { old = valid; for (int v = 0; v < G.V(); v++) { typename Graph:: adjIterator A(G, v); for (Edge* e = A.beg();! A.end(); e = A.nxt()) if (e-> capRto(e-> other(v)) > 0) if (e-> capRto(v) == 0) { update(augment(e), e); valid++; } } }
Во-вторых, для вычисления потенциалов мы принимаем " отложенный" подход. Вместо того, чтобы вычислять все потенциалы в векторе phi, индексированном именами вер-
|