Algoritmul Edmonds

Șablonul sinoptic {{ Algoritmo }} trebuie adăugat la acest articol sau secțiune

Puteți adăuga și completa șablonul conform instrucțiunilor și apoi eliminați acest avertisment. Dacă nu reușiți să o umpleți într-o mare măsură, nu faceți nimic; nu introduceți șabloane goale.

În teoria grafurilor, Edmonds algoritmul, de asemenea , numit Chu-Liu-Edmonds algoritm, este utilizat pentru a determina, pornind de la un anumit ponderat și puternic conectat digraph , subramificația sa orientat de greutate minimă și având rădăcina atribuită. Adică, algoritmul identifică un subset de arce ale digrafului dat care constituie un copac astfel încât fiecare pereche de noduri luate în considerare să fie conectată printr-o cale orientată și astfel încât greutatea totală a arcurilor identificate să fie minimă. O variantă predictibilă a algoritmului caută subarborele orientat al greutății maxime.

Acest algoritm a fost dezvoltat independent de Chu și Liu în 1965 și de Jack Edmonds în 1967. Edmonds a furnizat o dovadă destul de greoaie și complexă a corectitudinii sale folosind proceduri de programare liniară .

Descriere

Algoritmul acceptă ca intrare un grafic orientat și ponderat G = (V, A, w, a) , unde V este setul de noduri, A setul de margini, w: A → R ⁺ o funcție de la arcul setat la set de numere reale și la nodul care trebuie să fie rădăcina arborelui. La ieșire se întoarce arborele orientat pe cel mai mic cost T * = (V, A *, w, a) , unde A * este un subset al lui A format din card (V) - 1 margini. În timpul execuției, algoritmul funcționează pe graficele intermediare G _i = (V, A _i , w, a) și pe arborii intermediari T _j = (V _j , A * _j , w, a) care se modifică treptat.

La început, arcurile care intră în rădăcina a , evident străine de arborele necesar, sunt eliminate. Ulterior, algoritmul funcționează în două faze, respectiv numite contracție sau fază C și expansiune sau fază E: în timpul unei faze C, graficul G _i = (V, A _i , w, a) este contractat pentru a elimina posibilul său cicluri; în timpul fazei E arborele T _j = (V _j , A * _j , w, a) se extinde pentru a reapărea nodurile ciclurilor care fuseseră contractate. Atât în ​​timpul fazei de contracție, cât și în timpul fazei de expansiune, are loc alegerea arcurilor prezente în soluția finală T * = (V, A *, w, a) .

Să luăm în considerare faza de contracție care acceptă graficul G = (V, A, w, a) ca intrare:

pasul 1.

Pentru fiecare nod, este selectat arcul de intrare cu cea mai mică greutate. Deoarece rădăcina nu are margini de intrare, cardul (V) - 1 margini rămân. Dacă nu există cicluri, faza de contracție este terminată și arborele T ₁ = (V ₁ , A * ₁ , w, a) este returnat.

pasul 2 .

Dacă există cicluri, continuăm să le luăm în considerare în orice ordine:

la. Orice alte arcuri ale graficului de pornire care conectează nodurile ciclului sunt eliminate din setul de arce.

b. Toate arcurile care intră într-unul dintre nodurile ciclului trebuie să fie reetichetate în conformitate cu următorul criteriu: să fie j și i respectiv un nod al ciclului și un nod care nu îi aparține astfel încât să existe arc (i , j) cu greutate w _{i, j} ; mai mult, fie (k, j) să fie arcul ciclului care se termină în j (având greutate w _{k, j} ); atunci greutatea reetichetată asociată arcului (i, j) va fi:

w _{i, j} = w _{i, j} - w _{k, j}

adică din greutatea fiecărui arc care intră în ciclu scădem greutatea arcului ciclului direcționat către același nod în care intră arcul care este reetichetat.

c. Nodurile ciclului sunt prăbușite într-un supernod.

d. Dintre toate arcele reetichetate și paralele care intră într-un supernod, cel cu cea mai mică greutate este reținut și toate celelalte sunt eliminate.

