Algoritm de compresie a florilor

Algoritmul Blossom este un algoritm în teoria graficelor pentru a construi cele mai mari potriviri pe grafice. Algoritmul a fost dezvoltat de Jack Edmonds în 1961 [1] și publicat în 1965 [2] . Având în vedere un grafic general G =( V , E ), algoritmul găsește o potrivire M astfel încât fiecare vârf din V este incident cu cel mult o muchie din M și | M | maxim. O potrivire este construită prin îmbunătățirea iterativă a potrivirii goale inițiale de-a lungul căilor grafice de creștere. Spre deosebire de potrivirea bipartită , ideea cheie nouă a fost comprimarea unui ciclu impar dintr-un grafic (floare) într-un singur vârf și continuarea căutării iterativ peste graficul condensat.

Motivul principal pentru care algoritmul de compresie a florilor este important este că a oferit prima dovadă că a fost posibil să se găsească cea mai mare potrivire în timp polinomial. Un alt motiv este că metoda conduce la descrierea unui politop de programare liniară pentru un politop de potrivire, ceea ce duce la un algoritm de potrivire a greutății minime [3] . După cum a clarificat Alexander Schreiver , importanța suplimentară a rezultatului rezultă din faptul că acest politop a fost primul a cărui demonstrație integrală „nu numai că a rezultat din unimodularitatea totală , dar descrierea sa a fost o descoperire în combinatoria poliedrelor ” [4] .

Creșterea căilor

Având în vedere un grafic G =( V , E ) și un M potrivit pentru G , un vârf v este gol (nu este acoperit de potrivire) dacă nu există o muchie în M care să fie incidentă cu v . O cale în G este o cale alternativă dacă marginile sale alternativ nu aparțin lui M și sunt conținute în M . Calea de creștere P este un lanț alternativ care începe și se termină cu vârfuri goale. Rețineți că numărul de vârfuri nepotrivite din calea de creștere este mai mare cu unu decât numărul de muchii din potrivire și, prin urmare, numărul de muchii din calea de creștere este impar. Creșterea potrivirilor de-a lungul căii P este operația de înlocuire a setului M cu o nouă potrivire . $M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)$

După lema lui Berge , o potrivire M este maximă dacă și numai dacă nu există o cale de creștere a M în G [5] [6] . Prin urmare, fie potrivirea este cea mai mare, fie poate fi mărită. Astfel, începând cu unele potriviri, putem calcula cea mai mare potrivire prin creșterea potrivirii curente cu calea augmentată. Algoritmul poate fi formalizat după cum urmează

INTRARE: Graficul G , potrivirea inițială M pe G IEȘIRE: cea mai mare potrivire M* pe G Funcția A1 găsire_cel mai mare_potrivire ( G , M ): M* A2 calea_creștere_găsire ( G , M )

P\leftarrow

A3 dacă P nu este gol , atunci A4 returnează find_greatest_match ( G , increment M de-a lungul P ) A5 altfel A6 returnează M A7 end if A8 end function

Trebuie să descriem cum pot fi construite eficient căile de creștere. Rutina lor de căutare folosește flori și contracție.

Flori și constricție

Având în vedere un grafic G =( V , E ) și o potrivire M a unui grafic G , atunci floarea B este un ciclu în G format din 2k + 1 muchii din care exact k aparțin lui M și are un vârf v ( bază ) astfel că există un lanț alternativ de lungime pară ( tulpină ) de la v la un vârf gol w .

Găsirea florilor:

Privim prin grafic, pornind de la vârful gol;
Pornind de la acest vârf, îl marchem ca " o " exterior ;
Alternativ, etichetați nodurile ca " i " interior și " o " exterior, astfel încât să nu aibă două vârfuri adiacente aceeași etichetă;
Dacă ajungem cu două vârfuri adiacente etichetate ca exterior „ o ” , avem un ciclu de lungime impară și, prin urmare, o floare [7] .

Definim un grafic comprimat G' ca graficul obținut din G prin contractarea tuturor marginilor florii B și definim o potrivire comprimată M' ca potrivirea graficului G' corespunzător lui M .

G’ are o cale de creștere a M’ dacă și numai dacă G are o cale de creștere a M , și atunci orice cale de creștere a M’ P’ în G’ poate fi ridicată la o cale de creștere a M în G prin restaurarea florii B contractat mai devreme, astfel încât segmentul drumului P' (dacă există) care trece prin v B este înlocuit cu un segment adecvat care trece prin B [8] . In detaliu:

