Pull to refresh

Максимальный поток минимальной стоимости

Reading time15 min
Views84K
Транспортная задача (классическая) — задача об оптимальном плане перевозок товара со складов в пункты потребления на транспортных средствах.

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

Под катом очень-очень много текста, т.к. рассказывается один из вариантов решения данной задачи «в картинках» для тех, кто мало знаком с графами. Листинг прилагается.


На Хабре как-то проскользнула статья, где поднимался вопрос, а нужны ли статьи про основные алгоритмы. Я решил откликнуться на просьбы и немного рассказать про алгоритмы на графах и их практическое применение. Не знал, на какой уровень знаний рассчитывать, поэтому выбрал один относительно сложный и теоретически-практический алгоритм, чтобы статья носила хотя бы отчасти прикладной характер. При этом очень постараюсь рассказать доступно даже для тех, кто не особо знаком с графами.

Задача (сказка): Вы владелец некоторого завода, выпускающего «Товар», и недавно Вам посчастливилось заключить контракт с одной крупной фирмой, находящейся в другом городе на поставку товаров в их розничную сеть. Так как он находится очень далеко (во Владивостоке), товары придется доставлять авиаперевозкой. В ходе телефонных переговоров Партнер поинтересовался «а на какой объем поставок в день мы можем рассчитывать?». Вы задумались… У Вас есть собственные грузовики (дальнобойщики) осуществляющие транспортировку. Аэропорт находится далековато. Просмотрев накопленную статистику перевозок, Вы выявили, что в собственной области при транспортировке есть некоторые ограничения: на дорогах стоят пункты досмотра груза, весового контроля, некоторые дороги и вовсе ремонтируются. Все это назовем «пропускной способностью» дорог в день. Отталкиваясь от этих условий Вам необходимо узнать: сколько ящиков «Товара» в день вы можете подвозить в аэропорт? При этом, вы хотите эффективно вести бизнес и доставлять товар, кратчайшими маршрутами, т.к. это износ шин, механизмов, в общем амортизационные расходы.

Итого: сколько ящиков Вы сможете транспортировать в аэропорт в день, учитывая пропускную способность дорог, при этом, чтобы общее расстояние маршрутов было минимальным?

Задача – самая что ни на есть на графах. Решение будет построено постепенно.
There are no big problems, there are just a lot of little problems. (с)

Алгоритмы буду, если можно так выразиться, рассказывать, т.к. в сети предостаточно их описаний.

Основные понятия. Граф? Барон?


Карта дорог в нашем случае представляется в виде графа. Вершинами являются перекрестки, а ребра графа – это дороги. Ребрам (дорогам) приписаны их характеристики: расстояние (до след. перекрестка), а так же пропускная способность в день.

В коде граф представляют либо в виде списков смежности, либо матрицы смежности. Для простоты мы будем использовать матрицу смежности. Если в матрице смежности на пересечении [u] и [v] вершины стоит «1» – значит, что эти вершины (перекрестки) соединены ребром (дорогой). Не обязательно обозначать именно «1», в матрице очень удобно можно хранить и иную полезную информацию приписанную ребру: например расстояние, и пропускную способность (в аналогичной матрице).



На рисунке изображена матрица, симметричная относительно главной диагонали, т.е. M[u][v] = M[v][u]. Это значит, что нам задан ненаправленный граф и по ребру можно пройти в любом направлении (туда-обратно). Если в матрице M[u][v] = 1, а в обратном направлении M[u][v] = 0, то граф – направленный и можно пройти по ребру только от вершины [u] до [v].

Пропускные способности дорог у нас будут записаны в матрицу C[..][..], которая вообще говоря, представляет собой направленный граф. Ведь дороги нам нужны для того, чтобы проехать от «завода» по направлению в «аэропорт». Направленный граф с заданными пропускными способностями (заводом и аэропортом) называется – сетью.

Когда для графа необходимо вычислить определенную характеристику, но не массово «от всех-ко-всем», а допустим расстояние от одной вершины до остальных, то гораздо удобнее воспользоваться массивом (меньше памяти). Т.е. допустим в [u] ячейке массива dist[..] будем хранить расстояние до [u] вершины от «завода». Аналогично массивами будем пользоваться, при обходе графа для того, чтобы отмечать уже посещенные вершины (mark), записывать сколько ящиков привезли (push), и откуда мы в вершину приехали (pred).

ОК. Отлично. Знаем, как преобразовать нашу карту в граф. А как мы будем доставлять ящики до аэропорта? Нам нужно уметь находить путь от «завода» до «аэропорта». Для этого будем пользоваться…