Și. Acest proces se repetă pentru fiecare ciclu.

pasul 3.

Să revenim la pasul 1 și să aplicăm manevra de contracție pe graficul redus G _{i + 1} obținut.

Să luăm acum în considerare faza de expansiune care acceptă arborele T ₁ = (V ₁ , A * ₁ , w, a) obținut la sfârșitul fazei de contracție anterioare:

pasul 1.

Luați în considerare un super nod și arcul de intrare, arcul de intrare aparține soluției finale T * = (V, A *, w, a) și este etichetat așa cum a fost inițial.

pasul 2.

Supernodul este extins în nodurile originale și una dintre arcele ciclului trebuie eliminată; între nodurile ciclului unul are două arcuri de intrare: arcul tocmai adăugat la soluție și arcul ciclului, acesta din urmă este eliminat, celelalte arcuri ale ciclului sunt adăugate la soluție.

pasul 3.

Reveniți la pasul 1 până când am extins toate supernodurile.

Contracția fiecărui ciclu într-un supernod în timpul unei faze C corespunde expansiunii acestui supernod în ciclul de pornire în timpul fazei E.

Exemplul 1

Imagine	Descriere
	Graficul de intrare G = (V, A, w, a)
[[Imagine: | 200px]]	Prima manevră de contracție: pasul 1
[[Imagine: | 200px]]	Prima manevră de contracție: pasul 2.a
	Prima manevră de contracție: pasul 2.b
[[Imagine: | 200px]]	Prima manevră de contracție: pasul 2.c
[[Imagine: | 200px]]	A doua manevră de contracție: pasul 1
[[Imagine: | 200px]]	A doua manevră de contracție: pasul 2.a
[[Imagine: | 200px]]	A doua manevră de contracție: pasul 2.b
[[Imagine: | 200px]]	A doua manevră de contracție: pasul 2.c
[[Imagine: | 200px]]	A doua manevră de contracție: pasul 2.d Sfârșitul fazei de contracție
[[Imagine: | 200px]]	Prima manevră de expansiune: pasul 1
[[Imagine: | 200px]]	Prima manevră de expansiune: pasul 2
[[Imagine: | 200px]]	A doua manevră de expansiune: pasul 2 Sfârșit Obținem T * = (V, A *, w, a) .

Exemplul 2

Bibliografie

• YJ Chu. TH Liu: On the Shortest Arborescence of a Directed Graph , Science Sinica, v. 14, (1965), pp. 1396-1400.
• J. Edmonds: Filiale optime , J. Res. Nat. Bur. Standarde, v. 71B, 1967, pp. 233-240.
• Robert Tarjan : Găsirea ramificărilor optime , rețele, v.7, 1977, pp. 25–35.
• PM Camerini, L. Fratta, F. Maffioli: O notă despre găsirea unei ramificări optime , Networks, v.9, (1979), pp. 309-312.
• Alan Gibbons: Algorithmic Graph Theory, Cambridge University Press, (1985), ISBN 0-521-28881-9
• HN Gabow, Z. Galil, T. Spencer, RE Tarjan: Algoritmi eficienți pentru găsirea copacilor minimi în grafice nedirecționate și direcționate , Combinatorica 6 (1986), 109-122.
• Y. Zhang: Algoritmi paraleli pentru copacii cu întinderi minime ale graficelor direcționate , Int. J. Parallel Program., 3 (iunie 1990), pp. 109–122
• T. Magnanti, L. Wolsey: manuale în cercetarea operațională și știința managementului: copaci optimi (1995)

linkuri externe

• The Directed Minimum Spanning Tree Problem Descrierea algoritmului rezumată de Shanchieh Jay Yang, mai 2000.
• Algoritmul lui Edmonds (edmonds-alg) - O implementare open source a algoritmului lui Edmonds scris în C ++ și licențiat sub licența MIT . Această sursă utilizează implementarea lui Tarjan pentru graficul dens.
• AlgoWiki - Algoritmul lui Edmonds - O implementare în domeniul public a algoritmului lui Edmonds scris în Java .

Portal IT

Portalul de matematică