Problema căii celei mai largi

Cea mai largă problemă a căii  este problema găsirii unei căi între două vârfuri selectate într-un grafic ponderat care maximizează greutatea marginii cel mai puțin ponderate a graficului (dacă considerăm greutatea muchiei ca lățimea drumului, atunci problema este de a alege cel mai lat drum care leagă două vârfuri). Problema cu cea mai largă cale este cunoscută și sub denumirea de problema blocajului sau problema capacității maxime . Este posibil să se adapteze algoritmii de calea cea mai scurtă pentru a calcula debitul utilizând o valoare specială în loc de lungimea căii [1] . Cu toate acestea, în multe cazuri sunt posibili algoritmi mai rapizi.

De exemplu, într-un grafic care reprezintă conexiuni între routere de pe Internet , în care greutatea unei margini reprezintă lățimea de bandă a unei conexiuni între două routere, problema găsirii celei mai largi căi corespunde problemei găsirii unui end-to- cale finală între două noduri de Internet care are cea mai mare lățime de bandă posibilă [2] [3 ] . Cea mai mică greutate de margine de pe această cale este cunoscută ca capacitatea sau lățimea traseului. Alături de aplicațiile în rutarea rețelei, problema căii celei mai largi este, de asemenea, o componentă importantă a metodei lui Schulze pentru determinarea câștigătorului în alegerile cu mai multe sensuri [4] , a fost folosită în alinierea imaginilor digitale [5] , analiza fluxului metabolic [6] și pentru a calcula debitele maxime [7] .

Problema traseului minimax strâns legată solicită o cale care să minimizeze greutatea maximă a oricărei margini (poate fi interpretată ca găsirea celui mai neted drum cu unghiuri minime de urcare și coborâre). Această problemă își găsește aplicație în planificarea traficului [8] . Orice algoritm pentru problema de cale cea mai largă poate fi convertit într-un algoritm de cale minimax și invers, inversând sensul tuturor comparațiilor de pondere întreprinse în algoritm sau, în mod echivalent, prin schimbarea ponderilor la valori negative.

Grafice nedirecționate

Într -un grafic nedirecționat , calea cea mai largă poate fi găsită ca o cale între două vârfuri în arborele de întindere maxim al graficului , iar calea minimax poate fi găsită ca o cale între două vârfuri în arborele de întindere minim [9] [10] [11 ] .

În orice grafic, direcționat sau nu, există un algoritm simplu pentru a găsi calea cea mai largă dacă se cunoaște greutatea muchiei cu valoarea minimă - pur și simplu eliminați toate muchiile cu o valoare mai mică și căutați o cale printre muchiile rămase folosind lățimea -prima căutare sau adâncime -prima căutare . Există un algoritm de timp liniar bazat pe acest test pentru a găsi cea mai largă cale s - t într-un grafic nedirecționat care nu utilizează un arbore de întindere maximă. Ideea de bază a algoritmului este de a aplica un algoritm de timp liniar pentru a găsi o cale către mediana greutăților marginilor graficului și apoi fie să eliminați toate muchiile mai mici, fie să micșorați toate muchiile mai mari, în funcție de faptul că calea există sau nu și apoi procesează recursiv pe cel mai mic rezultat.grafic [10] [12] [13] .

Fernandez, Garfinkel și Arbiol [14] au folosit problema blocajului în graficele nedirecționate pentru a obține aliasarea imaginilor aeriene digitale , care combină mai multe imagini ale zonelor suprapuse. În subproblema căreia i se aplică cea mai largă problemă de cale, cele două imagini au fost deja convertite în același sistem de coordonate . Tot ce rămâne este să selectați o cusătură , o curbă care trece prin suprapunere și separă o imagine de alta. Pixelii de pe o parte a cusăturii sunt copiați dintr-o imagine, iar pixelii de pe cealaltă parte a cusăturii sunt copiați dintr-o altă imagine. Spre deosebire de alte metode de aliniere a imaginii, în care pixelii ambelor imagini sunt mediate, această metodă realizează o imagine fotografică reală a fiecărei părți a zonei fotografiate. În metodă, greutățile sunt atribuite marginilor rețelei cu valori care estimează cât de mult va apărea vizual cusătura pe margine și găsesc calea cea mai largă pentru aceste greutăți. Folosind această cale ca o cusătură, mai degrabă decât cea mai tradițională cale mai scurtă, are ca rezultat sistemul lor să găsească o cusătură greu de văzut, în loc să mărească calitatea unei părți a imaginii în detrimentul alteia [5] .

Rezolvarea problemei minimax dintre două colțuri ale unei rețele de rețea poate fi folosită pentru a găsi distanța Fréchet slabă dintre două linii întrerupte . Aici, fiecare vârf al rețelei reprezintă o pereche de segmente, câte unul din fiecare lanț, iar greutatea marginii reprezintă distanța Fréchet necesară pentru a trece de la o pereche de segmente la alta [15] .

Dacă toate greutățile de margine ale unui grafic nedirecționat sunt pozitive , atunci distanțele minimax dintre perechi de puncte (greutățile maxime de margine ale căilor minimax) formează un spațiu ultrametric . În schimb, fiecare spațiu ultrametric finit este format din distanțe minimax în acest fel [16] . O structură de date construită dintr-un arbore care se întinde cel mai puțin permite interogarea distanței minime dintre orice pereche de vârfuri în timp constant utilizând interogări de strămoș cel mai puțin obișnuit într-un arbore cartezian . Rădăcina unui arbore cartezian reprezintă marginea cea mai grea a arborelui cel mai puțin întins, iar copiii rădăcinii sunt arbori cartezieni construiți recursiv din subarbori ai arborilor cel mai puțin întins formați prin îndepărtarea marginii celei mai grele. Frunzele arborelui cartezian reprezintă vârfurile graficului de intrare, iar distanța minimax dintre două vârfuri este egală cu greutatea nodului arborelui cartezian care este strămoșul lor cel mai puțin comun. Odată sortate marginile celui mai mic arbore care se întinde, acest arbore cartezian poate fi construit în timp liniar [17] .

Grafice dirijate

În graficele direcționate , soluția maximă a arborelui de întindere nu poate fi utilizată. În schimb, sunt cunoscuți niște algoritmi diferiți. Întrebarea ce algoritm să alegeți depinde dacă vârfurile de început și de sfârșit ale căii sunt fixe sau dacă este necesar să găsiți căi de la mai multe vârfuri de început și de sfârșit în același timp.

Toate cuplurile

Cea mai largă problemă a căii pentru toate perechile are aplicații în metoda lui Schulze pentru determinarea câștigătorului în alegerile cu mai multe sensuri , în care alegătorii evaluează candidații într-un vot preferențial . Metoda lui Schulze construiește un graf complet direcționat , unde vârfurile reprezintă candidați și oricare două vârfuri sunt conectate printr-o muchie. Fiecare margine este direcționată de la câștigător la învins în dueluri între doi candidați și este marcată de avantajul câștigătorului în competiție. Metoda calculează apoi calea cea mai largă între toate perechile de vârfuri și câștigătorul este candidatul care are cele mai largi căi cu fiecare dintre adversari [4] . Rezultatele alegerilor prin această metodă sunt în concordanță cu metoda Condorcet  - candidatul care câștigă toate luptele devine automat câștigătorul alegerilor, dar metoda vă permite să alegeți câștigătorul atunci când metoda Condorcet nu funcționează [18] . Metoda Schulze a fost folosită de mai multe organizații, inclusiv de Fundația Wikimedia [19] .

Pentru a calcula calea cea mai largă pentru toate perechile de noduri în grafice dense direcționate, cum ar fi aplicațiile de vot, cea mai rapidă abordare asimptotic rulează în timp , unde este o metrică pentru algoritmii de multiplicare rapidă a matricei . Când se folosesc cei mai cunoscuți algoritmi de multiplicare a matricei, aceste limite de timp se transformă în [20] . Pentru algoritmii timpurii care au folosit și multiplicarea rapidă a matricei pentru a accelera găsirea celor mai largi căi pentru toate perechile, vezi Wassilewska, Williams și Yuster [21] și Capitolul 5 din Wassilewska [22] . Implementarea de referință a metodei Schulze folosește o versiune modificată a algoritmului mai simplu Floyd-Warshall care rulează în timp [4] . Pentru graficele rare , aplicarea multiplă a algoritmului de căutare a căii cele mai largi pentru o singură sursă poate fi utilizată mai eficient.

O sursă

Dacă muchiile sunt sortate după greutatea lor, atunci o versiune modificată a algoritmului lui Dijkstra poate calcula blocajele dintre vârful de pornire atribuit și toate celelalte vârfuri din grafic în timp liniar. Ideea cheie din spatele accelerării cu versiunea obișnuită a algoritmului lui Dijkstra este că succesiunea blocajelor până la fiecare vârf în ordinea în care acele vârfuri apar în algoritm este o subsecvență monotonă sortată după ponderile secvenței de muchii. Prin urmare, coada de prioritate a algoritmului lui Dijkstra poate fi implementată ca o coadă container , o matrice numerotată de la 1 la m (număr de muchii din grafic), unde celula matricei i conține vârfuri ale căror „gâturi de sticlă” sunt egale cu greutatea a muchiei cu poziţia i în ordine sortată. Această metodă rezolvă problema căii celei mai largi cu aceeași viteză ca sortarea . De exemplu, dacă greutățile marginilor sunt numere întregi, atunci timpul legat pentru sortarea întregilor unei liste de m numere întregi va fi, de asemenea, o estimare pentru această problemă [13] .

Sursă unică și destinație unică

Berman și Handler [23] au sugerat ca vehiculele de urgență și ambulanțele să folosească calea minimax atunci când se întorc de la punctul de apel la bază. În aceste cazuri, timpul de întoarcere este mai puțin important decât timpul de răspuns dacă apare un alt apel în timp ce aparatul este în proces de revenire. Când utilizați o cale minimax, în care greutatea este timpul maxim de călătorie de la marginea până la punctul cel mai îndepărtat al unui apel posibil, este posibil să planificați traseul astfel încât întârzierea maximă posibilă între primirea unui apel și sosirea mașinii este minim [8] . Ulla, Lee și Hassoon [24] au folosit căi maxime pentru a modela lanțul de reacții dominante în rețelele metabolice . În modelul lor, greutatea unei muchii este energia liberă a reacției metabolice reprezentată de muchie [6] .

O altă aplicație a celor mai largi căi apare în algoritmul Ford-Fulkerson pentru problema debitului maxim . Creșterea treptată a debitului de-a lungul unei căi cu capacitate maximă în rețeaua de curgere reziduală are ca rezultat o limită mică a numărului de incremente necesare pentru a găsi debitul maxim. Aici se presupune că capacitățile marginilor sunt numere întregi care nu depășesc U . Cu toate acestea, această analiză nu depinde de găsirea exactă a capacității maxime. Orice cale cu o capacitate care diferă de maximă printr-un factor constant este potrivită. Combinând aceste idei de aproximare cu metoda de creștere a drumului cel mai scurt a algoritmului Edmonds-Karp rezultă un algoritm de debit maxim cu timp de rulare [7] .

Este posibil să se găsească căi de capacitate maximă și căi minimax cu o singură sursă și o singură destinație foarte eficient chiar și în modelele de calcul care permit doar compararea greutăților muchiilor graficului de intrare, și nu aritmetică cu acestea [13] [25] . Algoritmul operează pe un set S de muchii despre care se știe că conțin marginea de blocare a căii optime. Inițial , S este format din toate m muchiile graficului. La fiecare iterație a algoritmului, S este împărțit într-o secvență ordonată de submulțimi de dimensiune aproximativ egală. Numărul de subseturi din această partiție este ales astfel încât toate punctele de partiție dintre subseturi să poată fi găsite prin găsirea medianelor de mai multe ori în timp O ( m ) . Algoritmul recalculează apoi greutățile tuturor muchiilor graficului după indicele subsetului care conține muchia și utilizează algoritmul Dijkstra modificat pe grafic cu ponderile actualizate. Pe baza rezultatelor acestor calcule, este posibil să se calculeze în timp liniar care dintre subseturi conține greutatea marginii gâtului. Algoritmul înlocuiește apoi S cu un submult Si care conține greutatea blocajului și începe o nouă iterație cu această mulțime S . Numărul de submulțimi în care S poate fi partiționat poate crește exponențial cu fiecare pas, astfel încât numărul de iterații este proporțional cu logaritmul iterat al lui , iar timpul total de execuție va fi [25] . Într-un model de calcul în care greutatea fiecărei margini este un număr întreg de mașină, utilizarea logaritmilor iterativi în acest algoritm poate fi înlocuită cu tehnica de partiționare a listelor Hahn și Thorup [26] , care permite partiția lui S în părți mai mici s S i într-o singură etapă, rezultând o limită comună liniară în timp [27] .

