Următoarea problemă este cunoscută în teoria graficelor sub numele de problema lui Steiner: punctele n sunt date pe plan; Este necesar să le conectați prin linii drepte astfel încât lungimea totală a segmentelor să fie cea mai mică.
În timpul căutării unei soluții, este permisă introducerea de noi puncte; „Lungimea“ a segmentului care leagă două puncte date, nu înseamnă neapărat literalmente geometrica - acesta poate fi o evaluare cantitativă a „prețuri“ care trec de la punct la punct pe orice polilinie.
Putem da următoarea interpretare grafică a problemei lui Steiner. Este dat un grafic nedirecționat G0 = (V0, ∅) fără margini. Este necesar să găsim un grafic ne-orientat G = (V, T) cu proprietăți speciale.
Presupunem că la fiecare margine a oricărui grafic nedirecționat obținut în procesul de rezolvare a problemei, putem asocia un număr nonnegativ numit greutatea acestei margini. Mai întâi, graficul G necesar trebuie să fie un arbore nedirecționat și, în al doilea rând, mulțimea de vârfuri trebuie să includă setul de vârfuri ale graficului original, adică V0 ⊆ V și, în al treilea rând, suma greutăților marginilor sale trebuie să fie cea mai mică.
Cerința ca graficul dorit G a fost copac neorientat, datorită faptului că în ea orice pereche de vârfuri trebuie unite printr-un circuit unic, deoarece altfel graficul nu ar avea cea mai mică cantitate de greutăți. Într-adevăr, în cazul în care există cel puțin două circuite care se conectează unele perechi de noduri, apoi selectați cea care suma ponderilor margini mai mici. În cazul în care, cu toate acestea, sugerează că, în această situație, există cel puțin două circuite cu aceeași greutate, este încă un fel de lanț (și apoi soluția optimă nu este unic) este selectat pentru soluția optimă.
Algoritmi eficienți * care oferă o soluție exactă a problemei Steiner nu există. Cu toate acestea, sunt cunoscuți algoritmi eficienți care găsesc unele aproximări ale soluției exacte. O astfel de soluție este algoritmul Kruskal. Un grafic nedirecționat (orientat), în care fiecare margine (arc) este asociată cu un anumit număr real, se numește un grafic ponderat sau marcat. Acest număr este numit greutatea sau eticheta unei margini (arc). De regulă, considerăm un grafic cu etichete naturale de margini (arce).
* Algoritmul este considerat eficient în cazul în care complexitatea algoritmului exprimat prin funcția delimitată de mai sus printr-un polinom în parametrul ce caracterizează „volumul“ al datelor originale. Pentru problema Steiner acest parametru este numărul de noduri de G0.
Algoritmul Kruskal calculează, pentru un grafic nedeterminat ponderat G, un arbore care se întinde cu cea mai mică sumă de greutăți a marginilor - arborele de cel mai mic greutate. Diferența esențială este doar că problema formulată de problema Steiner (în declarația sa a graficului) este faptul că, în noul set de noduri sarcină găsirea unui arbore de acoperire de greutate minimă nu se schimbă. Prin urmare, algoritmul Kruskal oferă doar o anumită aproximare a soluției problemei Steiner.
Când descriem algoritmul, vom folosi o metodă de stocare a datelor, numită o coadă. Elementele de date din coadă sunt ordonate până la momentul primirii. Elementele pot fi adăugate la coadă și extrase din coadă. În orice moment există doar un singur element care a fost coada de așteptare înainte de ceilalți, -. „Cap“ coadă Atunci când adăugați un nou element este plasat în „coada“ a cozii, care este, muncă este efectuată de coada de obicei pentru regula - „primul venit - primul ieșit“ pentru a elimina din coada de un anumit element care nu este disponibilă în acest moment, este necesar să se elimine toate elementele primite anterior, începând cu rândul său, „cap“ ..
Luați în considerare algoritmul pentru găsirea copacului de extindere a celei mai mici greutăți (algoritmul Kruskal). Fie G un grafic ne-orientat conectat G = (V, E) cu greutăți numerice ne-negationale. Denumim greutatea e prin φ (ε).
Ca rezultat al algoritmului, obținem un arbore spanning T = (V, H) de G astfel încât suma să fie cea mai mică.
Sortează toate marginile graficului inițial ascendent dimensiunile și forma tuturor, astfel încât în „capul“ coada a fost o margine cu cea mai mică greutate, iar „coada“ - cu cea mai mare și greutățile marginilor nu scad de la „capul“ coadă la „coada“.
Metoda constă în "coaserea" copacului dorit de la componentele pădurii care se întinde. Inițial, o pădure care se întinde este un set de vârfuri izolate ale graficului original, adică muchiile sale sunt goale. În prima etapă, marginea celei mai mici greutăți este extrasă din coadă și adăugată la setul de margini al arborelui original.
În etapele următoare ale algoritmului, o margine este extrasă din coadă. Dacă această margine conectează vârfuri aparținând diferitelor componente ale pădurii care se întinde în prezent, atunci ea este adăugată la setul curent de margini al arborelui dorit și aceste componente se îmbină într-una. În caz contrar, marginea este aruncată. Procesul se repetă până când numărul de componente ale pădurii care se întinde este setat la 1. Se poate demonstra că această componentă este arborele de spanning cel mai puțin ponderat.
Acum procedăm la o descriere formală a algoritmului.
- Am setat setul de margini H al copacului necesar (H = ∅).
- Formăm setul VS = 1>. n >>, ale căror elemente sunt seturile de noduri corespunzătoare componentelor pădurii originale. Fiecare astfel de componentă constă dintr-un singur punct.
- Sortim setul de margini E a graficului inițial prin mărirea greutății și formarea coadă Q ale cărei elemente sunt marginile graficului G.
- Dacă mulțimea VS conține mai mult de un element (adică pădurea care cuprinde mai multe componente) și coada Q nu este goală, treceți la pasul 5, dacă nu altceva - la pasul 7.
- Extras din coada Q margine e. În cazul în care marginile e aparțin diferitelor capete ale setului de vârfuri Vi și Vj de VS. apoi treceți la pasul 6, în caz contrar, apoi aruncați marginea extrasă și reveniți la pasul 4.
- Combinam o multitudine de vârfuri Vi și Vj (presupunând W = = Vi ∪ Vj), șterge o pluralitate de Vi și Vj pluralității VS VS și adăugați la W. Adăugarea set margine e în N. set Revenind la pasul 4.
- Ne oprim de la muncă. Setul H este setul de margini al copacului care se extinde.
Dovada corectitudinii algoritmului Kruskal, adică dovada faptului că algoritmul produs de algoritm este într-adevăr arborele care acoperă cea mai mică greutate nu este dat.
În Fig. 5.19, a-d pentru graficul nedirecționat arată secvența de construire a arborelui de spanning cu cea mai mică greutate. Rețineți că rezultatul algoritmului în cazul general depinde de ordinea marginilor aceleiași greutăți în coada de așteptare. Să presupunem că după sortarea primei în coadă este marginea 0. v1> cu o greutate de 2.
Graficul original este prezentat în Fig. 5.19, a. În Fig. 5.19, b arată rezultatul primei etape a algoritmului. În Fig. 5.19, c arată rezultatul adăugării marginii următoare 1. v2> cu o greutate de 2 din coadă. În Fig. 5.19, d arată rezultatul adăugării unei margini de 0. v4> cu greutatea 3. Dacă marginea următoare din coadă este 1. v4>, aceasta va fi aruncată. Continuarea parcursul algoritmului depinde de ordinea în care nervurile sunt plasate în coada de așteptare 2. v3> și 3. v4> cu greutăți 4. Oricare dintre acestea pot fi adăugate la setul de marginile unui arbore de acoperire, iar acest algoritm se va termina treaba. În Fig. 5.19, d arată copacul de acoperire obținut după adăugarea marginii 3. v4>.
Rețineți că, pentru graficul de mai sus, cu două margini de greutate 2 vor fi incluse în arbore de acoperire, indiferent de ordinea lor în coada de așteptare după sortare, și marginea 1. v4> nu intră în nici un arbore de acoperire greutate minimă.
Se poate demonstra că pasul cel mai laborios în algoritmul Kruskal este de a sorta marginile graficului prin mărirea greutăților. După cum știm deja, sarcina de a sorta n elemente nu poate fi rezolvată mai repede decât în timpul O (nlog2 n). În consecință, complexitatea algoritmului Kruskal este estimată prin numărul O (| E | log2 | E |), unde E | Este cardinalitatea setului de margini ale graficului. Deoarece inegalitatea | E | log2 | E | ≤ | E | 1. atunci algoritmul Kruskal poate fi considerat eficient.
Trimiteți-le prietenilor: