Flows and Transportation Networks Part 3

По-специални задачи върху потоци в мрежа


Потоци в мрежи с минимални стойности

Задача: Даден е $G = (N, A, \gamma, b, c)$, търси се $\gamma \phi \rightarrow \min$, където $\phi$ е поток по G със свойствата:

  1. A$\phi$ = 0 (нищо ново);
  2. $b \le \phi \le c$.

Привидно почти нищо не се е променило, имаме само някаква си долна граница на потока по всяка дъга. Да, алгоритъмът за Max-Flow на Ford-Fulkerson работи и за тази модификация на задачата, с малки промени:

  1. $u^+ \mbox{ = (i,j) } \mbox{if u = (i,j)} \in E \mbox{ and } \phi_u < c_u.$
  2. $u^- \mbox{ = (j,i) } \mbox{if u = (i,j)} \in E \mbox{ and } \phi_u > b_u.$

Ето къде идва и трудната част, за да се приложи горното, трябва да разполагаме с начален допустим поток. В стандартната задача това беше нулевия поток, допустим за случая.

Ето и подхода към тази, привидно не толкова трудна задача - намиране на допустим поток. Дефинираме вектор l, където:

(1)
\begin{align} l_u(\phi_u) = \begin{cases} 0 & b_u \le \phi_u \le c_u \\ \phi_u - c_u & \phi_u \ge c_u\\ b_u - \phi_u & \mbox{else} \\ \end{cases} \end{align}

Дефинираме ценовата функция на новата задача като $z = \underset{u \in A} {\sum} l_u(\phi_u) \rightarrow \min$. Ако z = 0, то първоначалната задача има решение, т.е. съществува допустим поток. Ако z != 0, то задачата няма решение.

Решаваме втората задача със следния алгоритъм. Нека за някое $u \in A$ да е дадено, че $\phi_u < b_u$. Оцветяваме u в черно. Всяка дъга $s \in A$ оцветяваме по следния начин:

  1. зелена, ако $\phi_s \ge c_s$;
  2. черна, aко $\phi_s < b_s$;
  3. червена иначе.

Ясно е какво следва… Прилагаме Лемата на Минти, и гледаме какво се получава в двата й случая:

  1. Има цветен сикъл с u. Увеличаваме $\phi = \phi + \epsilon \overset{\rightarrow}{\mu}$. За увеличаване на потока посредством цикъл с такова оцветяване, при $b, c \in \N_M$$ имаме, че сумата на l-овете строго намалява, поне с единица.
  2. Има коцикъл съответстващ на u. Първо да видим при какви условия съществува допустим поток.

i) От закона на Кирхоф имаме, че за всеки връх е в сила : $\underset{u \in \omega^+(i)}{\sum} \phi_u = \underset{u \in \omega^-(i)}{\sum} \phi_u$, $\Rightarrow \underset{u \in \omega^+(A`)}{\sum} \phi_u - \underset{u \in \omega^-(A`)}{\sum} \phi_u = 0$, за всяко $A` \subset A$;
ii) $\underset{u \in \omega^+(A`)}{\sum} c_u - \underset{u \in \omega^-(A`)}{\sum} b_u \ge 0$, това още се нарича капацитет на разреза на A`.

Сега да видим, какво следва от коцикъла - 2. В нашия коцикъл, всички дъги от
$\omega^-(A`)$ са черни, т.е. $\phi_t \le b_t , \forall t \in \omega^-(A`)$, като за началната ни u имаме $\phi_u < b_u$;
$\omega^+(A`)$ са зелени, т.е. $\phi_t \ge c_t , \forall t \in \omega^+(A`)$;
от i) и горните две характеристики на коцикъла следва:
$\underset{u \in \omega^+(A`)}{\sum} c_u - \underset{u \in \omega^-(A`)}{\sum} b_u < 0$, т.е. условие ii) не е в сила, в следствие на което можем да твърдим, че не съществува допустим поток и да прекратим алгоритъма.

