Индийский ученый разработал алгоритм для точного расчета кратчайших путей в больших сетях

Nacházení optimálních cest a počítání vzdáleností mezi body je běžným informatickým problémem. Jedna z jeho modifikací se zaměřuje na stanovení vzdáleností mezi všemi dvojicemi bodů (vrcholů v grafu) v rozsáhlém systému. Problém se označuje jako APSP (all-pairs shortest paths). Složitost výpočtu všech vzdáleností je kubická (pokud se velikost sítě zdvojnásobí, doba výpočtu se zvýší asi osmkrát), což sice není obávaná exponenciální závislost, ale i tento polynom znamená pro velmi velké grafy potíž. Proto se výzkumníci již desítky let snaží najít rychlejší aproximační algoritmy: metody, které poskytují odhady vzdáleností co nejblíže skutečných hodnot, přičemž jejich výpočet zabere mnohem méně času. Již v roce 1996 Dor, Halperin a Zwick (DHZ) ukázali, že je možné rychle získat odhady vzdáleností, které nejsou horší než dvojnásobek skutečné hodnoty (ovšem – viz dále). Pokud je skutečná vzdálenost 10 kilometrů, metoda zaručuje výsledek mezi 10 a 20. Aby to bylo efektivní, algoritmus pracuje s malou podmnožinou vrcholů vybraných ze sítě (vzorkované vrcholy, sampled vertices). Místo prozkoumávání všech možných tras mezi dvěma vrcholy se algoritmus při efektivním odhadu vzdáleností spoléhá na vzorkované vrcholy. Problém je ovšem v tom, že algoritmus DHZ funguje pouze pro větší vzdálenosti – tj. cca když poblíž nejkratší cesty mezi dvěma body leží nějaký vzorkovaný vrchol. U krátkých úseků naproti tomu neexistovala záruka, že DHZ nevrátí odhad delší než dvojnásobek nejkratší cesty. Vylepšení tohoto výpočtu pro bližší vrcholy rozsáhlých sítí nyní představil Manoj Gupta z Indického technologického institutu v Gandhinagaru. Nový algoritmus má stejnou výpočetní složitost jako DHZ, ale vrcholky v grafu se mohou nacházet i blíže sobě. Změněn byl totiž postup vzorkování vrcholů. Místo toho, aby se algoritmus spoléhal na jedinou vrstvu vzorkovaných vrcholů, organizuje je v různých měřítkách, takže i kratší cesty jsou pravděpodobně „zachyceny“ přesněji („budou pro ně nějaké body“). To umožňuje algoritmu zachovat alespoň stejnou časovou složitost a zároveň snížit prahovou hodnotu minimální vzdálenosti, pro kterou platí „záruka (maximálně) dvojnásobku“. Manoj Gupta, Improved 2-Approximate Shortest Paths for close vertex pairs, 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) (2025). DOI: 10.1109/focs63196.2025.00065 Zdroj: Indian Institute of Technology Gandhinagar / TechXplore.com, přeloženo / zkráceno