Dacă P' trece printr-un segment în G' , atunci acest segment este înlocuit cu un segment în G , unde vârfurile florii u' şi w' şi latura florii B , de la u' la w' sunt alese astfel încât noua cale rămâne alternativă ( u ' goală în raport cu , ). $u\to v_{B}\to w$ $u\to (u'\to \dots \to w')\to w$ $(u'\la \dots \la w')$ $M\cap B$ $\{w',w\}\în E\setminus M$

Dacă P' are destinaţia v B , atunci segmentul de cale din G' este înlocuit cu un segment de cale din G , unde vârfurile florii u' şi v' şi latura florii B , de la u' la v' , sunt ales astfel încât calea să fie alternată ( v' gol, ). $u\to v_{B}$ $u\to (u'\to \dots \to v')$ $(u'\la \dots \la v')$ $\{u',u\}\în E\setminus M$

Apoi floarea poate fi comprimată și căutarea poate fi continuată peste graficele comprimate. Această compresie este inima algoritmului Edmonds.

Găsirea unei căi de creștere

Creșterea căutării traseului utilizează o structură de date suplimentară, care este o pădure F , ai cărei arbori individuali corespund unor porțiuni din graficul G . De fapt, pădurea F este aceeași folosită pentru a găsi cele mai mari potriviri în graficele bipartite (fără a fi nevoie să contractați flori). La fiecare iterație, algoritmul fie (1) găsește o cale de creștere, fie (2) găsește o floare și recurge într-un grafic comprimat, fie (3) concluzionează că nu există o cale de creștere. Structura suplimentară este construită folosind o procedură incrementală, care este discutată mai jos [8] .

Procedura de construcție privește vârfurile v și muchiile e ale graficului G și actualizează incremental F în consecință. Dacă v este într-un arbore de pădure T , folosim root(v) pentru a desemna rădăcina lui T . Dacă ambii u și v se află în același arbore T în F , notăm prin distanță (u, v) lungimea singurei căi de la u la v din arborele T .

INTRARE: Graficul G , potrivirea M cu G IEȘIRE: Se mărește calea P la G sau cale goală dacă nu a fost găsită o astfel de caleFuncția B01 find_increment_path ( G , M ): P B02 pădure goală

F\leftarrow

B03 faceți toate vârfurile și muchiile neetichetate în G , etichetați toate muchiile M B05 pentru fiecare vârf gol v faceți B06 creați arbore dintr-un vârf { v } și adăugați arbore la capătul F B07 pentru B08 în timp ce există un vârf neetichetat v în F cu distanță egală (v, rădăcină(v)) faceți B09 în timp ce există o margine neetichetată e ={ v , w } faceți B10 dacă w nu este în F , atunci // w este în potrivire, deci adăugați marginea // acoperirea e și w în F B11 este potrivită cu vârful w în M B12 adăugați muchii { v , w } și { w , x } la arbore pentru v B13 altfel B14 dacă distanța (w, rădăcină(w)) este ciudat atunci

x\leftarrow

// nu face nimic. B15 altfel B16 dacă root(v) ≠ root(w) then // Raportează calea de creștere în F .

\cup \{e\)

calea B17 ( )

P\leftarrow