От горния алгоритъм следва директно Теорема на Hoffman за допустим поток: За даден граф G = (V, A), и за всяка дъга u от A по две числа bu и cu, такива че $b_u \le c_u$, поток $\phi$, за който $b_u \le \phi_u \le c_u , \forall u \in A$ съществува т.с.т.к. $\underset{u \in \omega^+(A`)}{\sum} c_u - \underset{u \in \omega^-(A`)}{\sum} b_u \ge 0$, за всеки коцикъл $\omega(A`) = \omega^+(A`) \bigcup \omega^-(A`), A` \subset A$.

Minimum Cost Flows

Държа да отбележа, че който има учебника, ще се убеди в завидните ми умения да превеждам дословно технически текст от английски на български, придобити в нетолкова известното 32 софийско СОУ xD. Въпреки красиво написаните, подробни лекции (powered by Мими) и подробния учебник, малко ми е хлабаво, та ако имате учебник или лекции и разбирате като четете от тях, ползвайте ги по предназначение. Дословното копиране свършва при Унгарския алгоритъм, секция по-надолу (и почва пак малко при правия алгоритъм в края ;]).

Задачата: Даден е свързан граф G = (V, U), за всяко u от U имаме реален интервал [bu,cu] и число $\gamma_u$, което ни казва колко струва да пратим единица поток по дъгата u. Ако цената на потока е $z = \gamma \phi = \underset{u \in U}{\sum} \gamma_u \phi_u$, то се търси $z \rightarrow \min$. Ето и ограниченията:

  1. $A \phi = 0$
  2. $\phi \ge b$
  3. $-\phi \ge -c$

Където А е матрицата на инцидентност (затова графът е G = (V, U), да не се бъркат много нещата (както досега ;] )).

Нека $\pi$ е произволен вектор, с големина равна на |V|. Дефинираме относителни цени $\overset{-}{\gamma } = \gamma + \pi A$. Последното може да се разпише и по дъги - $\overset{-}{\gamma_{ij} } = \gamma_{ij} + \pi_i - \pi_j$. Допускаме, че $\overset{-}{\gamma} \ge 0$.

Лема: (Достатъчно условие за оптималност) Ако φ е поток, отговарящ на условия 1, 2 и 3, и ако съществува напрежение $\theta = -\pi A$, такова че:

(2)
\begin{align} (C) \begin{cases} \gamma_u > \theta_u \Rightarrow & \phi_u = b_u\\ \gamma_u < \theta_u \Rightarrow & \phi_u = c_u \\ \gamma_u = \theta_u \Rightarrow & b_u \le \phi_u \le c_u\\ \end{cases} \end{align}

тогава, φ е поток с минимална цена.

А сега да видим нещо доста (не) интересно - Kilter диаграми. С радост бих ги пропуснал, но за да се спрем на out-of-kilter алгоритъма, ще са ни адски нужни.

Да разгледаме дъга u от U и да начертаем в равнината (φu θu) множеството от тези точки ζu (на такова ми прилича), които удовлетворяват условие (С). ζu се нарича Kilter диаграмата на дъгата u.
killtershitogramnd8.png

В зависимост от позицията на точката (φu θu) в релацията ζu, ще различаваме (само) 7 различни типа дъги:

  1. $\gamma_u > \theta_u$ и $\phi_u = b_u$;
  2. $\gamma_u = \theta_u$ и $b_u < \phi_u < c_u$;
  3. $\gamma_u < \theta_u$ и $\phi_u = c_u$;
  4. $\gamma_u = \theta_u$ и $\phi_u = b_u$;
  5. $\gamma_u = \theta_u$ и $\phi_u = c_u$;
  6. $\gamma_u < \theta_u$ и $\phi_u < c_u$;
  7. $\gamma_u > \theta_u$ и $\phi_u > b_u$;

Като първите 5 се водят in-kilter дъги, а последните 2 - out-of-kilter дъги. От лемата следва, че ако всички дъги са от тип in-kilter, то потокът φ е оптимален. Какво ни грее нас това? Ами за всяка дъга ще ръчкаме или напрежението, или потока, докато не стане in-kilter.
За всеки съвместим поток φ и напрежение θ дефинираме kilter индекс на дъгата u от U да е количеството:

(4)
\begin{cases} (\gamma_u - \theta_u)(\phi_u - b_u) & if \theta_u < \gamma_u\\ (\theta_u - \gamma_u)(c_u - \phi_u) & if \theta_u > \gamma_u\\ 0 & if \theta_u = \gamma_u\\ \end{cases}