Seturi de puncte euclidiene

O variantă a problemei traiectoriei minimax a fost luată în considerare pentru un set de puncte din planul euclidian . Ca și în problema graficului nedirecționat, această problemă a căii minimax euclidiene poate fi rezolvată eficient prin găsirea unui arbore de acoperire minim euclidian  - orice cale din arbore este o cale minimax. Cu toate acestea, problema devine mai complicată dacă se dorește ca calea nu numai să minimizeze lungimea superioară, ci și, printre căile cu aceeași lungime superioară, să minimizeze sau să minimizeze aproximativ lungimea totală a căii. Soluția poate fi aproximată folosind arborele de întindere geometric [28] .

În teoria numerelor, problema nerezolvată a șanțurilor gaussiene întreabă dacă lungimea minimax a căilor minimax în numerele prime Gaussiene este mărginită . Adică, există o constantă B astfel încât, pentru orice pereche p și q dintr-o mulțime infinită de puncte euclidiene definite de numere prime gaussiene, calea minimax în numere prime gausse între p și q are lungimea muchiei de cel mult B ? [29] .

Note

  1. ↑ Pollack, 1960 , p. 733–736.
  2. ↑ Shacham, 1992 , p. 1217–1221.
  3. ↑ Wang, Crowcroft, 1995 , p. 2129–2133.
  4. ↑ 1 2 3 Schulze, 2011 , p. 267–303.
  5. ↑ 1 2 Fernandez, Garfinkel, Arbiol, 1998 , p. 293–304.
  6. ↑ 1 2 Ullah, Lee, Hassoun, 2009 , p. 144–150.
  7. ↑ 1 2 Ahuja, Magnanti și Orlin, 1993 , p. 210–212.
  8. ↑ 1 2 Berman, Handler, 1987 , p. 115–122.
  9. ↑ Hu, 1961 , p. 898–900.
  10. ↑ 12 Punnen , 1991 , p. 402–404.
  11. ↑ Malpani, Chen, 2002 , p. 175–180.
  12. ↑ Camerini, 1978 , p. 10–14.
  13. ↑ 1 2 3 Kaibel, Peinhardt, 2006 .
  14. ↑ Fernandez, Garfinkel, Arbiol, 1998 .
  15. ↑ Alt, Godau, 1995 , p. 75–91.
  16. ↑ Leclerc, 1981 , p. 5–37, 127.
  17. ↑ Demaine, Landau, Weimann, 2009 , p. 341–353.
  18. ↑ Mai precis, singura posibilitate în care metoda lui Schulze eșuează este atunci când doi candidați au căi de lățime egală unul față de celălalt.
  19. ↑ Vezi Jesse Plamondon-Willard, Board election to use preference voting , mai 2008; Mark Ryan, Rezultatele alegerilor Consiliului Wikimedia 2008 , iunie 2008; Alegerile Consiliului de Administrație 2008 , iunie 2008; și alegerile Consiliului de administrație din 2009 , august 2009.
  20. ↑ Duan, Pettie, 2009 , p. 384–391.
  21. ↑ Vassilevska, Williams, Yuster, 2007 , p. 585–589.
  22. ↑ Vassilevska, 2008 .
  23. ↑ Berman, Handler, 1987 .
  24. ↑ Ullah, Lee, Hassoun, 2009 .
  25. ↑ 1 2 Gabow, Tarjan, 1988 , p. 411–417.
  26. ↑ Han, Thorup, 2002 .
  27. ↑ Han, Thorup, 2002 , p. 135–144.
  28. ↑ Bose, Maheshwari, Narasimhan, Smid, Zeh, 2004 , p. 233–249.
  29. ↑ Gethner, Wagon, Wick, 1998 , p. 327–337.

Literatură