Přejít na obsah
Odkaz na web organizace Teiresiás

Adaptace Matematických ALGoritmů

Ford-Fulkersonův algoritmus

messages.homepage.accessibility

Ford-Fulkersonův algoritmus

1. Popis standardní metody algoritmu

Ford-Fulkersonův algoritmus slouží k vyhledání maximálního toku v síti (Síť je orientovaný graf, kde ohodnocení každé hrany znamená maximální množství energie, které skrze hranu může procházet). Pracujeme tedy se sítí $G = (V, E)$, kde $V$ je množina vrcholů včetně zdroje $S$ a stoku $T$, $E$ je množina orientovaných hran. Návěští každé hrany zapisujeme ve formátu $F/C$, kde $C$ značí její kapacitu a $F$ tok, tj. množství energie, které v ní proudí.

  1. Na počátku algoritmu nastavíme u všech hran nulový tok.
  2. Opakovaně hledáme nenasycenou cestu od zdroje ke stoku. Jakmile ji nalezneme, zjistíme minimální rezervu kapacity všech jejích hran, o kterou následně navýšíme tok v síti.

Při běžném provedení algoritmu pracujeme s vizuální reprezentací sítě, u níž měníme návěští hran. Na Obrázku 1 je znázorněna síť $N$ o sedmi vrcholech s aktuálním tokem 1 (viz cesta $S → A → C → T$). Je zvýrazněna nenasycená cesta $S → B → D → T$, u níž je minimální rezerva kapacity hran rovna 1. Můžeme tedy v dalším kroku zvýšit tok v síti a upravit návěští hran nenasycené cesty, tj. modifikovat $0/1$ na $1/1$ v případě hran $S → B, B → D$ a $0/3$ na $1/3$ u hrany $D → T$.

Příklad 1: síť $N$
Obrázek 1: Síť $N$ s tokem 1 a vyznačenou nenasycenou cestou $S → B → D → T$

Pro názornost uvádíme i konkrétní příklad sítě a Animaci 1 naznačující výpočet maximálního toku pomocí Ford-Fulkersonova algoritmu.

Příklad 2: síť $N$
  •  
Animace 1: Výpočet maximálního toku pomocí Ford-Fulkersonova algoritmu

2. Návrh možných adaptací

1. Práce se sítí v jednom listu tabulkového procesoru:

Síť je opět nabízena ve formě tabulky a organizována podobným způsobem jako v případě 1. metody adaptace Dijkstrova algoritmu. V prvním sloupci jsou vypsány uzly sítě, do dalších buněk na stejném řádku pro daný uzel $X$ zapisujeme všechny hrany, které začínají v uzlu $X$. Uvádíme je ve formátu  $Y$$F/C$, kde $Y$ je uzel, ve kterém orientovaná hrana z $X$ končí, $F$ je aktuální tok skrze hranu a $C$ je její kapacita. Uvažujme tutéž síť $N$, jakou jsme znázornili na Obrázku 1. Následující Tabulka 1 zachycuje fázi algoritmu, při níž jsme již nalezli jednu nenasycenou cestu $S → A → C → T$.

Příklad 3: síť $N$
$S$ $*A$$1/1$ $B$$0/1$ $E$$0/5$
$A$ $*C$$1/1$ $E$$0/1$
$B$ $D$$0/1$
$C$ $T$$1/3$
$D$ $T$$0/5$
$E$ $B$$0/1$ $C$$0/2$ $D$$0/2$ $T$$0/1$
$T$
Tabulka 1: Síť $N$ formou tabulky po nalezení a zpracování první nenasycené cesty $S → A → C → T$

Nevidomý student nejprve najde nenasycenou cestu od zdroje $S$ ke stoku $T$. Prochází postupně tabulkou a pamatuje si posloupnost uzlů, kterými cesta vede, i aktuální minimální rezervu jejích hran. Ve druhém průchodu již upravuje tok a nasycené hrany označuje hvězdičkou.

2. Organizace hran pod sebou na jednotlivých řádcích v běžném textovém editoru:

Každou hranu zapisujeme na samostatném řádku ve formátu $X$$F/C$$Y$, kde $X$ je počáteční uzel hrany, $Y$ koncový uzel hrany, $F$ aktuální tok skrze hranu a $C$ její kapacita. Hrany řadíme abecedně dle uzlu, ze kterého vycházejí. Pracujeme s nimi obdobným způsobem jako u první metody, tj. procházíme hrany vždy dvakrát, poprvé, abychom nalezli nenasycenou cestu od zdroje ke stoku, podruhé, abychom upravili tok na této cestě.

3. Diskuze nad výhodami a nevýhodami

V tomto případě u nevidomých studentů zvítězila 1. metoda. Nebylo příliš složité se orientovat v tabulce a hledat nenasycenou cestu (Poznamenejme, že problém nastává ve chvíli, kdy je k nalezení maximálního toku nutné některé hrany procházet proti směru toku.). Nevýhodou druhé metody je fakt, že při hledání nenasycené cesty musí nevidomý často projít mnoha řádky s údaji, které jsou pro něj v tu chvíli nepodstatné. U obou nabízených adaptací se jeví jako vhodné poznamenat si zpracovávanou nenasycenou cestu např. do textového editoru (stačí vypsat posloupnost vrcholů od zdroje ke stoku).