Интересното в тези kilter индекси, е че сумата им е равна на разликата между правата задача и двойнствената й, тоест между лявата и дясната страна на неравенство (I) от доказателството на лемата.
Алгоритъм 2 - out-of-kilter алгоритъм за min-cost max-flow

Целта на алгоритъма : на всяка стъпка се грижим поне за една дъга да сме намалили kilter индекса, а за никоя друга да не сме го увеличили.
Нека φ е сегашния поток, а u0 = (t, s) една дъга out-of-kilter (тук няма логика да са сложили точно дъгата, по която отчитаме размера на потока - дъгата от консуматора към източника, но така са го написали…). Ако няма такава дъга (Out-of-kilter), то потока е оптимален.
Нека предположим, че дъгата е от тип 6. Правим ето какво оцветяване на дъгите в G:

(5)
\begin{align} u = \begin{cases} red & if \mbox{ u is of type 2}\\ black & if \mbox{ u is of type 4 or 6}\\ green & if \mbox{ u is of type 5 or 7}\\ uncolored & if \mbox{ u is of type 1 or 3}\\ \end{cases} \end{align}

От предположението, че u0 e от тип 6, то тя е черна.
killtershitogram2ao9.png
Следва да дефинираме промените, за всяка дъга u, които биха довели до не-увеличаване на kilter индекса на u.

величина поток напрежение
цвят - - -
червен - увеличаване и намаляване не може да се променя
черен - само увеличаване само намаляване
зелен - само намаляване само увеличаване
без цвят - не може да се променя увеличаване и намаляване

Ето как изглежда това на диаграма:

killtershitogram3cw1.png

От лемата на Минти, имаме точно 2 случая за u0.:
a) Има цветен ориентиран цикъл, минаващ през u0. Тогава взимаме остатъчният капацитет ε на цъгите от цикъла:
$\epsilon_1 = {min}\{ c_u - \phi_u\}, \forall \mbox{ u black or red}$
$\epsilon_1 = {min}\{ \phi_u - b_u \}, \forall \mbox{ u green or red}$
$\epsilon = min\{ \epsilon_1, \epsilon_2\}$
и увеличаваме φ = φ + εμ-- е вектора съответстващ на цикъла μ). Kilter индексът не се увеличава за никоя дъга от μ (защото сме се движили съобразно таблицата), а за u0 строго намалява.

б) Съществува коцикълът от лемата - ω(X), който съдържа u0. Имаме, че s ∈ X, t ∉ X. В този случай, ще променим потенциалите $\pi_i (i \in \overset{-}{X})$ с една и съща стойност ε, такава че за никоя дъга да не увеличим kilter индексът си, а поне една дъга го намали.
За дъгите извън ω(X), напрежението остава непроменено. За всяка дъга u от ω+(X), напрежението θu се увеличава с ε, за всяка дъга u от ω-(X), напрежението θu се намалява с ε.
Следователно, трябва да имаме

(6)
\begin{cases} \epsilon \le \theta_u - \gamma_u & \mbox{for u of type 3 or 6}\\ \epsilon \le \gamma_u - \theta_u& \mbox{for u of type 1 or 7}\\ \end{cases}

За всяко u от ω(X). Тогава за
$\epsilon_1 = {min}\{\theta_u - \gamma_u\}, \forall \mbox{ u of type 3 or 6}$
$\epsilon_2 = {min}\{\gamma_u - \theta_u\}, \forall \mbox{ u of type 1 or 7}$
$\epsilon = min\{ \epsilon_1, \epsilon_2\}$

Общата сума на kilter индексите строго намалява и поне една дъга е сменила типа си. Продължаваме така, докато всички дъги не станат in-kilter.
Забележка: Ако bu и cu са целочислени, алгоритъмът е сходим след краен брой стъпки. Ако всички величини са целочислени, то и kilter индексите са целочислени и за всяка стъпка имаме намаляване на сумата им поне с единица.

Графи без минимален капацитети по дъгите. Transshipment, transportation problems.