Алгоритм поиска в ширину (breadth first search), BFS.


Пока мы учитываем только: смежность (соседство) вершин графа, не рассматривая пропускные способности и расстояния.

BFS является одним из самых основных алгоритмов, составляющих основу многих других.
Простое описание (рисунок будет ниже). Мы сейчас стоим в некоторой стартовой (завод) вершине [s], из которой по ребрам видны только соседние вершины. И нам очень нужно как можно скорее попасть в вершину [t], которая находится где-то в этом графе. Далее мы поступаем так. Просматриваем по ребрам (а именно свободным дорогам) нашей вершины соседей: есть ли среди них [t]. Если нет, то записываем всех (впервые обнаруженных) соседей в очередь «нужно там побывать». Когда просмотрели всех соседей — отмечаем свою вершину – «тут уже побывали». Достаем первую непосещенную вершину из очереди и идем в нее.

Продолжаем поиски таким же образом. При этом те вершины, в которых однажды побывали — игнорируем (ни шагу назад). Если по дороге встретили [t] – отлично, цель достигнута!

Для того, чтобы не заезжать в одни и те же перекрестки по нескольку раз, мы будем их отмечать в массиве mark[..]. После осмотра соседей из [u] вершины, ставим отметку mark[u] = 1 – значит, что на [u]-ом перекрестке мы «уже побывали».

На рисунке: в вершинах – написаны порядковые номера



После завершения алгоритма получим следующую картину:



Отметим основные особенности:
  • в каждую вершину мы попадаем ровно (не более чем) один раз
  • помещаем вершины в очередь при их первом просмотре
  • от своего завода мы радиально (волнообразно) находим остальные вершины в графе
  • «радиус осмотра» постоянно увеличивается
  • когда мы найдем «аэропорт», то количество ребер (дорог) между «заводом» и «аэропортом» будем минимальным. Т.о. мы быстрейшим осмотром графа найдем «аэропорт»
  • Смотрим только по свободным дорогам, по которым можно перевезти ящики!
  • Эххх… пока мы не учитываем реальные расстояния (километраж).

Теперь мы знаем, как найти путь, по которому можно провезти наши ящики «Товара» в аэропорт. Хорошо… Провезем их по дороге, и отметим это себе на карте. Эту пометку – «сколько ящиков, по какой дороге (ребру) и в какую сторону мы везем» мы назовем «поток». Отмечать это будем в матрице (flow) F[..][..]. Т.е. по дороге из [u] в [v] мы везем F[u][v] ящиков.

Пора столкнуться с реальностью – придется считаться с «пропускной способностью», которая обозначается матрицей (capacity) C[..][..]. Ведь по дороге от [u] в [v] мы можем провезти не более C[u][v] ящиков. That’s a pity.

Мы поступили дальновидно. Пока мы BFS’ом искали «аэропорт», пока отмечали «посещенные вершины» мы так же отмечали, из какого перекрестка приехали — записывали в массив pred[..]. Т.е. в вершину [v] мы попали из вершины pred[v]. И так же заблаговременно завели еще один полезный массив: push[v], т.е. сколько мы могли бы «толкнуть» ящиков в перекресток [v] по некоторой дороге [u]-[v].
И поддерживали его в актуальном состоянии: push[v] = min(push[u], C[u][v]-F[u][v]);

Благодаря этому, пока нам не придется лишний раз «разматывать» траекторию от «аэропорта» до «завода» в обратном порядке, чтобы вычислить, сколько максимально ящиков мы сможем провести по этому маршруту.

Push[v] = push[«аэропорт»] = flow = вот! сколько ящиков довезли в аэропорт по найденному пути. Один раз размотаем маршрут и по всем ребрам (дорогам), и добавим «поток» flow ко всем ребрам пути.

Но, хоть в задаче речь идет о натуральных величинах: количестве ящиков, пропускной способности и расстояниях, все же возможно придется столкнуться с «минусом»…

Увеличение потока (или Алгоритм Форда-Фалкерсона)


Теперь принимаем во внимание: смежность (соседство) вершин графа, направленные пропускные способности ребер, но пока не рассматриваем расстояния.

Когда мы увеличиваем поток (ящиков) от вершины [u] к вершине [v], мы естественно выполняем операцию: F[u][v] += flow, но в обратную сторону мы уменьшаем поток F[v][u] -= flow; Вот почему. Возможна такая ситуация:

На рисунке: на ребрах – подписан (поток / пропускная способность)



В первый раз, пронеся поток в 3 ящика в вершину [i] и обнаружив ребро [i]-[j]: Мы перевезли min(push[i], C[i][j] – F[i][j]) = min(3, 3-0) = 3 ящика, и отметили это как F[i][j] += 3, а в обратную сторону мы поставили: F[j][i] -= 3.

Во второй раз, оказавшись в вершине [j], мы пытаемся протолкнуть min(push[j], C[j][i]-F[j][i]) = min(6, 0-(-3)) = min(6, 3) = 3 в вершину [i]. Против потока +3, мы толкнули -3 ящиков и получили компенсацию потока по этой дороге. Зато в направлении к «аэропорту» в следующей итерации мы дополнительно отправили остальные 3 ящика.

Интерпретация: из склада [j] мы позвонили в склад [i], и сказали: «Оставьте себе свои 3 ящика – найдите им другое применение, мы вместо них привезли своих 3». Хоть алгоритм сам любезно нашел им применение.

Продолжаем искать поток:


Мы договорились, настойчиво продолжать искать пути к «аэропорту», пока удается, и провозить по ним ящики. Грубо говоря, это и называется алгоритмом поиска максимального потока, или алгоритм Форда-Фалкерсона. А так как мы для «открытия» новых маршрутов доставки применяем BFS – это называется алгоритмом Эдмондса-Карпа.

Когда до упора «насытим» дороги транспортировкой своих ящиков, мы ответим Партнеру на вопрос «Сколько ящиков в день мы сможем провозить в аэропорт?». Но пора подумать и о собственных амортизационных расходах… Шины, бензин, износ…

Уже стало ясно, что при поиске BFS’ом по графу нам придется сталкиваться с отрицательными величинами, такими как обратный поток (а он имеет следствия в «финансовом выражении»), даже если речь идет о расстояниях. В общем, пора уже учитывать дополнительно и расстояния…

Расстояния. Hit the road, Jack!


Пора целиком добить эту задачу: смежность (соседство) вершин графа, направленные пропускные способности ребер, расстояния.

Продолжаем запускать BFS, пока не загрузим дороги нашими ящиками «до упора»:



Теперь посмотрим на то, что получилось. Будем проверять со стороны «аэропорта»: если какой-то ящик к нам добрался за расстояние 15 км., значит если бы мы от него отказались – то, сэкономили бы 15 км. проезда (т.е. вычитаем 15), но нужно по возможности попробовать найти (пристроить) ему другой путь движения.

Попробуем пройтись по ребрам в прямом (по свободным дорогам) и обратном (толкая назад и экономя) направлениях от «аэропорта»:

На рисунке: на ребрах – подписан (поток / пропускная способность), а сверху — расстояние



На картинке сверху – мы обнаружили «отрицательный цикл» -6, все так же шагая по доступным (свободным или толкая против потока) ребрам. Делая в нем один оборот, мы можем сократить расстояние для участвующих в нем вершин на -6. А это значит, что можно сэкономить на доставке транспортируемых в цикле ящиков. Просто пустив ящики «по циклу». На картинке сверху – мы сэкономим 6 км. пути.

Теперь мы знаем, как решить поставленную задачу, но для того, чтобы обнаруживать эти циклы… Рассмотрим:

Алгоритм Беллмана-Форда


Он применяется для нахождения кратчайшего расстояния от вершины [s] до остальных вершин. Но в отличие от BFS, коротким путь будет не в смысле количества ребер графа на этом пути, а в смысле суммированного «расстояния» по ребрам пути.

Но он нам понадобится не для этого. Одна из его ключевых особенностей, отличающая его от алгоритма Дейкстры, заключается в том, что он способен работать на графах, где вес ребер может быть задан отрицательным числом. Алгоритм может обнаруживать побочное явление таких графов — циклы отрицательной величины. Что нам и надо!

Алгоритм несколько сложней. Данная реализация несколько не коррелирует с библией Кормена, но тоже отлично работает. По виду она несколько напоминает BFS, потому и постараюсь объяснить, отталкиваясь от него.

Начиная с некоторой вершины, просматриваем по «доступным» ребрам соседние вершины, и пытаемся улучшить до них расстояние в массиве dist[..] и сделать как можно меньше. Этот процесс называется «релаксация». Если «нащупали» (по ребрам) такие вершины, то обновляем им расстояния и заносим их вершины в очередь «попробовать из них улучшить граф». Очень похоже на BFS! Но мы не отмечаем вершины («уже побывали») и если придется зайти в одну вершину дважды, то сделаем это.

Но вот вопрос, готовы ли мы к тому, что будут попадаться «отрицательные циклы», по которым можно вечно крутиться, уменьшая расстояние до вершин? Процесс не закончится. Поэтому, «радиус осмотра» вершин ограничим числом N (числом самих вершин). Этого будет гарантированно достаточно для того, чтобы просчитать минимальное расстояние до любой вершины, а главное алгоритм в любом случае завершится.

Для этого поместим первую вершину в очередь, и после нее «заглушку», таким образом обозначив, что в очереди находятся вершины в «радиусе осмотра 0». Когда, вынимая из очереди следующую вершину, вдруг достанем нашу «заглушку» — поставим новую, обозначив следующий «радиус осмотра». Вот, в общем, и вся логика алгоритма. =)

Улучшение расстояние до вершин проверяется следующим неравенством:
dist[v] > dist[u] + edge_cost(u, v)

На рисунке: на ребрах – длина, а в подсказке – найденное в текущий момент кратчайшее расстояние



Отметим основные особенности (в отличие от BFS):
  • в вершину мы можем попасть несколько раз, если расстояние до нее было улучшено. Зайдя потом в эту вершину, мы попробуем улучшать расстояния уже из нее
  • в очередь помещаются вершины, до которых было улучшено расстояние
  • от своего завода мы радиально (волнообразно) по расстояниям (а не по ребрам) находим остальные вершины
  • смотреть будем только по свободным дорогам, по которым можно перевезти (либо толкнуть обратно) ящики. Следовательно, учитывая расстояния и пропускную способность

Просмотр графа в «радиусе N (количества вершин)» гарантирует, что для всех вершин мы нашли минимальное расстояние. И больше нечего уменьшать. А если какие-то из вершин «втянуты» в «отрицательный цикл», то его легко можно будет обнаружить, проверив на нарушение равенства. Ведь в цикле расстояния бесконечно уменьшаются:
dist[v] > dist[u] + edge_cost(u, v)

Поэтому, если для вершины [v] это неравенство выполнится, значит – она участвует в отрицательном цикле. Что и нужно! «Разматывая» от нее путь, по которому мы в нее попали, мы будем крутиться по (её) циклу.

Все – цикл обнаружен! Осталось всего-то поток ящиков по нему направить «вспять», и тем самым увеличить эффективность ведения бизьнеса.

Алгоритм Максимального потока минимальной стоимости:


  • Запускаем нахождение Максимального потока Эдмондса-Карпа:
    • Пока BFS находит путь от «завода» до «аэропорта»
      • провозим по нему ящики
  • Пока алгоритм Беллмана-Форда находит «отрицательные циклы»:
    • Поворачиваем поток в «отрицательных циклах» вспять.
  • Получили максимальный поток минимальной стоимости (расстояния)


Все. Звоним Партнеру и сообщаем, какое количество товаров в день мы сможем ему поставлять. И думаем, как применить сэкономленные деньги. =)

int C[MAX_N][MAX_N];    // Матрица "пропускных способностей"
int F[MAX_N][MAX_N];    // Матрица "текущего потока в графе"
int P[MAX_N][MAX_N];    // Матрица "стоимости (расстояний)"
int push[MAX_N];        // Поток в вершину [v] из начальной точки
int mark[MAX_N];        // Отметки на вершинах, в которых побывали
int pred[MAX_N];        // Откуда пришли в вершину [v] (предок)
int dist[MAX_N];        // Расстояние до вершины [v] из начальной точки
int N, M, s ,t;         // Кол-во вершин, ребер, начальная и конечные точки
int max_flow;
int min_cost;

void file_read()
{
    int u, v, c, p;
    in >> N >> M >> s >> t; N++;
    
    for(int i = 0; i < M; i++)
    {
        in >> u >> v >> c >> p;
        C[u][v] = c;
        P[u][v] = p;
        P[v][u] = -p;
    }
}

int edge_cost(int u, int v)
{
    if( C[u][v] - F[u][v] > 0 ) return P[u][v];
    else return MAX_VAL;
}

int check_cycles()
{
    for(int u = 1; u < N; u++)
        for(int v = 1; v < N; v++)
            if( dist[v] > dist[u] + edge_cost(u, v) )
                return u;

    return MAX_VAL;
}

void init()
{
    for(int i = 1; i < N; i++)
    {
        mark[i] = 0;
        push[i] = 0;
        pred[i] = 0;
        dist[i] = MAX_VAL;
    }
}

