Problém nejširší cesty

Problém nejširší cesty  je problém najít cestu mezi dvěma vybranými vrcholy ve váženém grafu , která maximalizuje váhu nejméně vážené hrany grafu (pokud váhu hrany považujeme za šířku silnice, pak problém je vybrat nejširší cestu spojující dva vrcholy). Problém nejširší cesty je také známý jako problém úzkého hrdla nebo problém maximální kapacity . Algoritmy nejkratší cesty je možné přizpůsobit výpočtu propustnosti použitím nějaké speciální hodnoty místo délky cesty [1] . V mnoha případech jsou však možné rychlejší algoritmy.

Například v grafu, který představuje spojení mezi routery na internetu , kde váha hrany představuje šířku pásma spojení mezi dvěma routery, problém najít nejširší cestu odpovídá problému najít koncový bod. koncová cesta mezi dvěma internetovými uzly, která má největší možnou šířku pásma [2] [3 ] . Nejmenší tloušťka hrany na této cestě je známá jako kapacita nebo šířka cesty. Spolu s aplikacemi v síťovém směrování je problém nejširší cesty také důležitou součástí Schulzeho metody pro určení vítěze ve vícestranných volbách [4] , používá se v digitálním zarovnání obrazu [5] , analýze metabolických toků [6] a vypočítat maximální průtoky [7] .

Úzce související problém cesty minimax vyžaduje cestu, která minimalizuje maximální váhu kterékoli z hran (lze interpretovat jako nalezení nejhladší silnice s minimálními úhly do kopce a z kopce). Tento problém nachází uplatnění v dopravním plánování [8] . Libovolný algoritmus pro problém nejširší cesty může být převeden na algoritmus minimax cesty a naopak obrácením významu všech porovnání vah provedených v algoritmu, nebo ekvivalentně změnou vah na záporné hodnoty.

Neorientované grafy

V neorientovaném grafu lze nejširší cestu nalézt jako cestu mezi dvěma vrcholy v maximálním kostru grafu a cestu minimax lze nalézt jako cestu mezi dvěma vrcholy v minimálním kostru [9] [10] [11 ] .

V každém grafu, ať už orientovaném nebo ne, existuje jednoduchý algoritmus pro nalezení nejširší cesty, pokud je známa váha hrany s minimální hodnotou - jednoduše odstraňte všechny hrany s menší hodnotou a vyhledejte cestu mezi zbývajícími hranami pomocí šířky -první hledání nebo hloubka -první hledání . Existuje lineární časový algoritmus založený na tomto testu pro nalezení nejširší cesty s - t v neorientovaném grafu, který nepoužívá maximální kostru. Základní myšlenkou algoritmu je použít lineární časový algoritmus k nalezení cesty ke mediánu vah hran grafu a poté buď odstranit všechny menší hrany, nebo zmenšit všechny větší hrany podle toho, zda cesta existuje nebo ne, a výsledný menší pak rekurzivně zpracujte graf [10] [12] [13] .

Fernandez, Garfinkel a Arbiol [14] použili problém úzkých míst v neorientovaných grafech k získání digitálního aliasingu leteckého snímku , který kombinuje více snímků překrývajících se oblastí. V dílčím problému, na který se vztahuje problém s nejširší cestou, již byly dva obrázky převedeny do stejného souřadnicového systému . Zbývá pouze vybrat šev , křivku, která prochází přes přesah a odděluje jeden obrázek od druhého. Pixely na jedné straně švu jsou zkopírovány z jednoho obrázku a pixely na druhé straně švu jsou zkopírovány z jiného obrázku. Na rozdíl od jiných metod zarovnání snímků, ve kterých jsou pixely z obou snímků zprůměrovány, tato metoda pořizuje skutečný fotografický snímek každé části fotografované oblasti. V této metodě jsou okrajům mřížky přiřazeny váhy s hodnotami, které odhadují, jak moc se šev objeví vizuálně na okraji, a najdou nejširší cestu pro tyto váhy. Použití této cesty jako švu, spíše než tradičnější nejkratší cesty, vede k tomu, že jejich systém najde šev, který je těžko viditelný, místo aby zvyšoval kvalitu jedné části obrazu na úkor jiné [5] .

Řešení problému minimaxu mezi dvěma rohy mřížky může být použito k nalezení slabé Fréchetovy vzdálenosti mezi dvěma přerušovanými čarami . Zde každý vrchol mřížky představuje dvojici segmentů, jeden z každého řetězce, a váha hrany představuje Fréchetovu vzdálenost potřebnou k přechodu z jednoho páru segmentů do druhého [15] .

Pokud jsou všechny váhy hran neorientovaného grafu kladné , pak minimální maximální vzdálenosti mezi dvojicemi bodů (maximální váhy hran minimax cest) tvoří ultrametrický prostor . Naopak každý konečný ultrametrický prostor je tvořen z minimax vzdáleností tímto způsobem [16] . Datová struktura vytvořená ze stromu s nejmenším rozpětím umožňuje dotazování na minimální maximální vzdálenost mezi libovolným párem vrcholů v konstantním čase pomocí dotazů na nejméně společných předků v kartézském stromě . Kořen karteziánského stromu představuje nejtěžší hranu nejméně se rozpínajícího stromu a potomci kořene jsou kartézské stromy rekurzivně konstruované z podstromů nejméně se rozkládajících stromů vytvořených odstraněním nejtěžší hrany. Listy kartézského stromu představují vrcholy vstupního grafu a minimální maximální vzdálenost mezi dvěma vrcholy je rovna váze uzlu kartézského stromu, který je jejich nejmenším společným předkem. Jakmile jsou setříděny okraje stromu s nejmenším rozpětím, lze tento kartézský strom sestavit v lineárním čase [17] .

Orientované grafy

V orientovaných grafech nelze použít řešení maximálního spanning tree. Místo toho jsou známy některé různé algoritmy. Otázka, jaký algoritmus zvolit, závisí na tom, zda jsou počáteční a koncové vrcholy cesty pevné, nebo zda je nutné hledat cesty z několika počátečních a koncových vrcholů současně.

Všechny páry

Nejširší problém cesty pro všechny dvojice má aplikace v Schulzeho metodě pro určení vítěze ve vícecestných volbách , ve kterých voliči hodnotí kandidáty v preferenčním hlasování . Schulzeho metoda konstruuje úplný orientovaný graf , kde vrcholy představují kandidáty a libovolné dva vrcholy jsou spojeny hranou. Každá hrana směřuje od vítěze k poraženému v soubojích dvou kandidátů a je označena výhodou vítěze v soutěži. Metoda pak vypočítá nejširší cestu mezi všemi dvojicemi vrcholů a vítězem je kandidát, který má nejširší cesty s každým z protivníků [4] . Volební výsledky využívající tuto metodu jsou konzistentní s Condorcetovou metodou  - kandidát, který vyhraje všechny souboje, se automaticky stává vítězem voleb, ale metoda umožňuje zvolit vítěze, když Condorcetova metoda nefunguje [18] . Schulzeho metodu používá několik organizací, včetně Wikimedia Foundation [19] .

Pro výpočet nejširší cesty pro všechny páry uzlů v hustých orientovaných grafech, jako jsou aplikace pro hlasování, běží asymptoticky nejrychlejší přístup v čase , kde je metrika pro algoritmy rychlého násobení matic . Při použití nejznámějších algoritmů násobení matic se tyto časové limity promění v [20] . Rané algoritmy, které také používaly rychlé násobení matic k urychlení hledání nejširších cest pro všechny páry, viz Wassilewska, Williams a Yuster [21] a kapitola 5 Wassilewska [22] . Referenční implementace Schulzeovy metody využívá upravenou verzi jednoduššího Floyd-Warshallova algoritmu , který běží v čase [4] . U řídkých grafů lze efektivněji použít vícenásobné použití algoritmu pro vyhledávání nejširší cesty pro jeden zdroj.

Jeden zdroj

Pokud jsou hrany seřazeny podle jejich vah, pak upravená verze Dijkstrova algoritmu dokáže vypočítat úzká hrdla mezi přiřazeným počátečním vrcholem a všemi ostatními vrcholy v grafu v lineárním čase. Klíčovou myšlenkou zrychlení s obvyklou verzí Dijkstrova algoritmu je, že sekvence úzkých míst až ke každému vrcholu v pořadí, v jakém se tyto vrcholy objevují v algoritmu, je monotónní podsekvence seřazená podle vah sekvence hran. Proto může být prioritní fronta Dijkstrova algoritmu implementována jako kontejnerová fronta , pole očíslované od 1 do m (počet hran v grafu), kde buňka pole i obsahuje vrcholy, jejichž „úzká hrdla“ se rovnají váze. hrany s pozicí i v seřazeném pořadí. Tato metoda řeší problém nejširší cesty stejnou rychlostí jako řazení . Například, pokud jsou váhy hran celá čísla, pak bude odhadem pro tento problém také vázaný čas pro celočíselné třídění seznamu m celých čísel [13] .

Jediný zdroj a jeden cíl

Berman a Handler [23] navrhli, aby záchranná vozidla a sanitky při návratu z místa volání na základnu využívaly cestu minimax. V těchto případech je doba návratu méně důležitá než doba odezvy, pokud dojde k dalšímu volání, zatímco se stroj vrací. Při použití cesty minimax, ve které je hmotností maximální doba jízdy od okraje k nejvzdálenějšímu bodu možného hovoru, je možné naplánovat trasu tak, aby maximální možná prodleva mezi přijetím hovoru a příjezdem vozu je minimální [8] . Ulla, Lee a Hassoon [24] použili maximální cesty k modelování řetězce dominantních reakcí v metabolických sítích . V jejich modelu je hmotnost hrany volná energie metabolické reakce reprezentovaná hranou [6] .

Další aplikace nejširších cest vzniká ve Ford-Fulkersonově algoritmu pro problém maximálního průtoku . Postupně se zvyšující průtok podél cesty s maximální kapacitou v síti zbytkového průtoku vede k malému omezení počtu přírůstků potřebných k nalezení maximálního průtoku. Zde se předpokládá, že okrajové kapacity jsou celá čísla nepřesahující U. Tato analýza však nezávisí na nalezení přesné maximální kapacity. Vhodná je jakákoli cesta s kapacitou, která se od maxima liší konstantním faktorem. Kombinace těchto aproximačních myšlenek s metodou přírůstku nejkratší cesty algoritmu Edmonds-Karp vede k algoritmu maximálního toku s dobou běhu [7] .

Cesty maximální kapacity a cesty minimaxu s jedním zdrojem a jediným cílem je možné velmi efektivně najít i ve výpočetních modelech, které umožňují pouze porovnávání vah vstupních hran grafu, nikoli s nimi aritmetiku [13] [25] . Algoritmus pracuje se sadou S hran, o kterých je známo, že obsahují okraj úzkého hrdla optimální cesty. Zpočátku se S skládá ze všech m hran grafu. Při každé iteraci algoritmu se S rozdělí na uspořádanou sekvenci podmnožin přibližně stejné velikosti. Počet podmnožin v tomto oddílu je zvolen tak , aby bylo možné najít všechny body oddílu mezi podmnožinami nalezením mediánů vícekrát v čase O ( m ) . Algoritmus pak přepočítá váhy všech hran grafu podle indexu podmnožiny obsahující hranu a na graf s aktualizovanými vahami použije upravený Dijkstrův algoritmus. Na základě výsledků těchto výpočtů je možné lineárně vypočítat, která z podmnožin obsahuje váhu hrany úzkého místa. Algoritmus pak nahradí S podmnožinou Si , která obsahuje váhu úzkého hrdla, a zahájí novou iteraci s touto množinou S . Počet podmnožin, do kterých lze S rozdělit , se může s každým krokem exponenciálně zvyšovat, takže počet iterací je úměrný iterovanému logaritmu , a celková doba provádění bude [25] . Ve výpočtovém modelu, kde je váha každé hrany strojové celé číslo, lze použití iteračních logaritmů v tomto algoritmu nahradit technikou dělení seznamu podle Hahna a Thorupa [26] , která umožňuje rozdělit S na menší části s S i v jednom kroku, výsledkem je lineární společná hranice v čase [27] .

Množiny euklidovských bodů

Varianta problému minimax cesty byla zvažována pro soubor bodů na euklidovské rovině . Stejně jako v problému s neorientovaným grafem lze tento problém euklidovské cesty minimaxu efektivně vyřešit nalezením euklidovského minimálního kostry  — jakákoli cesta ve stromu je cesta minimaxu. Problém se však zkomplikuje, pokud chceme, aby cesta nejen minimalizovala horní délku, ale také mezi cestami se stejnou horní délkou minimalizovala nebo zhruba minimalizovala celkovou délku cesty. Řešení lze aproximovat pomocí geometrického kostry [28] .

V teorii čísel se nevyřešený problém Gaussova příkopu ptá, zda je minimax délka minimax cest v Gaussových prvočísel omezená . To znamená, existuje konstanta B taková, že pro jakýkoli pár p a q v nekonečné množině euklidovských bodů definovaných Gaussovými prvočísly má cesta minimaxu v Gaussových prvočíslech mezi p a q délku hrany nejvýše B ? [29] .

Poznámky

  1. ↑ Pollack, 1960 , s. 733–736.
  2. ↑ Shacham, 1992 , str. 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 , str. 293–304.
  6. ↑ 1 2 Ullah, Lee, Hassoun, 2009 , str. 144–150.
  7. ↑ 1 2 Ahuja, Magnanti a Orlin, 1993 , str. 210–212.
  8. ↑ 1 2 Berman, Handler, 1987 , s. 115–122.
  9. ↑ Hu, 1961 , str. 898–900.
  10. ↑ 12 Punnen , 1991 , s. 402–404.
  11. ↑ Malpani, Chen, 2002 , str. 175–180.
  12. ↑ Camerini, 1978 , s. 10–14.
  13. ↑ 1 2 3 Kaibel, Peinhardt, 2006 .
  14. ↑ Fernandez, Garfinkel, Arbiol, 1998 .
  15. ↑ Alt, Godau, 1995 , str. 75–91.
  16. ↑ Leclerc, 1981 , str. 5–37, 127.
  17. ↑ Demaine, Landau, Weimann, 2009 , s. 341–353.
  18. ↑ Přesněji, jediná možnost, kde Schulzeho metoda selže, je, když dva kandidáti mají cesty stejně široké.
  19. ↑ Viz Jesse Plamondon-Willard, Volba rady pro použití preferenčního hlasování , květen 2008; Mark Ryan, výsledky voleb do rady Wikimedia v roce 2008 , červen 2008; Volby do představenstva 2008 , červen 2008; a volby do představenstva 2009 , srpen 2009.
  20. ↑ Duan, Pettie, 2009 , str. 384–391.
  21. ↑ Vassilevska, Williams, Yuster, 2007 , str. 585–589.
  22. ↑ Vassilevska, 2008 .
  23. ↑ Berman, Handler, 1987 .
  24. ↑ Ullah, Lee, Hassoun, 2009 .
  25. ↑ 1 2 Gabow, Tarjan, 1988 , str. 411–417.
  26. ↑ Han, Thorup, 2002 .
  27. ↑ Han, Thorup, 2002 , str. 135–144.
  28. ↑ Bose, Maheshwari, Narasimhan, Smid, Zeh, 2004 , str. 233–249.
  29. ↑ Gethner, Wagon, Wick, 1998 , str. 327–337.

Literatura