Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
1. Príroda grafu:
* vážené vs. nevážené: Sú okraje vášho grafu spojené s nákladmi alebo vzdialenosťou (vážené), alebo sa považujú všetky hrany, ktoré majú rovnaké náklady (nevážené)?
* nasmerované vs. Sú okraje smerové (jednosmerné ulice) alebo obojsmerné (obojsmerné ulice)?
* cyklické vs. acyklické: Obsahuje graf cykly (cesty, ktoré môžu viesť späť do toho istého uzla)?
* hustota: Je graf riedky (relatívne málo hrán) alebo husté (mnoho hrán)?
* Negatívne hmotnosti: Sú všetky závažia okrajov nezáporné? To je * rozhodujúce * pre veľa algoritmov správne funguje. Ak máte negatívne váhy, je potrebné špeciálne zaobchádzanie.
* Euclidean vs. neeuklidian: Môžete použiť geometrické vlastnosti na odvodenie vzdialenosti medzi bodmi?
2. Cieľ algoritmu:
* Jednodulárne najkratšia cesta: Nájdenie najkratšej cesty z konkrétneho štartovacieho uzla do všetkých ostatných uzlov v grafe.
* najkratšia cesta: Nájdenie najkratšej cesty zo všetkých uzlov do konkrétneho cieľového uzla (koncepčne rovnaké ako jeden zdroj, ak obrátite smer hraní).
* All-Pairs najkratšia cesta: Nájdenie najkratšej cesty medzi * každým * dvojicou uzlov v grafe.
* heuristika povolená? Ak ste v poriadku s aproximáciou a nezaručujete * absolútnu * najkratšiu cestu, často môžete získať oveľa rýchlejšie výsledky s heuristickým vyhľadávaním.
Tu je rozpis bežných algoritmov a ich typických prípadov použitia:
pre nevážené grafy:
* Vyhľadávanie na prvom šírke (BFS): Toto je najrýchlejší * a najjednoduchší algoritmus pre nevážené grafy. Zaručuje nájdenie najkratšej cesty (z hľadiska * čísla * hrán) zo zdrojového uzla do všetkých ostatných dosiahnuteľných uzlov.
* Čas zložitosť: O (v + e), kde v je počet vrcholov a e je počet hrán.
pre vážené grafy s nezápornými váhami:
* Dijkstra's Algoritmus: Jeden z najčastejšie používaných algoritmov na nájdenie najkratšej cesty od jedného zdroja do všetkých ostatných uzlov vo váženom grafe s * negatívnymi * hrankovými hmotnosťami.
* Čas zložitosť:
* O (v^2) (s jednoduchou implementáciou poľa alebo zoznamu pre prioritné fronty)
* O (e + v log V) (pomocou binárnej haldy alebo frontu priority)
* O (e + v log* v) (pomocou haldy Fibonacci - v praxi menej bežné v dôsledku režijných nákladov)
* a* vyhľadávanie: Rozšírenie algoritmu Dijkstra, ktorý používa funkciu heuristickej * * na usmernenie vyhľadávania. Je to často výrazne rýchlejšie ako Dijkstra, keď máte dobré heuristické informácie o zostávajúcej vzdialenosti od cieľa.
* Čas zložitosť: Závisí to od heuristiky. V najlepšom prípade (perfektná heuristika) môže byť veľmi rýchla. V najhoršom prípade (zlá heuristika) môže byť rovnako pomalá ako Dijkstra.
* a* vyžaduje heuristiku, ktorá je prípustná (nikdy nepreceňuje náklady na dosiahnutie cieľa) a konzistentné (monotonické).
pre vážené grafy s negatívnymi hmotnosťami (a bez záporných cyklov):
* Algoritmus Bellman-Ford: Dokáže spracovať grafy s zápornou hmotnosťou okrajov, pokiaľ neexistujú žiadne negatívne cykly (cykly, kde je súčet okrajových hmotností negatívny). Ak existuje negatívny cyklus, dokáže ho zistiť.
* Čas zložitosť: O (v * e)
Pre najkratšie cesty pre všetky páry:
* algoritmus floyd-warshall: Nájde najkratšiu cestu medzi * každým * dvojicou vrcholov v smerovanom alebo neistotelom grafe. Dokáže tiež zvládnuť záporné hmotnosti okrajov (ale nie negatívne cykly).
* Čas zložitosť: O (v^3)
* Johnsonov algoritmus: Môže tiež nájsť najkratšie chodníky na všetky koláče a dokáže zvládnuť záporné hmotnosti okrajov. Všeobecne je rýchlejší ako Floyd-Warshall na * riedky * grafy. Funguje to tým, že preváži hrany, aby sa eliminovala negatívne hmotnosti (pomocou Bellman-Ford) a potom spustenie algoritmu Dijkstra z každého vrcholu.
* Čas zložitosť: O (v^2 log V + ve)
súhrnná tabuľka
| Algoritmus Typ grafu Váhy okrajov Časová zložitosť Poznámky |
| ------------------ | ------------------------------------------------- | ------------ | ---------------------------- | ------------------------------------------------------------------------- |
| BFS | Nevážené Žiadne | O (v + e) | Najrýchlejšie pre nevážené grafy. |
| Dijkstra Vážené, negatívne Nezávratové | O (E + V Log V) | Bežné, funguje dobre s prioritným frontom. |
| A* | Vážené, negatívne Nezávratové | Heuristická závislá Môže byť oveľa rýchlejšia ako Dijkstra, ak existuje dobrá heuristika. |
| Bellman-Ford | Vážené, môžu mať negatívne hrany Akékoľvek | O (v * e) | Dokáže detekovať negatívne cykly. |
| Floyd-Warshall | Vážené, môžu mať negatívne hrany (bez cyklov) Akékoľvek | O (v^3) | Najkratšie cesty, dobré pre husté grafy. |
| Johnson's | Vážené, môžu mať negatívne hrany (bez cyklov) Akékoľvek | O (v^2 log v + ve) | Najkratšie cesty All-Cairs, lepšie ako Floyd-Warshall pre riedke grafy |
Praktické úvahy a optimalizácie:
* Dátové štruktúry: Výber dátovej štruktúry pre front priority v algoritme Dijkstra (napr. Binárna halda, fibonacci halda) môže významne ovplyvniť výkon, najmä pri veľkých grafoch.
* heuristika pre a*: Výber dobrej heuristiky pre* je rozhodujúci. Dobre zvolená heuristika môže vyhľadávanie dramaticky urýchliť. Bežná heuristika zahŕňa euklidovskú vzdialenosť (pre grafy zabudované do lietadla) a vzdialenosť na Manhattane.
* Reprezentácia grafu: Spôsob, akým reprezentujete svoj graf (napr. Zoznam susedných síl, matica susediace), môže tiež ovplyvniť výkon. Zoznamy susedstva sú vo všeobecnosti uprednostňované pre riedke grafy, zatiaľ čo matice susedstva môžu byť efektívnejšie pre husté grafy.
* predbežné spracovanie: Pre grafy, ktoré sa opakujú opakovane, môžete predkompultovať určité informácie (napr. O orientačných bodoch, najkratších stromoch cesty), aby ste zrýchlili následné otázky.
* Sieť v reálnom svete: V prípade cestných sietí ponúkajú špecializované algoritmy, ako sú kontrakčné hierarchie (CH) a prispôsobiteľné plánovanie trasy (CRP) * oveľa rýchlejšie časy dotazu ako generické algoritmy, ako sú Dijkstra, ale vyžadujú si významné spracovanie. Tieto sa často používajú v navigačných systémoch GPS.
* Knižnice: Používajte optimalizované knižnice (napr. Networkx v Pythone, Jgrapht v Java), kedykoľvek je to možné. Tieto knižnice často poskytujú vysoko optimalizované implementácie najkratších algoritmov cesty.
V súhrne určiť „najrýchlejší“ algoritmus pre vašu situáciu:
1. charakterizujte svoj graf: Je to vážené, nevážené, nasmerované, riedke, husté atď.?
2. Potrebujete jednotlivé alebo koláče najkratšie cesty?
3. sú prítomné záporné hranené hmotnosti? Ak áno, ste obmedzení na Bellman-Ford (single Source) alebo Johnson's/Floyd-Warshall (All-Pairs).
4. Ak nezáporné váhy, zvážte Dijkstra alebo A*. Ak*, môžete navrhnúť dobrú heuristiku?
5. Pre nevážené grafy je BFS takmer vždy najlepšou voľbou.
6. Profil a referenčné číslo: Experimentujte s rôznymi algoritmami a dátovými štruktúrami, aby ste zistili, ktoré najlepšie fungujú na vašom konkrétnom súbore údajov a hardvéri.
Vyberte najjednoduchší algoritmus, ktorý vyhovuje vašim potrebám. Nepoužívajte Floyd-Warshall, ak potrebujete iba najkratšie cesty s jedným zdrojom.