Твърдение: В началната задача, ако заменим $\gamma$ с $\overset{-}{\gamma}$, където $\pi$ е произволен вектор, такъв че $\overset{-}{\gamma} \ge 0$, то поток оптимален спрямо $\gamma$ е оптимален и спрямо $\overset{-}{\gamma}$.

Следствие: Ако подберем $\pi$ такъв, че се получат повече дъги с нулеви цени, то всеки валиден поток в каноничния граф G ще е оптимален.
Забележка: Каноничен граф на графа G = (X⋃Y , U, γ ) ще наричаме граф ca(G) = (X⋃Y ⋃ {s, t}, U`), където:

(7)
\begin{align} U` = \begin{cases} (i, j) & \forall (i,j) \in U\\ (s, i) & i \in X \\ (j, t) & j \in Y \\ \end{cases} \end{align}

На базата на горното твърдение, се формира и право-двойнствения алгоритъм за решаване на задачата, още известен като Унгарски алгоритъм.

Унгарски алгоритъм за максимално по цена двойкосъчетание в двуделен граф

За нуждите на алгоритъма, ще дефинираме частичния граф $\overset{-}{G} = (V, \overset{-}{U})$, такъв, че в $\overset{-}{U} = \{ (i,j) | \overset{-} {\gamma_{ij} } = 0 \}$. От неотрицателността на $\overset{-} {\gamma}$, следва, че $U/ \overset{-}{U}$ е съставено само от дъги с положителни цени.

  1. намираме $\overset{-}{\gamma } = \gamma + \pi A \ge 0$;
  2. създаваме $\overset{-}{G} = (V, \overset{-}{U})$;
  3. на $\overset{-}{G}$ създаваме каноничния еквивалент - $ca( \overset{-}{G})$;
  4. търсим $\underset{ca( \overset{-}{G}) }{max} \phi$. Нека максималния поток в $ca( \overset{-}{G})$ е $\overset{-}{\phi}$. Aко $\overset{-}{\phi}$ е максималния, който може да се достигне в G (максималния поток може да бъде намерен например, като напълно се игнорират цените на дъгите в графа), то край на алгоритъма. Иначе отиди на 5.
  5. намираме $\epsilon = \underset {(i, j) \in U/ \overset{-}{U}}{min} \overset{-}{\gamma_{i,j}} $$ , $$ \epsilon > 0$.

За всички i, които имат етикет спрямо $\overset{-}{\phi}$, намаляваме $\pi_i = \pi_i - \epsilon$
Отиди на 3.

Ето и алгоритъма върху примерна задача: Дадени са N работника и N работи (в нашия пример N = 4), където с матрица с неотрицателни стойности е отбелязана цената, за i-ия работник да бъде нает да свърши j-та работа, като изискването е на всеки работник да бъде дадена точно една работа и общата цена за наемане на всички работници да е минимална.
Пример:

5 7 3 8
10 18 2 7
3 2 8 15
11 7 5 13

Минаваме и вадим от всеки ред най-малката цена, намерена в него. Числата, които вадим в нашия случай са : -3, -2, -2, -5 (съответно по редове), тоест $\pi$ = {-3, -2, -2, -5, 0, 0, 0, 0,}. Ето какво получаваме:

2 4 0 5
8 16 0 5
1 0 6 13
6 2 0 8

След като пуснем flow-a, ще видим че минималния брой черти с които да задраскаме всички нули, е 2. Cover-a на нулите е 3-и ред и 3-и стълб. ε от останалата таблица, е 2, вадим и получаваме:

0 2 0 3
6 14 0 3
1 0 8 13
4 0 0 6

Забележете, че на мястото, където се пресичат избран в cover-a ред и стълб, сме прибавили ε. Това е защото, сме променили само $\pi_j$ в $\overset{-}{\gamma_{ij} } = \gamma_{ij} + \pi_i - \pi_j$.
След второ пускане на flow-a, вече cover-a е 3. Продължаваме, докато не достигнем поток $\overset{-}{\phi}$ с $\overset{-}{\phi_0}$ = 4. Цената за наемане на работниците, е сбора от цените $\gamma_{i,j}$ за дъгите с положителен поток по тях във $\overset{-}{\phi}$.

Примерна задача : http://acm.timus.ru/problem.aspx?space=1&num=1076. (Който не е решавал задачи от online judge-ове досега, да не се обезсърчава, ако не се получава лесно - грешен отговор или time limit, в случая важен е и опита. Дори 5-6 минати теста са някакъв успех.)

Прав алгоритъм за Minimum cost flows with lower and upper bounds

Задача: Отново G = (V, U) е свързан граф, чийто дъги имат две числа - cu и bu , съответно горна и долна граница на поток по тях, освен това има и γu - цена за пренасяне на единица поток по дъгата u. Търсим поток φ, който е съвместим (тоест bu ≤ φu ≤ cu) и който има най-малка цена
$\gamma \phi = \underset{u \in U}{\sum}\gamma_u \phi_u$.

Ето и самият алгоритъм:

i) k = 0. Търсим съвместим поток φ0 с алгоритъма от началото на темата.

  1. Не съществува съвместим поток φ0. Край, задачата няма решение.
  2. Иначе продължаваме с ii)

