Пользователь
0,0
рейтинг
13 июня 2009 в 00:46

Разработка → Максимальный поток минимальной стоимости

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

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

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


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

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

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

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

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (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
        Вот, нашел, чуть вниз промотайте и увидите структуру Вирта. Там над ней как раз граф нарисован из 5-ти врешин, который она представляет: Модифицированные структуры Вирта
  • 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 )

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