Algoritmul Edmonds-Karp

Algoritmul Edmonds-Karp rezolvă problema găsirii debitului maxim într-o rețea de transport . Algoritmul este un caz special al metodei Ford-Fulkerson și rulează în timp în grafic . A fost publicat pentru prima dată în 1970 de omul de știință sovietic E. A. Dinitz . Mai târziu, în 1972, a fost descoperit independent de Edmonds și Karp . $O(|V|\cdot |E|^{2})$ $G=(V,E)$

Algoritm

Algoritmul Edmonds-Karp este o variantă a algoritmului Ford-Fulkerson în care cea mai scurtă cale complementară de la până la în rețeaua reziduală este aleasă la fiecare pas (presupunând că fiecare muchie are lungimea unitară). Cea mai scurtă cale este găsită prin căutarea pe lățimea întâi . $s$ $t$

Descriere

Resetăm toate fluxurile. Rețeaua reziduală coincide inițial cu rețeaua originală.
În rețeaua reziduală, găsim calea cea mai scurtă 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 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.

Pentru a găsi calea cea mai scurtă într-un grafic, folosim căutarea pe lățimea întâi :

Creăm o coadă de vârfuri O. Inițial , O constă dintr-un singur vârf s .
Marcăm vârfurile ca fiind vizitate, fără părinte, iar restul ca nevizitate.
Atâta timp cât coada nu este goală, efectuați următorii pași:
1. Ștergeți primul vârf din coada u .
2. Pentru toate arcele ( u , v ) care ies din vârful u , pentru care vârful v nu a fost încă vizitat, efectuați următorii pași:
  1. Marcăm vârful v ca vizitat, cu părintele u .
  2. Adăugați vârful v la sfârșitul cozii.
  3. Dacă v = t , ieșiți din ambele bucle: am găsit calea cea mai scurtă.
Dacă coada este goală, returnăm răspunsul că nu există deloc cale și ne oprim.
Dacă nu, mergem de la t la s , de fiecare dată mergând la părinte. Ne întoarcem pe calea în ordine inversă.

Dificultate

În timpul lucrului, algoritmul Edmonds-Karp va găsi fiecare cale complementară în timp . Mai jos vom demonstra că numărul total de creșteri de debit efectuate de acest algoritm este . Astfel, complexitatea algoritmului Edmonds-Karp este . $O(|E|)$ $O(|V|\cdot |E|)$ $O(|V|\cdot |E|^{2})$

Dovada

Să numim distanța de la vârful x la vârful y lungimea celei mai scurte căi de la x la y din rețeaua reziduală, măsurată prin numărul de muchii. Dacă nu există o astfel de cale, vom considera că distanța este infinită. Vom spune că y s-a apropiat de x (a îndepărtat de x ) dacă distanța de la x la y a scăzut (a crescut). Vom spune că y este mai aproape de x (mai departe de x ) decât z dacă distanța de la x la y este mai mică (mai mare) decât distanța de la x la z .

Lema . Pe parcursul algoritmului, niciun vârf nu se apropie de sursă. Dovada . Să nu fie așa, atunci cu o oarecare creștere a debitului, unele vârfuri s-au apropiat de sursă. Să le numim greșit. Alegem unul dintre vârfurile greșite, care, după creșterea fluxului, s-a dovedit a fi cel mai aproape de sursă (dacă există mai multe dintre ele, atunci oricare dintre ele). Notați vârful selectat cu v . Luați în considerare calea cea mai scurtă de la s la v . Notați penultimul vârf de pe această cale cu u , astfel încât calea să arate ca . Deoarece u este mai aproape de s decât v și v este cel mai apropiat vârf ilegal de s , atunci u este un vârf obișnuit. Notând distanțele de la s la u și v înainte și după creșterea debitului, respectiv , ca , , , , avem: $s-\ldots-uv$ $d_{u}\$ ${\displaystyle d_{u}^{'))$ $d_{v}\$ ${\displaystyle d_{v}^{'))$

