Транспортная задача (классическая) — задача об оптимальном плане перевозок товара со складов в пункты потребления на транспортных средствах.Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).
Под катом очень-очень много текста, т.к. рассказывается один из вариантов решения данной задачи «в картинках» для тех, кто мало знаком с графами. Листинг прилагается.
На Хабре как-то проскользнула статья, где поднимался вопрос, а нужны ли статьи про основные алгоритмы. Я решил откликнуться на просьбы и немного рассказать про алгоритмы на графах и их практическое применение. Не знал, на какой уровень знаний рассчитывать, поэтому выбрал один относительно сложный и теоретически-практический алгоритм, чтобы статья носила хотя бы отчасти прикладной характер. При этом очень постараюсь рассказать доступно даже для тех, кто не особо знаком с графами.
Задача (сказка): Вы владелец некоторого завода, выпускающего «Товар», и недавно Вам посчастливилось заключить контракт с одной крупной фирмой, находящейся в другом городе на поставку товаров в их розничную сеть. Так как он находится очень далеко (во Владивостоке), товары придется доставлять авиаперевозкой. В ходе телефонных переговоров Партнер поинтересовался «а на какой объем поставок в день мы можем рассчитывать?». Вы задумались… У Вас есть собственные грузовики (дальнобойщики) осуществляющие транспортировку. Аэропорт находится далековато. Просмотрев накопленную статистику перевозок, Вы выявили, что в собственной области при транспортировке есть некоторые ограничения: на дорогах стоят пункты досмотра груза, весового контроля, некоторые дороги и вовсе ремонтируются. Все это назовем «пропускной способностью» дорог в день. Отталкиваясь от этих условий Вам необходимо узнать: сколько ящиков «Товара» в день вы можете подвозить в аэропорт? При этом, вы хотите эффективно вести бизнес и доставлять товар, кратчайшими маршрутами, т.к. это износ шин, механизмов, в общем амортизационные расходы.Итого: сколько ящиков Вы сможете транспортировать в аэропорт в день, учитывая пропускную способность дорог, при этом, чтобы общее расстояние маршрутов было минимальным?
Задача – самая что ни на есть на графах. Решение будет построено постепенно.
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 находит путь от «завода» до «аэропорта»
- провозим по нему ящики
- Пока 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! Тем, кто еще не решился (не отважился) на ранних курсах университета собрать команду, засиживаться допоздна в компьютерных классах, обсуждать асимптотики алгоритмов, придумывать решения и контр-примеры для них. Алгоритмы – интересно и хороший повод собраться вместе, а опыт командной игры – бесценно. Присоединяйтесь!
