Поняття потокових алгоритмів

Поняття потокові алгоритми включає в себе ряд алгоритмів.

1) Алгоритм пошуку збільшую чого ланцюга.

Основна ідея алгоритму: побудова дерева, що росте з вершини “s” і складається з розфарбованих дуг, по яких з вершини “s” можуть пересилатись додаткові одиниці потоку.

В процесі виконання алгоритму можуть виникнути дві різні ситуації: а) стік “t” є розфарбованим???, тоді в побудованому з розфарбованих дуг дереві єдиний ланцюг з “s” в “t” є збільшуючим потік ланцюгом; б) стік “t” не вдається розфарбувати, що означає: що у вихідній сітці не існує збільшуючого ланцюга між “s” і “t” .

2) Алгоритм пошуку максимального потоку.

Основна задача алгоритму пошуку максимального потоку полягає в пошуку способів пересилання максимальної кількості одиниць потоку з витоку в стік при умові відсутності перевищення пропускних здатностей дуг вихідного графа. В основі алгоритму пошуку максимального потоку лежить наступна ідея: вибираємо початковий потік з витоку “s” в стік “t”, потім використовуємо алгоритм пошуку збільшуючого ланцюга. Цей алгоритм дозволяє знайти єдиний збільшуючий ланцюг з “s” в “t”, якщо той існує. Послідовність, в якій повинні розфарбовуватись вершини і дуги, конкретно не визначається. Тому можливі два варіанти розфарбування вершин і дуг: 1) вибирається яка-небудь вершина, а потім проводиться розфарбування максимальної кількості вершин; 2) проводиться розфарбування, виходячи з останньої розфарбованої вершини. Який саме спосіб розфарбування буде вибраний, буде залежати від характеру більш загальної задачі, тобто від алгоритму пошуку максимального потоку, який в якості підалгоритму використовує алгоритм пошуку збільшуючого ланцюга. Якщо пошук збільшуючого ланцюга вдалий, тобто знайдено збільшуючий ланцюг з “s” в “t”, то за допомогою алгоритму пошуку максимального потоку здійснюється максимально можливе збільшення потоку вздовж знайденого ланцюга. Потім повторюється пошук нового збільшуючого ланцюга і т.д. Виконання алгоритму завершується за скінчене число кроків, коли ланцюг, що збільшує потік, знайти не вдається: це означає, що біжучий потік з “s” в “t” є максимальним.

3) Алгоритм пошуку потоку мінімальної вартості.

Дана задача полягає в організації пересилання з мінімальними витратами заданої кількості v одиниць потоку з витоку в стік в графі з заданими на дугах пропускними здатностями і вартостями проходження одної одиниці потоку.

4) Алгоритм дефекту.

Основна ідея алгоритму: рішення задачі про потік мінімальної вартості, але на відміну від попереднього алгоритму алгоритм дефекту вирішує задачу про потік мінімальної вартості у випадку, коли найменша кількість одиниць потоку, яка повинна протікати по дузі, більша або рівна 0 для всіх дуг.

5) Алгоритм пошуку динамічного потоку.

Попередні алгоритми використовували потоки, які задовольняли деяким умовам, які визначались заданими на дугах пропускними здатностями і вартостями. Даний алгоритм використовує сітки, дуги яких характеризуються ще одним показником - часом проходження потоку (кожна одиниця в цих потоках проходить з витоку в стік за час, що не перевищує заданий).

6) Потоки з підсиленням.