d_{v}^{'}<d_{v}

d_{u}^{'}\geq d_{u)

d_{v}^{'}=d_{u}^{'}+1

Unde

d_{v}\geq d_{u}+2

Prin urmare, înainte de creșterea debitului, arcul ( u , v ) era absent din rețeaua reziduală. Pentru ca acesta să apară, calea de creștere trebuia să conțină un arc ( v , u ). Dar în algoritmul Edmonds-Karp, calea de creștere este întotdeauna cea mai scurtă, deci

d_{v}=d_{u}-1

care contrazice inegalitatea anterioară. Deci presupunerea noastră a fost greșită. Lema este dovedită.

Să o numim critică pe cea a marginilor căii de creștere, a cărei capacitate reziduală este minimă. Să estimăm de câte ori o muchie (u, v) poate fi critică. Lăsați să se întâmple la iterare și data viitoare la iterare . Notând distanța de la s la y la iterația t, avem: $t_{1}$ $t_{2}$ $D_{y}(t)$

D_{v}(t_{1})=D_{u}(t_{1})+1

D_{v}(t_{2})=D_{u}(t_{2})+1

Rețineți că la iterație marginea critică dispare din rețeaua reziduală. Pentru ca muchia (u, v) să reapară în ea până în momentul iterației, este necesar ca la o iterație intermediară să fie aleasă o cale de creștere care să conțină muchia (v, u). Prin urmare, $t_{1}$ $t_{2}$ $t_{3)$

D_{u}(t_{3})=D_{v}(t_{3})+1

Folosind lema demonstrată anterior, obținem:

D_{v}(t_{2})=D_{u}(t_{2})+1\geq D_{u}(t_{3})+1=D_{v}(t_{3} )+2\geq D_{v}(t_{1})+2

Deoarece inițial (altfel v = s, dar muchia care duce la s nu poate apărea pe calea cea mai scurtă de la s la t), și întotdeauna, când desigur, este mai mică decât |V| (cea mai scurtă cale nu conține cicluri și, prin urmare, conține mai puține muchii |V|), o muchie poate fi critică de cele mai multe ori. Deoarece fiecare cale de creștere conține cel puțin o margine critică și numărul total de muchii care ar putea deveni într-o zi critice (toate marginile rețelei originale și cele opuse ale acestora), atunci putem crește calea nu mai mult de |E|·|V | o singura data. Prin urmare, numărul de iterații nu depășește O(|E|·|V|), ceea ce urma să fie demonstrat. $D_{v}>0$ $D_{v)$ ${\frac {(|V|-1)-1}{2}}+1=|V|/2$ $2|E|$

Exemplu

Fie dată o rețea cu sursă la vârf și dren la vârf . În figură, o pereche indică fluxul de-a lungul acestei margini și debitul acesteia. $A$ $G$ $f/c$

Lățimea prima căutare

Să descriem căutarea pe lățimea întâi la primul pas.

Coada este formată dintr-un singur vârf A. A fost vizitat vârful A. Nu există niciun părinte.
Coada este formată (de la început până la sfârșit) din vârfurile B și D. Sunt vizitate vârfurile A, B, D. Nodurile B, D au părintele A.
Coada este formată din vârfurile D și C. Vizitată de A, B, C, D. Nodurile B, D au părintele A, vârful C are părintele B.
Coada este formată din vârfurile C, E, F. Vizitate de A, B, C, D, E, F. Nodurile B, D au părintele A, vârful C are părintele B, vârfurile E, F au părintele D.
Vârful C este eliminat din coadă: marginile sale conduc doar la vârfuri deja vizitate.
Se găsește o muchie (E,G) și bucla se oprește. Vârfurile (F,G) sunt în coadă. Toate vârfurile vizitate. Vârfurile B, D au părintele A, vârful C are părintele B, vârfurile E, F au părintele D și vârful G are părintele E.
Mergem după părinte: . Revenim calea trecută în ordine inversă: . $G\la E\la D\la A$ $A\la D\la E\la G$

Rețineți că vârfurile accesibile de la A în exact 1 pas, exact 2 pași și exact 3 pași au fost adăugate secvenţial la coadă. În plus, părintele fiecărui vârf este vârful accesibil de la A exact cu 1 pas mai repede.

Algoritm de bază

Capacitatea traseului	cale
Capacitatea traseului
$\min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))=$ $\min(3-0,2-0,1-0)=$ $\min(3,2,1)=1$	$A,D,E,G$

$\min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-1,6-0,9-0)=$ $\min(2,6,9)=2$	$A,D,F,G$

$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f} (F,G))=$ $\min(3-0.4-0.1-0.6-2.9-2)=$ $\min(3,4,1,4,7)=1$	$A,B,C,D,F,G$

$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f} (D,F),c_{f}(F,G))=$ $\min(3-1.4-1.2-0.0--1.6-3.9-3)=$ $\min(2,3,2,1,3,6)=1$	$A,B,C,E,D,F,G$

Rețineți că în timpul execuției algoritmului, lungimile căilor complementare (indicate cu roșu în figuri) nu scad. Aceasta proprietate este indeplinita datorita faptului ca cautam cea mai scurta cale complementara .

Algoritmul lui Dinitz

O versiune îmbunătățită a algoritmului Edmonds-Karp este algoritmul Dinitz, care necesită operații. $O(|V|^{2}|E|)$

Să numim o rețea auxiliară fără contur a unui grafic G cu sursa s subgraful său care conține doar acele muchii (u, v) pentru care distanța minimă de la s la v este cu o mai mare decât distanța minimă de la s la u.

Algoritmul lui Dinit:

Construim o rețea minimă fără contur a graficului rezidual.
Atâta timp cât există o cale de la s la t în rețea, efectuați următorii pași:
1. Găsiți calea cea mai scurtă de la s la t. Dacă nu există, ieșiți din buclă.
2. Pe calea găsită în rețeaua reziduală, căutăm o margine cu capacitatea minimă . $c_{\min }$
3. 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 }$
4. Ștergem toate marginile care au ajuns la saturație.
5. Ștergem toate punctele moarte (adică vârfurile, cu excepția chiuvetei, din care nu ies margini, și vârfurile, cu excepția sursei, unde nu intră margini), împreună cu toate marginile incidente cu acestea.
6. Repetați pasul anterior atâta timp cât există ceva de eliminat.
Dacă fluxul găsit este diferit de zero, adăugați-l la fluxul total și reveniți la pasul 1.

Link -uri

Literatură

Thomas 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 .

Algoritmi de căutare grafică
Metode neinformate	Căutare bidirecțională Căutare fascicul Prima căutare a lățimii lexicografice Lățimea prima căutare Căutare după criteriul de cost Profunzime prima căutare Căutare înapoi Caută prin urcare în vârf Căutare limitată la profunzime Căutare în profunzime cu aprofundare iterativă
Metode informate	Decuparea alfa beta Ramura și metoda legată Căutați după prima potrivire A* B* D* Găsirea unui punct de tranziție IDA* Căutare recurstivă pe primul cel mai bun meci SMA*
Comenzi rapide	Algoritmul undelor Algoritmul Bellman-Ford algoritmul lui Dijkstra Algoritmul Johnson algoritmul lui Levit Algoritmul Floyd-Warshall Căutare margine
Arborele de întindere minim	algoritmul lui Boruvka algoritmul lui Prim algoritmul lui Kruskal
Alte	Algoritmul British Museum Algoritmul Edmonds Traversarea copacilor Algoritmul celui mai apropiat vecin în problema vânzătorului ambulant