root(v)\to \dots \to v)\to (w\to \dots \to root(w)

B18 return P B19 else // Contractați floarea la G și căutați o cale în graficul comprimat. B20 floarea formată din e și marginile căii în T B21 micșorați G și M prin micșorarea florii B B22 găsire_caer_creștere B23 ridicare P' la G B24 întoarcere P B25 capăt dacă B26 capăt dacă B27 capăt dacă B28 marcați marginea e B29 sfârşitul în timp ce B30 marchează vârful v B31 sfârşitul în timp ce B32 întoarce calea goală

B\leftarrow

v\la w

G',M'\leftarrow

P'\leftarrow

(G',M')

P\leftarrow

Funcția finală B33

Exemple

Următoarele patru figuri ilustrează execuția algoritmului. Liniile punctate arată margini care nu sunt prezente în prezent în pădure. În primul rând, algoritmul prelucrează o margine care nu aparține pădurii, ceea ce duce la extinderea pădurii actuale (liniile B10 - B12).

Apoi floarea este îndepărtată și graficul este comprimat (linii B20 - B21).

În cele din urmă, algoritmul găsește o cale de creștere P′ în graficul comprimat (linia B22) și o ridică în graficul original (linia B23). Rețineți că capacitatea algoritmului de contracție a florii este decisivă aici. Algoritmul nu poate găsi P în graficul original în mod direct, deoarece în linia B17 a algoritmului sunt considerate doar muchiile non-păduri între vârfuri la o distanță uniformă de rădăcină.

Analiză

Pădurea F construită de find_increasing_path() este o pădure în dungi [9] .

un arbore T în G este un arbore alternant în raport cu M dacă
- T conține exact un vârf r , numit rădăcina arborelui
- orice vârf aflat la o distanță impară de rădăcină are exact două muchii incidente în T și
- toate căile de la r la frunzele din T au lungimi pare, muchiile lor impare nu aparțin lui M , dar muchiile lor pare aparțin lui M.
o pădure F în G este o pădure cu dungi în raport cu M dacă
- componentele sale conectate sunt arbori alternanți și
- orice vârf gol din G este o rădăcină într-un arbore alternant în F .

Fiecare iterație a buclei, începând de la linia B09, fie adaugă un nod arborelui T în F (linia B10), găsește o cale de creștere (linia B17), fie găsește o floare (linia B20). Este ușor de observat că timpul de rulare al algoritmului este . Micali și Vazirani [10] au arătat un algoritm care construiește cea mai mare potrivire în timp . $O(|E||V|^{2})$ $O(|E||V|^{1/2})$

Potrivire bipartită

Algoritmul se reduce la algoritmul standard pentru potrivirea în grafice bipartite [6] dacă G este bipartit . Deoarece nu există cicluri impare în G în acest caz , florile nu vor fi găsite niciodată și puteți șterge pur și simplu liniile B20 - B24 ale algoritmului.

Potrivire ponderată

Problema de potrivire poate fi generalizată prin atribuirea de ponderi muchiilor graficului G . În acest caz, se pune întrebarea despre mulțimea M , care dă o potrivire cu greutatea totală maximă (minimă). Problema de potrivire ponderată poate fi rezolvată cu un algoritm combinatoriu care utilizează algoritmul Edmonds neponderat ca subrutină [5] . Vladimir Kolmogorov a dat o implementare eficientă a acestui algoritm în C++ [11] .

Note

↑ Edmonds, 1961 , pp. 32-54.
↑ Edmonds, 1965 , pp. 449-467.
↑ Edmonds, 1965 , pp. 125-130.
↑ Schrijver, 2003 .
↑ 1 2 Lovász, Plummer, 1986 .
↑ 12 Karp , 2006 .
↑ Prin construcție, „ i ” marchează începutul unei muchii din M , astfel încât cazul întâlnirii a două vârfuri adiacente etichetate „ i ” este imposibil.
↑ 12 Tarjan , 2002 .
↑ Kenyon, Lovász, 1990 .
↑ Micali, Vazirani, 1980 , pp. 17-27.
↑ Kolmogorov, 2009 , pp. 43-67.

Literatură

Alexander Schrijver. Optimizare combinatorie: poliedre și eficiență . - Berlin, Heidelberg: Springer-Verlag, 2003. - (Algoritmi și combinatorie). — ISBN 9783540443896 .
Jack Edmonds. O privire asupra raiului // Istoria programării matematice - O colecție de reminiscențe personale / JK Lenstra, AHG Rinnooy Kan, A. Schrijver. - CWI, Amsterdam and North-Holland, Amsterdam, 1961. - p. 32–54.
Jack Edmonds. Cărări, copaci și flori // Can. J. Matematică .. - 1965. - T. 17 . — S. 449–467 . - doi : 10.4153/CJM-1965-045-4 .
Jack Edmonds. Potrivire maximă și un poliedru cu vârfuri de 0,1 // Jurnalul de Cercetări al Biroului Național de Standarde Secția B. - 1965. - T. 69 . — S. 125–130 .
László Lovász, Michael D. Plummer. Teoria potrivirii. - Akademiai Kiado, 1986. - ISBN 963-05-4168-8 .
Richard Karp. note de curs. UC Berkeley . - 2006. Arhivat la 30 decembrie 2008.
Robert. Sketchy Notes on Incredible Shrinking Blossom Algorithm al lui Edmonds pentru potrivirea generală // Note de curs-423: Teoria algoritmilor . — Departamentul de Informatică, Universitatea Princeton, 2002.
Claire Kenyon, László Lovász. Matematică algoritmică discretă // Raport tehnic CS-TR-251-90, Departamentul de Informatică, Universitatea Princeton. — 1990.
Blossom V: O nouă implementare a unui algoritm de potrivire perfectă a costurilor minime // Calcularea programării matematice. - 2009. - T. 1 , Nr. 1 . — p. 43–67 .
Silvio Micali, Vijay Vazirani. Un algoritm O(V 1/2 E) pentru găsirea potrivirii maxime în graficele generale // Cel de-al 21-lea simpozion anual privind fundamentele informaticii,. - IEEE Computer Society Press, New York, 1980. - P. 17-27.