Algoritmul Ford-Fulkerson

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 29 aprilie 2022; verificările necesită 3 modificări .

Algoritmul Ford-Fulkerson rezolvă problema găsirii debitului maxim într-o rețea de transport .

Ideea algoritmului este următoarea. Valoarea debitului este setată inițial la 0: pentru toate . Cantitatea de flux este apoi crescută iterativ prin căutarea unei căi de creștere (o cale de la sursă la chiuvetă de -a lungul căreia poate fi trimis mai mult flux). Procesul se repetă până când poate fi găsită o cale de creștere. $f(u,v)=0$ $u,v\în V$ $s$ $t$

Algoritm

Descriere informală

Resetăm toate fluxurile. Rețeaua reziduală coincide inițial cu rețeaua originală.
În rețeaua reziduală, găsim orice cale de la sursă la chiuvetă. Dacă nu există o astfel de cale, ne oprim.
Lăsăm prin calea găsită (se numește cale crescătoare sau lanț crescător ) debitul maxim posibil:
1. Pe calea găsită în rețeaua reziduală, căutăm o margine cu capacitatea minimă . $c_{\min }$
2. Pentru fiecare muchie de pe traseul găsit, creștem debitul cu , iar în sens opus, îl micșorăm cu . $c_{\min }$ $c_{\min }$
3. Modificam reteaua reziduala. Pentru toate muchiile de pe traseul găsit, precum și pentru muchiile opuse (antiparalele) acestora, calculăm noua capacitate. Dacă devine diferit de zero, adăugăm o margine rețelei reziduale, iar dacă devine zero, o ștergem.
Revenim la pasul 2.

Este important ca algoritmul să nu specifice exact ce cale căutăm în pasul 2 sau cum o facem. Din acest motiv, algoritmul este garantat să converge doar pentru lățimi de bandă întregi, dar chiar și pentru acestea, pentru lățimi de bandă mari, poate rula foarte mult timp. Dacă capacitățile sunt reale, algoritmul poate rula la nesfârșit fără a converge la soluția optimă (vezi exemplul de mai jos ).

Dacă nu căutați nicio cale, ci cea mai scurtă, obțineți algoritmul Edmonds-Karp sau algoritmul Dinits . Acești algoritmi converg pentru orice ponderi reale în timp și respectiv. $O(|V||E|^{2})$ $O(|V|^{2}|E|)$

Descriere formală

Dat un grafic cu capacitate și debit pentru muchiile de la până la . Este necesar să se găsească debitul maxim de la sursă la chiuvetă . La fiecare pas al algoritmului, se aplică aceleași condiții ca pentru toate fluxurile: $G(V,E)$ $c(u,v)$ $f(u,v)=0$ $u$ $v$ $s$ $t$

$\ 0\leqslant f(u,v)\leqslant c(u,v)$ . Debitul de la până la nu depășește debitul. $u$ $v$
$\f(u,v)=-f(v,u)$ .
$\ \sum _{v}f(u,v)=0\Longleftrightarrow f_{{in}}(u)=f_{{out}}(u)$ pentru toate nodurile cu excepția și . Fluxul nu se modifică pe măsură ce trece prin nod. $u$ $s$ $t$

Rețeaua reziduală este o rețea cu lățime de bandă și fără flux. $G_{f}(V,E_{f})$ $c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$

Grafic de intrare cu lățimea de bandă , sursă și receptor Ieșire Debit maxim de la la $G$ $c$ $s$ $t$
$f$ $s$ $t$

$f(u,v):=0$ pentru toate marginile $(u,v)$
Atâta timp cât există o cale de la la la astfel încât pentru toate marginile : $p$ $s$ $t$ $G_f$ $c_{f}(u,v)>0$ $(u,v)\în p$
1. Găsi $c_{f}(p)=\min\{c_{f}(u,v)\;|\;(u,v)\in p\)$
2. Pentru fiecare margine $(u,v)\în p$
  1. $f(u,v):=f(u,v)+c_{f}(p)$
  2. $f(v,u):=f(v,u)-c_{f}(p)$
  3. $c_{f}(u,v)=c(u,v)-f(u,v)$
  4. $c_{f}(v,u)=f(u,v)$

Calea poate fi găsită, de exemplu, prin căutare pe lățimea întâi ( algoritmul Edmonds-Karp ) sau căutarea pe adâncime în . $G_{f}(V,E_{f})$

Dificultate

La fiecare pas, algoritmul adaugă un flux de cale de creștere fluxului existent. Dacă capacitățile tuturor muchiilor sunt numere întregi, este ușor de demonstrat prin inducție că fluxurile prin toate muchiile vor fi întotdeauna numere întregi. Prin urmare, la fiecare pas, algoritmul mărește debitul cu cel puțin unu, deci va converge în cel mult pași, unde f este debitul maxim din grafic. Este posibil să finalizați fiecare pas în timp , unde este numărul de muchii din grafic, apoi timpul total de rulare al algoritmului este limitat . $O(|f|)$ $O(|E|)$ $|E|$ $O(|E|\max |f|)$