// Алгоритм Поиска в ширину

int bf(int s)
{
    init();
    queue<int> Q;
    pred[s] = s;
    dist[s] = 0;

    Q.push(s);
    Q.push(MAX_N);
    
    int u, series = 0;
    while( !Q.empty() )
    {
        while( Q.front() == MAX_N )
        {
            Q.pop();
            if( ++series > N ) return check_cycles();
            else Q.push(MAX_N);
        }

        u = Q.front(); Q.pop();
        for(int v = 1; v < N; v++)
            if( dist[v] > dist[u] + edge_cost(u, v) )
            {
                dist[v] = dist[u] + edge_cost(u, v);
                pred[v] = u;
                Q.push(v);
            }
    }
}

// Алгоритм Беллмана-Форда

int bfs(int s, int t)
{
    init();
    queue<int> Q;
    mark[s] = 1;
    pred[s] = s;
    push[s] = MAX_VAL;
    
    Q.push(s);
    while( !mark[t] && !Q.empty() )
    {
        int u = Q.front(); Q.pop();
        for(int v = 1; v < N; v++)
            if( !mark[v] && (C[u][v]-F[u][v] > 0) )
            {
                push[v] = min(push[u], C[u][v]-F[u][v]);
                mark[v] = 1;
                pred[v] = u;
                Q.push(v);
            }
    }

    return mark[t];
}

// Алгоритм Форда-Фалкерсона

void max_flow_ff() 
{
    int u, v, flow = 0;

    while( bfs(s, t) )
    {
        int add = push[t];

        v = t; u = pred[v];
        while( v != s )
        {
            F[u][v] += add;
            F[v][u] -= add;
            v = u; u = pred[v];
        }
        flow += add;
    }

    max_flow = flow;
}

// Алгоритм вычисления Максимального поток минимальной стоимости

void min_cost_flow()    
{
    max_flow_ff();
    
    int u, v, flow = 0;
    int add = MAX_VAL;
    int neg_cycle;

    neg_cycle = bf(t);
    while( neg_cycle != MAX_VAL )
    {
        v = neg_cycle; u = pred[v];
        do
        {
            add = min(add, C[u][v]-F[u][v]);
            v = u; u = pred[v];
        }
        while( v != neg_cycle );

        v = neg_cycle; u = pred[v];
        do
        {
            F[u][v] += add;
            F[v][u] -= add;
            v = u; u = pred[v];
        }
        while( v != neg_cycle );

        neg_cycle = bf(t);
    }

    for(int u = 1; u < N; u++)
        for(int v = 1; v < N; v++)
            if( F[u][v] > 0 )
                min_cost += F[u][v] * P[u][v];
}

void file_write()
{
    out << max_flow << endl;
    out << min_cost << endl;
}

void main()
{
    file_read();
    min_cost_flow();
    file_write();
}


* This source code was highlighted with Source Code Highlighter.


// А если бы мы взяли таке условия: вершины – перекрестки улиц, ребра – дороги, пропускная способность – количество полос (разрешенная скорость, и.т.п.) за минусом текущего количества машин на данных дорогах. Найдем максимальный поток от улицы «А» до улицы «Б» — чем не свободные на текущий момент дороги в городе? Конечно, учитывать нужно гораздо больше параметров, но основа – графы. Это интересно. =)

Итого


Не ругайте сильно, пожалуйста,

Начиная пост про графы, я не знал на какой уровень компетенции рассчитывать: решил пока не рассказывать просто про, допустим, Дейкстру, ведь его доступное описание очень просто отыскать в сети. Вдруг его каждый второй пишет наизусть. Но точно помню, что Хабра-товарищей интересовало именно практическая сторона этих алгоритмов. Потому взял «сферическую» задачку и в ее терминах постарался наглядно рассказать про графы.

Надеюсь, что кому-нибудь будет интересно почитать про графы и пример их применения. Более того, написать статью меня еще побудило желание напомнить студентам (школьникам), либо аспирантам, преподающим у них программирование, про одну из самых известных олимпиад по программированию ACM ICPC! Тем, кто еще не решился (не отважился) на ранних курсах университета собрать команду, засиживаться допоздна в компьютерных классах, обсуждать асимптотики алгоритмов, придумывать решения и контр-примеры для них. Алгоритмы – интересно и хороший повод собраться вместе, а опыт командной игры – бесценно. Присоединяйтесь!
Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
Total votes 173: ↑165 and ↓8+157
Comments76

Articles