ii) На стъпка k сме, текущия поток е φk. Нека с $\overset{-}{G}(\phi^k)$ означим инкременталния граф съответсващ на φk. На дъгите от инкременталния граф съответстват следните цени $\overset{-}{\gamma}$ и капацитети $\overset{-}{c}$:

  1. ако u = (i, j) ∈ U и bu ≤ φu < cu, тогава дъгата u+ = (i, j) има цена $\overset{-}{\gamma_{u^+}} = \gamma_u$ и капацитет $\overset{-}{c_{u^+}} = c_u - \phi_u > 0$;
  2. aко u = (i, j) ∈ U и bu < φu ≤ cu, тогава дъгата u- = (i, j) има цена $\overset{-}{\gamma_{u^-}} = -\gamma_u$ и капацитет $\overset{-}{c_{u^-}} = \phi_u - b_u > 0$;

iii) Търсим в инкременталния граф $\overset{-}{G}(\phi^k)$ цикъл μ с отрицателна цена спрямо , $\overset{-}{\gamma}$. Важно е да дефинираме, какво ще разбираме под цикъл с отрицателна дължина - това е цикъл, на който произведението $\overset{-}{\mu} \gamma < 0$, където

(8)
\begin{align} \overset{-}{\mu}_i = \begin{cases} 0 & i = (s, t) \in \mbox{ E and i} \notin \mu\\ 1 & i = (s, t) \in \mbox{ E and i} \in \mu\\ -1 & i = (s, t) \in \mbox{ E and i`=(t, s)} \in \mu\\ \end{cases} \end{align}

Ако съществува такъв цикъл, тогава намираме
$\epsilon = \underset{(i,j)\in \mu}{min}\overset{-}{c}_{ij}$
Тоест ε е остатъчния капацитет по цикъла μ. Тогава дефинираме φk + 1 = φk + ε μ-, където μ- е вектора на μ.
k = k + 1, отиваме на ii).

Ако не съществува μ, то сме открили оптималния поток, край на алгоритъма.

Сходимостта на алгоритъма следва от следната теорема:
Теорема: Поток φ, съвместим с долните и горните граници по дъгите, е минимален по цена ⇔ не съществува цикъл с отрицателна цена спрямо $\overset{-}{\gamma}$ в инкременталния граф $\overset{-}{G}(\phi)$.

Последният алгоритъм е по-популярния (спрямо право-двойнствения вариант по-горе) , според създателите на учебника ни. Около имплементацията му, обаче има малко неприятния момент на търсене на цикли с отрицателна дължина, подзадача с трудност O(N3).

Съвет, какво да правите ако ви се падне въпрос "Потоци с минимална цена"

Имате право на избор (поне на нас първия ден ни даде такова), или да напишете првия, или право двойнствения.

  • ако сте избрали право-двойнствения (алгоритъм 2 и частния му случай - Унгарския алгоритъм), УСПЕХ!
  • ако сте избрали правия (последния алгоритъм в темата), трябва да напишете и част-та от първия алгоритъм в темата, свързана с намиране на допустим поток.

Това е само съвет! Със сигурност няма да изгубите да знаете повече, а и кой знае, може да си е променил методите на изпитване и оценяване за 1 седмица.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License