Попередні розгляди потоку показували, що потік не змінювався: одиниця ввійшла - одиниця вийшла. При проходженні потоку через дугу нові одиниці не створювались, але і старі не щезали. Потоки з підсиленням усувають припущення, згідно якого при проходженні по дугам потік залишається незмінним. Висувається припущення, що кількість одиниць в потоці, що проходить по дузі, може збільшуватись або зменшуватись. Точніше, вважають, що якщо в будь-яку дугу (х,у) в вершині “х” входить f(x,y) одиниць потоку, то з цієї дуги в вершині “у” вийде k(x,y)f(x,y) одиниць потоку. Можна вважають, що кожна одиниця потоку, що проходить по дузі (x,y), помножується на величину k(x,y) (яка називається підсиленням дуги (x,y).

ПРИКЛАД РОБОТИ АЛГОРИТМУ ПОШУКУ ЗБІЛЬШУЮЧОГО ЛАНЦЮГА

Як було сказано вище, алгоритм знаходить перший збільшуючий ланцюг, якщо той існує. Процедура розфарбування буде організована таким чином, що розфарбування наступної вершини буде проводитись виходячи з останньої розфарбованої вершини.

_{Нехай задано граф, що має наступний вигляд(рис.4):}

_R

_IR ^{a b}

^R I

R

^S _I ^{N t}

N ^R c ^d

IR

Рис.4.

(поряд з дугами графа вказані букви І,R,N, що визначають, до якої множини належать відповідні дуги)

Насамперед розфарбовується вершина “s” (початкова вершина). З вершини “s” може бути розфарбована вершина “а” і дуга (s,a), оскільки (s,a) І. Розфарбовані вершини запам’ятовуються в масиві збільшуючих ланцюгів в порядку їх роçфарбування. З вершини “а” не можуть бути розфарбовані вершина “b” і дуга (a,b), оскільки (а,b) І. Вершина “с” і дуга (а,с) можуть бути зафарбовані, оскільки (а,с)І. Вершина “d” і дуга (d,a) можуть бути розфарбовані з вершини “а”, оскільки (d,а)  N. Це завершує процедуру зафарбовування з вершини “а”.

Далі будемо зафарбовувати вершини і дуги з вершини “b”. Вершини “а”, “с” і “d”, які вже розфарбовані, можна вже не розглядати. З вершини “b” може бути розфарбована вершина “t” і дуга (b,t), оскільки (b,t) є І.

Отже збільшуючим ланцюгом з “s” в “t” є (s,a), (a,с), (b,c), (b,t), в якому максимальне

_{збільшення потоку по цьому рівне min{i(s,a), i(a,c),r(b,c), t(b,t)}}

_{На цьому процедура розфарбування}

^{a b}

завершується, оскільки виявляється розфарбованою

вершина “t”. Підграф, що складається з ^{S t}

розфарбованих вершин і дуг, має вигляд зображений _{c d}

_{на рис. 5.}

Рис.5.

ПРИКЛАД РОБОТИ АЛГОРИТМУ ПОШУКУ МАКСИМАЛЬНОГО ПОТОКУ

Крок 1. Алгоритм починається з задання нульового потоку, тобто для всіх дуг (х,у)

графа, що розглядається, задають f(x,y)=0.

Крок 2. Оскільки для всіх дуг f(x,y)=c(x,y), кожна дуга може бути віднесена до множини І, при цьому і(x,y)=c(x,y)-f(x,y)=c(x,y). Оскільки f(x,y)=0, тому на цьому кроці ні одну з дуг неможливо включити в множину R.

Крок 3. Використовується алгоритм пошуку збільшуючого ланцюга для визначення відповідного ланцюга з “s” в “t”.

З прикладу (рис. 6) видно, що у графі є декілька таких збільшуючих ланцюгів: sabt, sact, sbact, sbt.

I _S I _a

_I

c _I

^RI _b I _t

S a S 0 2 a 0 0 b 0 2 c 0 0 t 0 0

b c t

5 0 0

3 4 0

0 0 2

0 0 1

0 0 0

Рис.6

Допустимо, що у використаному алгоритмі на даному кроці формується ланцюг sabt. Максимальне збільшення потоку по цьому ланцюгу

min{i(s,a), i(a,b), i(b,t)=min{2,3,2}=2.

Отже потік в цих трьох дугах збільшиться на дві одиниці. Після цього переходимо на крок 2.

Крок 2. Для нових значень потоку в дугах вхідного графа перераховуються величини і(х,у) і r(x,e); окрім цього, коректуються множини I і R:

f(s,a)=2=c(s,a) (s,a) I (s,a) R, r(s,a)=2, f(a,b)=2<c(a,b) (a,b)I, i(a,b)=1 (a,b) R, r(a,b)=2, f(b,t)=2=c(b,t) (b,t) I (b,t)  R, r(b,t)=2, f(s,b)=0<c(s,b) (s,b)I, i(s,b)=3 (s,b) R, f(a,c)=0<c(a,c) (a,c)I, i(a,c)=4 (a,c) R, f(c,t)=0<c(c,t) (c,t)I, i(c,t)=1 (c,t)  R.

Крок 3: Знову використовується алгоритм пошуку збільшуючого ланцюга для визначення відповідного ланцюга з “s” в “t”. В даному випадку ланцюг, що збільшує потік, єдиний - це ланцюг (s,b), (b,a), (a,c), (c,t). Його і формує алгоритм. Максимально можливе збільшення потоку вздовж знайденого ланцюга дорівнює:

min {i(s,b), r(a,b), i(a,c)} i(c,t) = min {5,2,4,1} = 1

Таким чином, з вершини “s” в вершину “t“ може бути додатково пропущена одиниця потоку. При цьому значення потоку в кожній з трьох прямих дуг (s,b), (a,c) i (c,t), що належать знайденому ланцюгу, на одиницю збільшується, а значення потоку в зворотній дузі (a,b) цього ланцюга на одиницю зменшується. Тепер потоки в дугах графа, що розглядається, будуть мати наступні значення:

f(s,a)=2, f(a,b)=2, f(b,t)}=2, f(s,b)=1, f(a,c)=1, f(c,t)=1.

Кожна з цих трьох одиниць побудованого до цього моменту потоку проходить по наступним маршрутам:

1 одиниця проходить з “s” в “t” по шляху (s,a), (a,b), (b,t);

1 одиниця проходить з “s” в “t” по шляху (s,b), (b,t);

1 одиниця проходить з “s” в “t” по шляху (s,a), (a,c), (c,t)

Далі здійснюється повернення до кроку 2.

Крок 2. Для нових значень потоку в дугах вхідного графа перераховуються величини і(х,у) і r(x,e). Крім цього, коректується множини склад множин I і R:

_{f(s,a)=2=c(s,a) (s,a)I (s,a)R, r(s,a)=2,}

f(a,b)=1<c(a,b) (a,b)I, i(a,b)=2 (a,b)R, r(a,b)=1, f(b,t)=2=c(b,t) (b,t)I (b,t)R, r(b,t)=2, f(s,b)=1<c(s,a) (s,a)I, i(s,b)=2 (s,a)R, r(s,a)=1, f(a,c)=1<c(a,c) (a,c)I, i(a,c)=3 (a,c)R, r(a,c)=1, f(c,t)=1<c(c,t) i(c,t)I (c,t)R, r(c,t)=1.

Крок 3. Знову використовується алгоритм пошуку збільшуючого ланцюга для визначення відповідного ланцюга з “s” в “t”. При цьому виявляється, що при біжучих значеннях потоку в дугах графа в ньому не існує ні одного збільшуючого ланцюга. В процесі виконання алгоритму у вихідному графі виявляються розфарбованими вершинами “s”, “b”, “a”, “c” (причому у вказаному порядку), однак вершина “t” не розфарбовується. Оскільки ланцюг, що збільшує потік, знайти не вдається, алгоритм пошуку максимального потоку завершує свою роботу. Останній з побудованих потоків є максимальним. Тобто в розглянутому прикладі з “s” в “t” може бути додатково пропущено 3 одиниці потоку.

Відмітимо, що останнє застосування алгоритму пошуку збільшуючого ланцюга приводить до розрізу з дуг (b,t),(c,t), що мають на одній кінцевій і одній незафарбованій вершини. Пропускна здатність цього розрізу рівна с(b,c)+с(c,t)=2+1=3, що співпадає з мінімально можливим числом одиниць потоку з “s” в “t”.