Dacă capacitatea a cel puțin uneia dintre muchii este un număr irațional, atunci algoritmul poate rula la nesfârșit, fără a converge neapărat către soluția corectă. Un exemplu este dat mai jos.

Un exemplu de algoritm neconvergent

Luați în considerare rețeaua afișată în dreapta, cu capacități sursă , canalizare , margini și capacitatea tuturor celorlalte margini egală cu un număr întreg . Constanta este aleasă astfel încât . Folosim căile din graficul rezidual dat în tabel și , și . $s$ $t$ $e_{1}=1$ $e_{2}=r=({\sqrt {5}}-1)/2$ $e_{3}=1$ $M\geq 2$ $r$ $r^{2}=1-r$ ${\displaystyle p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\))$ ${\displaystyle p_{2}=\{s,v_{2},v_{3},v_{4},t\))$ ${\displaystyle p_{3}=\{s,v_{1},v_{2},v_{3},t\))$

Etapa	Calea găsită	S-a adăugat thread	Capacități reziduale
Etapa	Calea găsită	S-a adăugat thread	$e_{1}$	$e_{2}$	$e_{3}$
0			$r^{0}=1$	$r$	$unu$
unu	$\{s,v_{2},v_{3},t\}$	$unu$	$r^{0}$	$r^{1}$	$0$
2	$p_{1}$	$r^{1}$	$r^{2}$	$0$	$r^{1}$
3	$p_{2}$	$r^{1}$	$r^{2}$	$r^{1}$	$0$
patru	$p_{1}$	$r^{2}$	$0$	$r^{3}$	$r^{2}$
5	$p_{3}$	$r^{2}$	$r^{2}$	$r^{3}$	$0$

Rețineți că după pasul 1, precum și după pasul 5, abilitățile reziduale ale muchiilor , și au forma , și , respectiv, pentru unele naturale . Aceasta înseamnă că putem folosi căile de creștere , , și de nenumărate ori, iar capacitatea reziduală a acestor margini va fi întotdeauna în aceeași formă. Debitul total după pasul 5 este . În timp infinit, debitul total va converge spre , în timp ce debitul maxim este . Astfel, algoritmul nu numai că rulează pe termen nelimitat, dar nici măcar nu converge către soluția optimă. [unu] $e_{1}$ $e_{2}$ $e_{3}$ $r^{n}$ $r^{{n+1}}$ $0$ $n$ $p_{1}$ $p_{2}$ $p_{1}$ $p_{3}$ $1+2(r^{1}+r^{2})$ $\textstyle 1+2\sum _{{i=1}}^{\infty }r^{i}=3+2r$ $2M+1$

Exemplu

Următorul exemplu prezintă primii pași ai algoritmului Ford-Fulkerson într-o rețea de transport cu patru noduri, sursa A și canal D . Acest exemplu arată cel mai rău caz. Când utilizați căutarea pe lățime, algoritmul are nevoie de doar 2 pași.

cale	Lățimea de bandă	Rezultat
	Rețeaua de transport inițială
$A,B,C,D$	$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D))=$ $\min(c(A,B)-f(A,B),c(B,C)-f(B,C),c(C,D)-f(C,D))=$ $\min(1000-0,1-0,1000-0)=1$
$A,C,B,D$	$\min(c_{f}(A,C),c_{f}(C,B),c_{f}(B,D))=$ $\min(c(A,C)-f(A,C),c(C,B)-f(C,B),c(B,D)-f(B,D))=$ $\min(1000-0,0-(-1),1000-0)=1$
	După pașii din 1998...
	Rețeaua de destinație

Vezi și

Teorema Ford-Fulkerson

Link -uri

Un exemplu de rezolvare a unei probleme pe YouTube
Algoritm Vizualizator
Implementarea căutării debitului maxim prin metoda Ford-Fulkerson în Java
Wikimedia Commons are conținut media legate de algoritmul Ford-Fulkerson

Literatură

Thomas H. Kormen et al.Algoritmi : construcție și analiză = INTRODUCERE ÎN ALGORITMI. - Ed. a II-a. - M. : „Williams”, 2006. - S. 1296. - ISBN 0-07-013151-1 .

Note

↑ Zwick, Uri. Cele mai mici rețele pe care procedura de debit maxim Ford-Fulkerson poate eșua să se încheie // Teoretică Informatică : jurnal. - 1995. - 21 august ( vol. 148 , nr. 1 ). - P. 165-170 . - doi : 10.1016/0304-3975(95)00022-O .