Problemet med den bredeste vej

Det bredeste vejproblem  er problemet med at finde en vej mellem to udvalgte hjørner i en vægtet graf , der maksimerer vægten af ​​den mindst vægtede kant af grafen (hvis vi betragter kantens vægt som vejens bredde, så er problemet er at vælge den bredeste vej, der forbinder to spidser). Problemet med den bredeste vej er også kendt som flaskehalsproblemet eller problemet med maksimal kapacitet . Det er muligt at tilpasse korteste vejs algoritmer til at beregne gennemløb ved at bruge en speciel værdi i stedet for vejlængde [1] . I mange tilfælde er hurtigere algoritmer dog mulige.

For eksempel, i en graf, der repræsenterer forbindelser mellem routere på internettet , hvor vægten af ​​en kant repræsenterer båndbredden af ​​en forbindelse mellem to routere, svarer problemet med at finde den bredeste vej til problemet med at finde en ende-til- endesti mellem to internetnoder, der har den bredest mulige båndbredde [2] [3] . Den mindste kantvægt på denne sti er kendt som kapaciteten eller bredden af ​​banen. Sammen med applikationer inden for netværksrouting er det bredeste vejproblem også en vigtig komponent i Schulze 's metode til at bestemme vinderen i flervejsvalg [4] , den er blevet brugt i digital billedjustering [5] , metabolisk flowanalyse [6] og for at beregne maksimale strømme [7] .

Det nært beslægtede minimax-stiproblem beder om en sti, der minimerer den maksimale vægt af enhver af kanterne (kan tolkes som at finde den glatteste vej med minimale op- og nedadgående vinkler). Dette problem finder anvendelse i trafikplanlægning [8] . Enhver algoritme for det bredeste vejproblem kan konverteres til en minimax-stialgoritme og omvendt ved at vende betydningen af ​​alle vægtsammenligninger, der er foretaget i algoritmen, eller tilsvarende ved at ændre vægtene til negative værdier.

Urettede grafer

I en urettet graf kan den bredeste sti findes som en sti mellem to hjørner i grafens maksimale spændingstræ , og minimax sti kan findes som en sti mellem to spidser i minimumspændingstræet [9] [10] [11 ] .

I enhver graf, rettet eller ej, er der en simpel algoritme til at finde den bredeste vej, hvis vægten af ​​kanten med minimumsværdien er kendt - fjern blot alle kanter med en mindre værdi og søg efter en vej blandt de resterende kanter ved hjælp af bredden -første søgning eller dybde -første søgning . Der er en lineær tidsalgoritme baseret på denne test til at finde den bredeste st - t sti i en urettet graf, der ikke bruger et maksimalt spændingstræ. Den grundlæggende idé med algoritmen er at anvende en lineær tidsalgoritme til at finde en vej til medianen af ​​grafens kantvægte, og derefter enten fjerne alle mindre kanter eller formindske alle større kanter alt efter om stien eksisterer eller ej, og bearbejd derefter den resulterende mindre graf [10] [12] [13] rekursivt .

Fernandez, Garfinkel og Arbiol [14] brugte flaskehalsproblemet i urettede grafer til at opnå digital luftbilledaliasing , som kombinerer flere billeder af overlappende områder. I underproblemet, som det bredeste vejproblem anvendes på, er de to billeder allerede blevet konverteret til det samme koordinatsystem . Det eneste, der er tilbage, er at vælge en søm , en kurve, der passerer gennem overlapningen og adskiller et billede fra et andet. Pixels på den ene side af sømmen kopieres fra ét billede, og pixels på den anden side af sømmen kopieres fra et andet billede. I modsætning til andre billedjusteringsmetoder, hvor der beregnes gennemsnit af pixels fra begge billeder, tager denne metode et ægte fotografisk billede af hver del af det fotograferede område. I metoden tildeles vægte til kanterne af gitteret med værdier, der estimerer, hvor meget sømmen vil vises visuelt på kanten, og finder den bredeste vej for disse vægte. Brug af denne vej som en søm, frem for den mere traditionelle korteste vej, resulterer i, at deres system finder en søm, der er svær at se, i stedet for at øge kvaliteten af ​​en del af billedet på bekostning af en anden [5] .

Løsning af minimax-problemet mellem to hjørner af et gittergitter kan bruges til at finde den svage Fréchet-afstand mellem to stiplede linjer . Her repræsenterer hvert hjørne af gitteret et par segmenter, et fra hver kæde, og kantvægten repræsenterer den Fréchet-afstand, der kræves for at gå fra et par segmenter til et andet [15] .

Hvis alle kantvægte af en ikke-rettet graf er positive , danner minimax-afstandene mellem par af punkter (maksimale kantvægte af minimax-baner) et ultrametrisk mellemrum . Omvendt dannes hvert endeligt ultrametrisk rum ud fra minimax afstande på denne måde [16] . En datastruktur bygget ud fra et mindst spændende træ gør det muligt at forespørge om minimumsafstanden mellem ethvert par af hjørner i konstant tid ved at bruge mindst fælles forfaderforespørgsler i et kartesisk træ . Roden af ​​et kartesisk træ repræsenterer den tungeste kant af det mindst spændende træ, og rodens børn er kartesiske træer rekursivt konstrueret af undertræer af de mindst spændende træer dannet ved at fjerne den tungeste kant. Bladene på det kartesiske træ repræsenterer hjørnerne af inputgrafen, og minimumsafstanden mellem to hjørner er lig med vægten af ​​den kartesiske træknude, der er deres mindst fælles forfader. Når kanterne af det mindst spændende træ er sorteret, kan dette kartesiske træ bygges i lineær tid [17] .

Styrede grafer

I rettede grafer kan den maksimale spændingstræ-løsning ikke bruges. I stedet kendes nogle forskellige algoritmer. Spørgsmålet om, hvilken algoritme der skal vælges, afhænger af, om stiens start- og sluthjørner er faste, eller om det er nødvendigt at finde stier fra flere start- og sluthjørner på samme tid.

Alle par

Det bredeste vejproblem for alle par har anvendelser i Schulzes metode til at bestemme vinderen i flervejsvalg , hvor vælgere vurderer kandidater i en fortrinsstemme . Schulze's metode konstruerer en komplet rettet graf , hvor toppunkterne repræsenterer kandidater, og hvilke som helst to hjørner er forbundet med en kant. Hver kant er rettet fra vinderen til taberen i dueller mellem to kandidater og er markeret af vinderens fordel i konkurrencen. Metoden beregner derefter den bredeste vej mellem alle par af hjørner, og vinderen er den kandidat, der har den bredeste vej med hver af modstanderne [4] . Valgresultater, der bruger denne metode, stemmer overens med Condorcet-metoden  - den kandidat, der vinder alle kampene, bliver automatisk vinderen af ​​valget, men metoden giver dig mulighed for at vælge vinderen, når Condorcet-metoden ikke virker [18] . Schulze-metoden er blevet brugt af flere organisationer, herunder Wikimedia Foundation [19] .

For at beregne den bredeste vej for alle par af knudepunkter i tætte rettede grafer, såsom i afstemningsapplikationer, kører den asymptotisk hurtigste tilgang i tid , hvor er en metrik for hurtige matrixmultiplikationsalgoritmer . Når man bruger de bedst kendte matrixmultiplikationsalgoritmer, bliver disse tidsgrænser til [20] . For tidlige algoritmer, der også brugte hurtig matrixmultiplikation til at fremskynde at finde de bredeste veje for alle par, se Wassilewska, Williams og Yuster [21] og kapitel 5 af Wassilewska [22] . Referenceimplementeringen af ​​Schulze-metoden bruger en modificeret version af den mere simple Floyd-Warshall-algoritme , der kører i tid [4] . For sparsomme grafer kan flere anvendelser af den bredeste søgealgoritme for en enkelt kilde bruges mere effektivt.

Én kilde

Hvis kanterne er sorteret efter deres vægt, så kan en modificeret version af Dijkstras algoritme beregne flaskehalsene mellem det tildelte startpunkt og alle andre hjørner i grafen i lineær tid. Nøgleideen bag at fremskynde med den sædvanlige version af Dijkstras algoritme er, at sekvensen af ​​flaskehalse op til hvert toppunkt i den rækkefølge, som disse hjørner optræder i algoritmen, er en monoton undersekvens sorteret efter vægten af ​​kantsekvensen. Derfor kan prioritetskøen i Dijkstras algoritme implementeres som en containerkø , et array nummereret fra 1 til m (antal kanter i grafen), hvor arraycelle i indeholder hjørner, hvis "flaskehalse" er lig med vægten af kanten med position i i sorteret rækkefølge. Denne metode løser det bredeste vejproblem med samme hastighed som sortering . For eksempel, hvis kantvægtene er heltal, så vil den bundne tid for heltalssortering af en liste med m heltal også være et estimat for dette problem [13] .

Enkelt kilde og enkelt destination

Berman og Handler [23] foreslog, at udrykningskøretøjer og ambulancer skulle bruge minimax-stien, når de returnerede fra alarmcentralen til basen. I disse tilfælde er returtiden mindre vigtig end responstiden, hvis der opstår et andet opkald, mens maskinen er i gang med at returnere. Ved brug af en minimax-sti, hvor vægten er den maksimale rejsetid fra kanten til det fjerneste punkt af et muligt opkald, er det muligt at planlægge ruten, så den størst mulige forsinkelse mellem modtagelsen af ​​et opkald og ankomsten af ​​bilen er minimal [8] . Ulla, Lee og Hassoon [24] brugte maksimale veje til at modellere kæden af ​​dominerende reaktioner i metaboliske netværk . I deres model er vægten af ​​en kant den frie energi af den metaboliske reaktion repræsenteret af kanten [6] .

En anden anvendelse af de bredeste veje opstår i Ford-Fulkerson-algoritmen for det maksimale flowproblem . Gradvist stigende flow langs en vej med maksimal kapacitet i reststrømsnettet resulterer i en lille grænse for antallet af trin, der er nødvendige for at finde det maksimale flow. Her antages kantkapaciteterne at være heltal, der ikke overstiger U . Denne analyse afhænger dog ikke af at finde den nøjagtige maksimale kapacitans. Enhver vej med en kapacitet, der adskiller sig fra maksimum med en konstant faktor, er egnet. Kombination af disse tilnærmelsesideer med den korteste vej-inkrementmetode i Edmonds-Karp- algoritmen resulterer i en maksimal flow-algoritme med køretid [7] .

Det er muligt at finde maksimale kapacitetsveje og minimaksveje med en enkelt kilde og en enkelt destination meget effektivt selv i beregningsmodeller, der kun tillader sammenligning af vægten af ​​inputgrafkanterne og ikke aritmetiske med dem [13] [25] . Algoritmen fungerer på et sæt S af kanter, der vides at indeholde flaskehalskanten af ​​den optimale sti. Til at begynde med består S af alle m kanter af grafen. Ved hver iteration af algoritmen opdeles S i en ordnet sekvens af delmængder af omtrent samme størrelse. Antallet af delmængder i denne partition er valgt således, at alle partitionspunkter mellem delmængder kan findes ved at finde medianer flere gange i O ( m ) tid . Algoritmen genberegner derefter vægtene af alle grafens kanter med indekset for den delmængde, der indeholder kanten, og bruger den modificerede Dijkstra-algoritme på grafen med de opdaterede vægte. Ud fra resultaterne af disse beregninger er det muligt i lineær tid at beregne, hvilken af ​​delmængderne der indeholder flaskehalskantvægten. Algoritmen erstatter derefter S med en delmængde Si , der indeholder flaskehalsvægten, og starter en ny iteration med dette sæt S . Antallet af delmængder, som S kan opdeles i, kan stige eksponentielt med hvert trin, således at antallet af iterationer er proportionalt med den itererede logaritme af , og den samlede udførelsestid vil være [25] . I en beregningsmodel, hvor vægten af ​​hver kant er et maskinelt heltal, kan brugen af ​​iterative logaritmer i denne algoritme erstattes af Hahn og Thorup [26] listeopdelingsteknikken , som gør det muligt at opdele S i mindre dele s Si i ét trin, hvilket resulterer i lineær fælles grænse i tid [27] .

Sæt af euklidiske punkter

En variant af minimax-vejproblemet blev overvejet for et sæt punkter på det euklidiske plan . Som i det urettede grafproblem, kan dette euklidiske minimax-stiproblem løses effektivt ved at finde et euklidisk minimumspændende træ  - enhver sti i træet er en minimax-sti. Problemet bliver dog mere kompliceret, hvis man ønsker, at stien ikke kun skal minimere den øvre længde, men også blandt stier med samme øvre længde minimere eller nogenlunde minimere stiens samlede længde. Løsningen kan tilnærmes ved hjælp af det geometriske spændingstræ [28] .

I talteorien spørger det uløste gaussiske voldgravproblem om minimakslængden af ​​minimaksveje i gaussiske primtal er afgrænset . Det vil sige, er der en konstant B , således at for ethvert par p og q i et uendeligt sæt af euklidiske punkter defineret af gaussiske primtal, har minimaksvejen i gaussiske primtal mellem p og q højst kantlængde B ? [29] .

Noter

  1. ↑ Pollack, 1960 , s. 733-736.
  2. ↑ Shacham, 1992 , s. 1217-1221.
  3. ↑ Wang, Crowcroft, 1995 , s. 2129-2133.
  4. ↑ 1 2 3 Schulze, 2011 , s. 267-303.
  5. ↑ 1 2 Fernandez, Garfinkel, Arbiol, 1998 , s. 293-304.
  6. ↑ 1 2 Ullah, Lee, Hassoun, 2009 , s. 144-150.
  7. ↑ 1 2 Ahuja, Magnanti og Orlin, 1993 , s. 210-212.
  8. ↑ 1 2 Berman, Handler, 1987 , s. 115-122.
  9. ↑ Hu, 1961 , s. 898-900.
  10. ↑ 12 Punnen , 1991 , s. 402-404.
  11. ↑ Malpani, Chen, 2002 , s. 175-180.
  12. ↑ Camerini, 1978 , s. 10-14.
  13. ↑ 1 2 3 Kaibel, Peinhardt, 2006 .
  14. ↑ Fernandez, Garfinkel, Arbiol, 1998 .
  15. ↑ Alt, Godau, 1995 , s. 75-91.
  16. ↑ Leclerc, 1981 , s. 5-37, 127.
  17. ↑ Demaine, Landau, Weimann, 2009 , s. 341-353.
  18. ↑ Mere præcist er den eneste mulighed, hvor Schulze's metode fejler, når to kandidater har stier af samme bredde til hinanden.
  19. ↑ Se Jesse Plamondon-Willard, Bestyrelsesvalg for at bruge præferenceafstemning , maj 2008; Mark Ryan, 2008 Wikimedia Board Valgresultater , juni 2008; Bestyrelsesvalg 2008 , juni 2008; og bestyrelsesvalg 2009 , august 2009.
  20. ↑ Duan, Pettie, 2009 , s. 384-391.
  21. ↑ Vassilevska, Williams, Yuster, 2007 , s. 585-589.
  22. ↑ Vassilevska, 2008 .
  23. ↑ Berman, Handler, 1987 .
  24. ↑ Ullah, Lee, Hassoun, 2009 .
  25. ↑ 1 2 Gabow, Tarjan, 1988 , s. 411-417.
  26. ↑ Han, Thorup, 2002 .
  27. ↑ Han, Thorup, 2002 , s. 135-144.
  28. ↑ Bose, Maheshwari, Narasimhan, Smid, Zeh, 2004 , s. 233-249.
  29. ↑ Gethner, Wagon, Wick, 1998 , s. 327-337.

Litteratur