arbore de acoperire minimă (sau arborele minim se întinde) într-un ponderat, grafic legat, neorientat - este un arbore de acoperire al graficului având greutatea minimă posibilă, care este înțeleasă ca suma ponderilor muchiilor sale constitutive sub greutatea copacului.
Algoritmul de construire a unui arbore minim spanning presupune îmbinarea tuturor vârfurilor rețelei utilizând căi de cea mai mică lungime. O problemă tipică a cărei soluție necesită un astfel de algoritm este crearea (proiectarea) a rețelei de drumuri pavate care leagă așezările din zonele rurale, unde drumurile care leagă oricare două puncte poate trece prin alte localități. Designul cel mai economic al sistemului rutier ar trebui să minimizeze lungimea totală a drumurilor asfaltate, în timp ce rezultatul dorit poate fi obținut folosind algoritmul de construire a unui arbore minim spanning.
Luați în considerare schema generală a algoritmilor de construire a unui arbore minim spanning folosind o strategie lacomă. Deci, permiteți unui grafic G (V; E) conectat nedirectat cu n noduri și o funcție de greutate w să fie dat. E → R.
Cadrul dorit este construit treptat. Algoritmul folosește un subgraf aciclic A al grafului original G. Aceasta se numește o pădure intermediară care se întinde. Inițial, G constă din n noduri care nu sunt conectate una la alta (n copaci dintr-un vertex). La fiecare pas, o margine nouă este adăugată la A. Graficul A este întotdeauna un subgraf al unui schelet minimal. Următoarea margine adăugată e = (u. V) este aleasă astfel încât să nu se încalce această proprietate: A ∪ e> trebuie să fie, de asemenea, un subgraf al celei minime. O astfel de margine este numită în siguranță.
Să descriem procedura de realizare a acestui algoritm. Indicați cu N = setul de noduri ale rețelei și introduceți notația nouă:
Compania de televiziune intenționează să conecteze cinci noi zone la rețeaua sa de cablu. În Fig. 6.4 prezintă structura rețelei planificate și distanța (în mile) între zone și telecentru. Este necesar să planificați cea mai economică rețea de cablu.
Pentru a porni algoritmul de construire a unui arbore minim spanning, selectați nodul 1 (sau orice alt nod). atunci
Etapele iterative ale execuției algoritmului sunt prezentate în Fig. 6.5. Aici liniile subțiri arată marginile care leagă nodurile aparținând seturilor. printre care se caută o margine cu un cost minim (lungime). Această margine găsită este afișată cu linii punctate. Linii groase pline denotă marginile care unește nodurile setului Ck (și care au fost mai devreme marcate cu linii punctate).
De exemplu, marginea (1.2) de pe prima iterație are cel mai mic cost (adică cea mai scurtă distanță între punctele de rețea) între toate muchiile de legătură nodul 1 cu o multitudine de noduri. (rețineți că nodul 6 nu are o margine care să o conecteze direct la nodul 1).
Soluția sub forma unui arbore minim de spanning a fost obținută la a 6-a iterație (Figura 6.5).
Lungimea minimă a cablului pentru construirea unei astfel de rețele este de 1 + 3 4 4 + 3 + 5 = 16 mile.
Tema 10. Problema găsirii celei mai scurte căi
Problema găsirii celei mai scurte căi:
Determinați în rețeaua de transport calea cea mai scurtă dintre punctul de sursă dat și destinație. Acest model poate fi folosit pentru a descrie o varietate de situații, după cum se arată în exemplele de mai jos.
Exemple practice ale problemei de a găsi calea cea mai scurtă.
Sarcina poate fi formulată ca o rețea cu cinci noduri cu numere de la 1 la 5,
Costul arcurilor este egal cu costul înlocuirii autoturismelor. Soluția problemei este echivalentă cu găsirea celei mai scurte căi între nodurile 1 și 5.
Exemplul 2: Cea mai fiabilă rută
Dl. Razumnik merge să lucreze în fiecare zi cu mașina. După ce și-a terminat cursul complet în teoria cercetării operaționale, a identificat cu ușurință calea cea mai scurtă de la casă la muncă. Din nefericire, acest traseu este foarte ocupat de detașamente de poliție, iar mașina lui Razumnik este adesea oprită pentru depășirea vitezei (așa cum i se pare, nu justificat). Astfel, cea mai scurtă cale nu a fost cea mai rapidă. Prin urmare, domnul Razumnik intenționează să dezvolte un nou traseu în care ar avea cea mai mare probabilitate de a nu fi oprit de poliție.
Schema rețelei de drumuri prin care domnul Razumnik poate ajunge de la domiciliu la locul de muncă este prezentată în Fig. 6.10. Aceeași schemă arată probabilitatea de a nu se opri pentru fiecare segment al rețelei rutiere. Probabilitatea de a nu se opri de-a lungul întregii căi a mașinii Razumnik este egală cu produsul probabilităților de a nu se opri pe fiecare segment al căii alese. De exemplu, probabilitatea de a nu fi oprit pe traseu
1- »3-» 5- »7 este 0,9 x 0,3 x 0,25 = 0,0675.
Trimiteți-le prietenilor: