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

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

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

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


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

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

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

    Задача – самая что ни на есть на графах. Решение будет построено постепенно.
    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! Тем, кто еще не решился (не отважился) на ранних курсах университета собрать команду, засиживаться допоздна в компьютерных классах, обсуждать асимптотики алгоритмов, придумывать решения и контр-примеры для них. Алгоритмы – интересно и хороший повод собраться вместе, а опыт командной игры – бесценно. Присоединяйтесь!
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 76
    • +11
      Это очень круто. К сожалению графы и поиски оптимального [чего-либо] это слабое место многих программистов, а ведь это основа основ.
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          У нас идет курс Математические Модели в Экономике. Тоже решаем подобные задачи: о комивояжоре, задача о рюкзаке, транспортная задача, сеть и другие.
        • +9
          Когда-то программистами называли людей, умеющих решать подобные задачи, а не только умеющих писать скриптики на пхп.
          • 0
            На учебе я решаю подобные задачи на php (теория принятия решений, моделирование систем). На том же php пишу проекты на работе.
            • НЛО прилетело и опубликовало эту надпись здесь
              • НЛО прилетело и опубликовало эту надпись здесь
                • +3
                  раздвоение личности?:)
                  • НЛО прилетело и опубликовало эту надпись здесь
        • +1
          Да, помню контесты по 5 часов…
          Жаль сейчас в другой сфере.
          • +1
            >Под катом очень-очень много текста
            Ну зачем же так людей пугать? :)
            • +1
              Ах, мой первый курсовой проект ^_^
              • –5
                Транспортные задачи не только один из моих курсовиков, но и диплом — через неделю защищать.
                По сабжу — реально много текста, не стал читать. Но на графах не представлял эту задачу, только табличный метод. Хотя согласен, многие из них на графе проще решать.
                • +1
                  Курсач? Диплом? У меня транспортная задача (равно как и все алгоритмы поиска по графам, задача комивояжера, симплекс-метод) были простыми лабами на 1-2 пары. Что там писать на курсач или диплом? Реализация от силы 300-400 строк занимает.
                  • 0
                    Курсовой проект. Делается 1 семестр.
                • +2
                  Кстати, думаю большинство кому нужно знают, но для меня когда-то очень полезным открытием оказалась книга Роберта Седжвика — Фундаментальные алгоритмы на С++, а конкретно в данном случае ее пятая часть посвященная графам.
                  Может кому еще поможет в их изучении
                  • +1
                    Спасибо большое! Отличная книжка! Я сам с нее писал свои заготовки многих алгоритмов на ACM ICPC. Очень короткие получались. =)
                  • +2
                    направленные/ненаправленные графы
                    вроде графы называются ориентированные/неориентированные?
                    • +3
                      это не существенно, вообще в теории графов существует много чего что именуется всеми по-разному, главное что-бы логически верно воспринималось.
                    • +1
                      А я вот веду разработку решения задачи о укладке плоского графа, если есть интерес, давайте кооперироваться.
                      • 0
                        на эту тему могу посоветовать статью Efficient Planarity Testing portal.acm.org/citation.cfm?id=321852 (если нет доступа, могу послать pdf), этот же алгоритм значительно подробнее описан в книге «Комбинаторные алгоритмы. Теория и практика» авторы Э. Рейнгольд, Ю. Нивергельт и Н. Део, издательство «МИР» 1980
                        • 0
                          Спасибо, статья есть, а вот книгу сейчас поищу.
                      • +2
                        Оо, спасибо! А то в университете этот предмет как-то не особо посещал, нужно совершенствоваться, спасибо!
                        • +6
                          Преподаю студентам дискретную математику, как вы получили такие классные иллюстрации? это какая-то обучающая программа или вы «ручками», спасибо
                          • +5
                            Очень просто MS Visio + «ручки»…
                            Уж очень хотелось сделать что-нибудь полезное. Потребовалась неделя!

                            А Вам огромное спасибо! за то что прочитали, очень рассчитываю что кто-нибудь из Ваших студентов заинтересуется ACM ICPC =)
                            • +3
                              Когда-то для них написал несколько апплетов на Java, демонстрирующих разные алгоритмы на графах, вот здесь посмотрите (не пугайтесь это чешский :), но теперь понимаю КАК можно было все оформить :)

                              Региональный ACM у нас проводится, да не хватает чехам русской/советской школы )
                          • +1
                            Чертовски много текста, но спасибо. Впреть буду знать где искать информацию по теме, а то в универе благополучно прогулял все лекции по Методам оптимизации… (чем, впрочем, отнють не горжусь).

                            И да, отличные иллюстрации с графами! Сразу видно, душу вложили…
                            • +1
                              <grammar nazi>
                              отнюдь = вовсе нет
                              </grammar nazi>
                            • +1
                              Очень неплохо. Материал нескольких лекций, дом. заданий и одной из шести практик за семестр по основам информатики — в одной статье.
                              • +1
                                мы в универе проходили форда-фалкерсона (предмет «Сети ЭВМ...»)… ох как я его люто бешено ненавидел, но когда разобрался и понял — стал боготворить. текста не на самом деле не много, кода больше :)
                                • +3
                                  Большой плюс за великолепное оформление!
                                  Просто образцовый пост!
                                  • +1
                                    Весьма польщен! =) Огромнейшее спасибо! =)
                                  • +1
                                    Я заставлю себя это прочитать и понять! :)
                                    • +1
                                      Дмитрий, спасибо. Изложение шикарное.
                                      • 0
                                        Благодарю за Ваш отзыв! Очень старался! Спасибо! =)
                                    • +1
                                      Попробуйте лучше симплекс-метод — более универсальный алгоритм и подходит не только для транспортной задачи. У меня лет 8 назад был заказ — оптимизировать производство мороженого: смысл в том что в готовом мороженом должно содержаться определенное кол-во различных веществ таких, как сухой молочный остаток, жир, влага и сахар и еще кажись что то. И есть набор сырья, содержащий эти вещества в разных пропорциях, а так же имеющиеся на складе в разных кол-вах и имеющих разную себестоимость. Например, можно положить сгущенку, немного воды и немного масла, а можно сухое молоко, сахар, воды и много масла. Так вот при помощи симплекс метода — задача была решена. Каждый день выдавалась оптимальная рецептура, да и выдается до сих пор
                                      • НЛО прилетело и опубликовало эту надпись здесь
                                        • +1
                                          Неправильно тебе известно — симплекс метод тоже можно отнести к дискретной математике (хотя предмет назывался «Начало анализа») — а она большинство задач решает перебором (примеры в топике это доказывают). Смысл различных методов решения различных задач в дискретной математике достичь решения за как можно меньшее кол-во переборов
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                            • 0
                                              Насколько я помню, симплекс-метод больше заточен под поиск екстремума линейных(квадратичный — нелинейных) функций от многих переменных при ограничениях на фазовое пространство. ИМХО, теория графов служит немного другим целям. Хотя все, естественно, зависит от формализации поставленной задачи.
                                            • +1
                                              У Вас странное представление о теории сложности, Вы путаетесь в терминологии.

                                              Вкратце, симплекс-метод (в среднем) работает за полиномиальное время, так же и память. Есть, впрочем, другие методы линейной оптимизации, которые работают строго за полиномиальное время, но они сильно сложнее в понимании/реализации.
                                            • 0
                                              Насколько я понял условие задачи. Я бы счел ее «Задачей о назначениях» и решал бы ее «Венгерским алгоритмом». Вы натолкнули меня на мысль! Попробую описать Венгерку в картинках в след. статье! Спасибо! =)
                                              • +1
                                                Кстати, было бы просто здорово! Так и не сумел разобраться в настолько, чтобы писать ее просто и по памяти, надеюсь, с вашим прекрасным изложением это удастся.=) Между прочим, а не подскажете ли литературу, в которой можно поразбирать задачу о назначениях и примеры порешать, для experience?
                                                • 0
                                                  Кое что можно взять из «Operations Research» за авторством Hamdy A. Taha, в том числе список специализированной литературы по любой подобной теме.
                                                  • 0
                                                    Спасибо, поизучаю на досуге, тем более давно эту книгу почитать советовали.)
                                                • 0
                                                  Ну, венгерский алгоритм основан на симплекс-методе, потому и часто (на практике) так же и интерпретируется.

                                                  А вы, кстати, никогда не пробовали решения подобных задач доверить генетическим алгоритмам?
                                                  • 0
                                                    В олимпиадном программировании им нельзя доверять… И в жизни, нередко, требуется точное решение, тем более, что оно (в данном и многих других случаях) получается быстро и наверняка.
                                              • –3
                                                У вас недостаточно заряда для голосования
                                                • 0
                                                  P.S. если уж понижаете карму, то хоть говорите за что :( а то уж очень обидно! Легко тихо отминусовать и пройти дальше!
                                                • –3
                                                  У вас недостаточно заряда для голосования — у меня то же самое. А ты бы проголосовал за.
                                                  • –3
                                                    > А ты бы проголосовал за.
                                                    Исправь «ы» на «а» или поставь знак вопроса :-)
                                                  • 0
                                                    У нас на первом курсе в качестве курсового проекта была примерно такая же задача :)
                                                    Просто великолепная статья, как и в плане описания, так и в плане оформления, можно смело копи+паст и сдавать )
                                                    • +1
                                                      Хорошая статья спасибо!
                                                      • +4
                                                        Получится значительно меньше кода, если не искать сначала максимальный поток, и потом понижать его стоимость, а каждый раз искать наиболее легкий путь в остаточной сети. Этот способ поддерживает инвариант, что на каждом шаге текущий поток самый дешевый из потоков такой же величины.

                                                        Вот еще несколько наблюдений:
                                                        видимо, у вас перепутаны комментарии в коде около функций bf() и bfs();
                                                        похоже, что ваш код неправильно работает в орграфах со встречными дугами;
                                                        вы N увеличили вначале, чтобы не писать "<="?.. очень странный ход, лучше перейти к 0-индексации.

                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                          • +1
                                                            +1 (что-то не так с комментариями в коде около функций bf() и bfs())
                                                            • 0
                                                              Спасибо! =)

                                                              Да, действительно. Я комментарии к ним перепутал местами.
                                                              Решил потом не поправлять — по честному с первой попытки (с авторской ошибкой).
                                                              Пусть будет мини-квест для внимтельных читателей (коим Вы оказались) =)
                                                          • +1
                                                            Добавил в избранное. Ибо пары по теме прогулял но информация очень интересна, а времени сейчас нет т.к. диплом на носу.
                                                            • –1
                                                              Возможно напишу что-то ужасное, но когда у нас был целый семестр дискретной оптимизации, мы решали и эту и еще ряд других задач на графах, используя модифицированную структуру вирта.

                                                              Поищите в сети, дядя Вирт ее специально для графовых задач придумал. Только изначально она была у него так себе, а потом ее модифицировали.

                                                              Точно не помню, как она описывалась, но, по-моему, там был список всех вершин, и в каждой ячейке списка хранился список смежных для текущей вершин. Обходы по этому списку, создание матриц и алгоритмы писались на ура. Главное было в самом начале грамотно спроектировать классы, которые описывали бы структуру вирта.
                                                              • 0
                                                                По вашему описанию, это просто списки смежности.
                                                            • 0
                                                              Хех, вспомнил прошлую сессию — как раз экзамен по сетевой экономике :)
                                                              • +1
                                                                Хм… После трех лет занятия олимпиадами могу написать Форда-Фалкерсона за двадцать минут, даже если разбудят посреди ночи пистолетным выстрелом.

                                                                П.С. Извините за занудство, но Форд-Фалкерсон — это не алгоритм, а метод. А вот Беллман-Форд уже его реализация в виде алгоритма.
                                                                • 0
                                                                  Не совсем понятно, к чему вы это… Много людей умеют реализовывать метод Форда-Фалкерсона. Это вовсе не означает, что его не нужно никому объяснять.
                                                                  Вообще, в статье действительно как-то многовато слова «алгоритм», но все же автор указал, что показывает реализацию Эдмондса-Карпа. А вот с Беллманом-Фордом, наверное, очепятались — это вообще несколько другое.
                                                                • 0
                                                                  Где ж вы раньше были, а то я вспоминал ТИЛС из универа, когда карту дорог строил, ох и намучался :)
                                                                  • +1
                                                                    Можно небольшое разъяснение?
                                                                    «Алгоритм поиска в ширину (breadth first search), BFS»
                                                                    на первом рисунке на последнем шаге мы смотрим из 4й вершины на 7ю и 8ю, и там даже два квадратика «в конце итерации» 7 и 8. Так почему на втором рисунке восьмёрка красная? Мы же не можем в восьмерку попасть из семерки или шестерки, мы там были уже после четверки…

                                                                    а в остальном вроде всё доступно написано, спасибо за статью!
                                                                    • 0
                                                                      Да. Спасибо за Вашу наблюдательность.
                                                                      Ошибся в иллюстрации. Извините за «ляп». =)
                                                                    • –1
                                                                      вот на транспортную задачу я убила весь прошлый день и ночь. захожу с утра (наконец-то выспавшись) на хабр — и тут опять это! >_<
                                                                      а по теме — отличная статья!
                                                                      • +2
                                                                        Было бы интересно увидеть статьи про симплекс-метод и венгерский алгоритм. И, наверно, напрасно вы используете матрицы смежности — они не сильно нагляднее, но чаще медленнее (на разреженных графах).
                                                                        • +1
                                                                          Вот побольше бы таких статей, может в конце концов и прав будет Дон Тэпскотт насчет того, что университеты в том виде, что они сейчас — отомрут.
                                                                          • +1
                                                                            уф… аж ностальгия по институтским временам! «Задача коммивояжера» Спасибо огромное!
                                                                            • +1
                                                                              Отлично, спасибо
                                                                              • +1
                                                                                хорошая, годная статья.
                                                                                • 0
                                                                                  Под катом увидел немного не то, что ожидал. Дело в том, что в классическом понимании «транспортная задача» линейного программирования решается составлением матрицы перевозок, а не через графы.
                                                                                  • 0
                                                                                    Ага, я тоже удивился, не увидев в статье знакомого способа :)
                                                                                  • 0
                                                                                    А вот это 5 баллов. Это вам не описание транспортной задачи в два клика в Excel )

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