În matematică, rețelele rutiere (auto și nu numai) sunt reprezentate de un grafic ponderat. Seturile (sau intersecțiile) reprezintă vârful graficului, marginile sunt drumuri, greutățile marginilor sunt distanțele de-a lungul acestor drumuri.
Un număr de algoritmi sunt propuși pentru graficele ponderate. De exemplu, algoritmul popular Dijkstra pentru găsirea celei mai scurte căi de la un vârf la altul. Toți acești algoritmi au un principiu comun (pentru matematică) - sunt universali, adică poate fi aplicat cu succes la grafice de orice design. În special, pentru fiecare algoritm, complexitatea sa este cunoscută - corespunde aproximativ unei creșteri a duratei de execuție a algoritmului, în funcție de numărul de vârfuri ale graficului. Toate acestea pot fi citite în detaliu, de exemplu, în Wikipedia.
Să ne întoarcem la probleme practice. Drumurile sunt reprezentate de un grafic ponderat, dar drumurile nu sunt nici un grafic. Cu alte cuvinte, este imposibilă construirea unei rețele rutiere din orice grafic. Spre deosebire de graficul virtual ca abstracție matematică, drumurile sunt construite de oameni din materiale reale și costă destul de mulți bani. Prin urmare, ele nu sunt așezate atât de oribil, ci în conformitate cu anumite reguli economice și practice.
Noi nu știm regulile, cu toate acestea, lucrul cu rețelele de drumuri, este posibil să se utilizeze algoritmi care sunt eficiente pentru grafice drumuri, cu toate că nu sunt adecvate pentru universal sau grafice în sens matematic. Luați în considerare doi astfel de algoritmi.
Câteva concepte și convenții importante
1. Vom folosi grafice nedirecționate ponderate cu greutăți neangajate. În special, drumurile din regiune (țară) reprezintă exact acest tip de grafic.
2. Cea mai scurtă matrice de distanțe (MKR) - exemplul său mic și simplu poate fi găsit în multe atlasuri rutiere. Această tabletă este denumită de obicei "distanțele dintre cele mai importante orașe". Se pare ca o parte a matricei este sub sau deasupra diagonalei principale (din stânga sus spre dreapta jos), deoarece cealaltă parte a diagonalei principale sunt aceleași figuri, cu alte cuvinte un element M (i, j) = M (j, i). Acest lucru se întâmplă deoarece graficul, așa cum spun matematicienii, este nedirecționat. Rândurile și coloanele corespund orașelor (vârfurile graficului). În realitate, un astfel de tabel este mult mai mare, deoarece topurile graficului, cu excepția orașelor, includ toate satele și intersecțiile, dar este, în mod firesc, imposibilă imprimarea unei asemenea mese mari în atlas.
În primul rând, continuați (mental) masa noastră de sus, obținem MKR, simetric în ceea ce privește diagonala principală și vom ține minte doar o astfel de masă. În acest caz, o coloană cu un anumit număr este egală cu un rând cu același număr și nu contează care dintre conceptele de utilizat. Folosim ambele pentru a le traversa.
MKR-ul nostru poate fi: a) cunoscut în avans, deoarece l-am socotit ca una dintre metodele de căutare a MKR; b) este posibil să nu știm MKR, ci să o definim linia după linie, după cum este necesar. Linia de linie înseamnă că pentru rândul necesar, distanțele sunt calculate numai de la vârful corespunzător la vârfurile rămase, de exemplu, prin metoda lui Dijkstra.
3. O altă pereche de concepte. Excentricitatea unui vârf dat este distanța de la acest vârf la cel mai îndepărtat de el. Raza graficului este cea mai mică dintre excentricitățile tuturor vârfurilor. Centrul graficului este un vârf a cărui eccentricitate este egală cu raza.
Cum arată în practică. Centrul unei rețele rutiere este un oraș sau o răscruce de drum, cel mai puțin îndepărtat de toate celelalte puncte ale acestei rețele. Radiusul este distanța maximă de la acest nod central la cel mai îndepărtat.
4. Gradul vârfului este numărul de margini atașate vârfului.
În graficele de rețele de drumuri, gradul mediu de toate nodurile situate în zona de la 2 la 4. Este destul de firesc - este dificil și costisitor de a construi intersecții cu o mulțime de drumuri feeder, nu mai puțin dificil să se utilizeze apoi această rețea de drumuri. Graficele, cu un grad mediu scăzut de un vârf este rarefiat, după cum putem vedea grafice ale rețelelor de drumuri la fel ca asta.
Problema 1. Găsiți raza și centrul graficului din matricea cea mai mică distanță
Rețineți că graficul poate avea mai multe centre, dar dorim să găsim oricare dintre acestea.
Aceasta nu este cea mai rapidă cale. Pentru ceea ce este necesar mai rapid, dacă, aparent, raza și centrul graficului pot fi găsite odată? De exemplu, există probleme și algoritmi asupra lor, unde în timpul căutării, nodurile sunt "reconectate" în mod constant în grupuri, iar criteriul pentru fiecare grup este raza sa. În acest caz, raza este recalculată de mai multe ori, iar viteza căutării sale devine un parametru important. Cum să găsiți raza mai repede?
Să vedem, în detrimentul a ceea ce se dovedește. Luați în considerare valorile într-un rând al matricei MKR, cu alte cuvinte, luați în considerare distanțele de la un vârf la celelalte. Este ușor să se demonstreze că raza graficului nu poate fi mai mare decât valoarea maximă din această linie și nu poate fi mai mică decât valoarea minimă din această linie. Din punct de vedere matematic, am găsit limitele superioare și inferioare ale unui număr și, dacă coincid, găsim un număr.
Să presupunem că am găsit valori numai în două rânduri A și B. În acest caz, valoarea maximă în rândul A este valoarea minimă din rândul B (această valoare va fi la intersecția coloanei A și liniei B). Este ușor să demonstrați că A este centrul unui grafic, iar valoarea găsită este raza sa. Problema este rezolvată.
În general, și din punctul de vedere al matematicii, acest lucru, desigur, nu este așa. Este posibil să construiți un grafic teoretic în care va trebui să utilizați o mulțime de rânduri de B (aproape tot, cu excepția lui A). Este imposibil să construim o rețea de drumuri reale de acest fel - banii nu sunt suficienți.
Ultima sarcină rămâne. Cât de repede găsiți aceste linii de succes B1, B2 etc. Pentru graficele rețelelor rutiere reale, acest lucru este foarte simplu și rapid. Acestea sunt vârfurile cât mai îndepărtate posibil, dar nu neapărat cele mai îndepărtate (din punct de vedere matematic, nu trebuie să găsim diametrul graficului). Luăm orice vârf, găsim pentru el cel mai îndepărtat, pentru cel nou, cel mai îndepărtat și așa mai departe, până când o pereche de vârfuri sunt cele mai îndepărtate unul pentru celălalt.
Am obținut o pereche de vârfuri Bl și B2. Vom găsi vectorul M pentru pereche, așa cum este descris mai sus. Un rând în care ne găsim min (M (i)) - un pretendent la centru, notată cu A. Dacă în coloana O valoare de min (M (i)) - maxim, ați găsit centrul și raza. Dacă nu, atunci valoarea maximă din coloana A corespunde distanței față de celălalt vârf (nu B1 și nu B2). Deci, avem un nou B3 de sus a listei pentru a găsi vectorul M. Alternativ, puteți căuta top B3 și cele mai îndepărtate și în cazul în care nu este B1 și B2, adauga ca B4. Astfel, creștem lista de vârfuri B până când se găsesc centrul și raza.
Problema 2. Căutați matricea celor mai scurte distanțe
Cele mai populare algoritmi pentru căutarea MKR (de exemplu, Floyd-Worshell) sunt descrise aici. Toate sunt universale, iar unul dintre ele - algoritmul Dijkstra cu un heap binar - ia în considerare un lucru ca un grafic slab. Cu toate acestea, el nu utilizează, de asemenea, caracteristicile rețelelor rutiere.
Le vom folosi și pe un algoritm complet diferit, iar pe grafice existente obținem accelerație de zeci de ori în comparație cu algoritmul Dijkstra. Observăm deodată că particularitatea acestui algoritm este că acesta caută MKR, și imediat toate și exact (adică, nu aproximativ, nu euristic).
Să luăm în considerare ideea principală a algoritmului. Esența sa este eliminarea vârfurilor graficului fără a schimba distanțele cele mai scurte pentru punctele rămase. Dacă facem acest lucru, amintindu-ne care puncte și la ce distanțe era atașat vârful de la distanță, putem șterge toate punctele cu excepția unuia și apoi le putem colecta înapoi în grafic, dar cu distanțele deja calculate.
Să începem cu una simplă, cu un vârf cu gradul 1. Poate fi șters în orice caz. Prin aceasta, nu trece calea cea mai scurtă, cu excepția căii spre vârful însuși, și ei merg exact prin vârful la care era atașat vârful îndepărtat.
Fie A un vârf al gradului 2 și alăturați-l la vârfurile B1 și B2. Dacă ruta B1-A-B2 este mai lungă sau egală cu marginea B1-B2, nu traversează rutele prin punctul A, cu excepția rutelor către punctul A (restul trec prin B1-B2). Prin urmare, punctul A poate fi șters. Altfel, adică dacă scurt coaste B1-B2 și B2 B1 B1-A-B2 nu, nodul A poate fi îndepărtată prin stabilirea greutății nervurilor B2-B1 egală cu suma greutăților: | B1-A | + | A-B2 |. Traseul de la A la alte puncte trece prin B1 sau prin B2, dacă distanțele pentru B1 și B2 sunt cunoscute, distanțele de la A sunt la fel de ușor de calculat.
Prin același principiu, este posibil să se elimine un vârf de orice grad, înlocuind, dacă este necesar, Bi-A-Bj de Bi-Bj. Adevărat, trebuie să înțelegem că cu cât este mai mare gradul de vârf, cu atât mai multe margini posibile trebuie să fie verificate. Pentru un nod de grad n acest număr este egal cu n (n-1) / 2.
Teoretic, în acest fel, puteți șterge toate nodurile din orice grafic, însă, în general, ne aflăm în dificultate datorită creșterii numărului de muchii. Dacă eliminați un vârf cu o putere de n, gradul vârfurilor adiacente vârfului care este șters poate: să scadă cu -1, să nu se modifice, să crească la n-2. Rezultă că, atunci când ștergerea nodurile de gradul 3 și mai mare, gradul de nodurile rămase, în general, este în creștere, graficul devine mai puțin rarefiat și, în cele din urmă, eliminarea vârfurile transforma într-o sarcină destul de laborioasa. Algoritmul, în general, este extrem de consumator de timp și aproape inutil, dar este cazul în general.
Graficele rețelelor rutiere au o caracteristică unică de acest tip: multe vârfuri pot fi îndepărtate nu numai fără creștere, dar și cu grade descrescătoare de vârfuri adiacente. Și dacă un anumit vârf nu poate fi "șters" cu succes, acesta poate fi șters "cu succes" mai târziu, după eliminarea unor vârfuri adiacente acestuia.
În consecință, pur și simplu avem nevoie de fiecare etapă pentru a selecta corect nodurile pentru ștergere, începând cu cele care sunt șterse mai "cu succes".
Algoritmul în sine poate fi văzut în detaliu aici. Descrie modul în care se elimină un vârf, păstrând distanțele și căile dintre cele rămase. Acest proces se numește dezasamblare. Acesta descrie modul de restaurare a graficului atunci adăugând vârfurile în ordine inversă unul câte unul, cum să recalculează MKR. Acest proces se numește ansamblu.
Rezultatele utilizării algoritmului pe graficele rețelelor rutiere din SUA prin referință sunt de asemenea date acolo.
Dacă luăm în considerare rețelele rutiere nu ca grafice în general, ci ca grafice cu anumite proprietăți speciale, putem crea și aplica cu succes algoritmi mai eficienți pentru multe probleme practice.
Articole similare
Trimiteți-le prietenilor: