7. Osobná doprava vzorové riešenie

7
skladka smetisko 350
kontajner smetisko 299
dub javor 123
javor breza 234
dub breza 45678
breza lipa 1000
topol breza 50010
6
15 600 47 3 skladka smetisko kontajner
23 10 0 3 dub breza javor
1 1234 5 4 dub javor breza lipa
4 350 35 3 dub javor breza
100 1 0 2 javor dub
10 50 0 3 topol breza lipa
3
skladka kontajner
kontajner skladka
dub lipa

0d 0h 1m 31s
neda sa
0d 0h 4m 11s

Našou úlohou bolo zistiť, či sa dá zo zastávky A dostať na zastávku B, a ak áno, ako najrýchlejšie to vieme spraviť. Toto je zjavne úloha grafová a zrejme bude nejak súvisieť s najkratšími cestami. Ale ako presne?

Základné pozorovanie, ktoré nám pomôže úlohu vyriešiť, je nasledovné: Predstavme si, že sme objavili dva rôzne spôsoby, ako sa zo zastávky A dá dostať na nejakú zastávku C. Prvý z nich tam príde v čase \(t_1\), druhý v čase \(t_2\) a platí \(t_1<t_2\). Pri hľadaní optimálneho presunu z A do B nám stačí zapamätať si len jeden z týchto dvoch spôsobov – ten prvý. Totiž každý spôsob, akým vieme pokračovať zo zastávky C ďalej v druhom spôsobe máme k dispozícii aj pri prvom spôsobe príchodu, a možno máme ešte aj nejaké iné možnosti navyše, ktoré by sme pri príchode v čase \(t_2\) nestihli.

Myšlienka všetkých nižšie popísaných algoritmov bude teda veľmi jednoduchá: V priebehu nášho algoritmu sa budeme snažiť zostrojiť množinu všetkých zastávok, ktoré sú dosiahnuteľné zo zastávky A. Pre každú takú zastávku si navyše vypočítame aj najskorší čas, v ktorom môžeme na danej zastávke byť.

 Predspracovanie vstupu

Už vieme, že vrcholmi nášho grafu budú jednotlivé zastávky. Na vstupe však namiesto hrán máme zadanú množinu spojení, ktoré našimi zastávkami prechádzajú. Priamo pri načítavaní vstupu však vieme každé spojenie prekonvertovať na sadu hrán – ako keby sme ho nahradili viacerými linkami, z ktorých každá premáva len z jednej zastávky spojenia na druhú, bezprostredne nasledujúcu. Všetky hrany pochádzajúce z toho istého spojenia budú mať tú istú periódu. Ich offsety vypočítame jednoducho tak, že simulujeme jednu jazdu dotyčného spojenia a zapisujeme si, kedy sme navštívili ktorú zastávku.

Pre algoritmus Bellmana a Forda (prvé z riešení uvedených nižšie) by nám stačilo uložiť si všetky hrany grafu v jednom dlhočiznom zozname. Pre Dijkstrov algoritmus (druhé, lepšie riešenie) však budeme potrebovať hrany roztriediť: v každom vrchole grafu si budeme pamätať zoznam hrán, ktoré vedú z neho von. Takéto predspracovanie uvádzame aj v nasledovnom listingu.

from collections import defaultdict
from queue import PriorityQueue

def nacitaj_vzdialenosti():
    vzdialenost = {}
    d = int( input() )
    for riadok in range(d):
        x, y, dist = input().split()
        vzdialenost[ (x,y) ] = vzdialenost[ (y,x) ] = int(dist)
    return vzdialenost

class Segment:
    def __init__(self,kam,offset,perioda,cas):
        self.kam     = kam
        self.offset  = offset
        self.perioda = perioda
        self.cas     = cas

def nacitaj_linky(vzdialenost):
    graf = defaultdict(list)

    s = int( input() )
    for riadok in range(s):
        tokeny = input().split()
        v, p, o, z = [ int(x) for x in tokeny[:4] ]
        zastavky = tokeny[4:]
        for i in range(z-1):
            dist = vzdialenost[ (zastavky[i],zastavky[i+1]) ]
            time = (dist + v - 1) // v
            graf[ zastavky[i] ].append( Segment( zastavky[i+1], o, p, time ) )
            o = (o+time) % p
    return graf

V ďalšom texte budeme počet zastávok označovať \(n\) a celkový počet hrán v našom grafe (teda súčet počtov úsekov jednotlivých spojení) budeme označovať \(m\).

 Algoritmus Bellmana a Forda

Tento algoritmus je veľmi jednoduchý. Na začiatku vieme, že na zastávke A vieme byť v čase 0, a na žiadnej inej zastávke ešte nevieme byť. Toto si zapamätáme tak, že si pre ostatné zastávky zapíšeme, že tam vieme byť v čase “nekonečno”, pričom ako nekonečno použijeme nejakú dostatočne veľkú hodnotu.

Teraz ideme tieto hodnoty postupne zlepšovať. Zlepšovanie bude prebiehať v kolách. V každom kole sa postupne (je jedno, v akom poradí) raz pozrieme na každú hranu. Predstavme si, že sa práve pozeráme na hranu zo zastávky C na zastávku D. Momentálne sa vieme na zastávku C dostať v čase \(t_c\) a na zastávku D v čase \(t_d\). Pomôže nám hrana, ktorú práve skúmame, niečo zlepšiť? Jediné, v čom nám môže táto hrana pomôcť, je, že sa pomocou nej možno vieme skôr dostať na zastávku D. Zoberime teda čas \(t_c\), počkáme na zastávke C na najbližší spoj idúci práve skúmanou hranou a zistíme, kedy tento spoj dorazí na zastávku D. Ak sme práve dostali hodnotu menšiu ako \(t_d\), zmenšíme \(t_d\) na práve vypočítanú hodnotu – práve sme objavili lepší spôsob ako docestovať z A na D.

V programe spracovanie jednej hrany vyzerá nasledovne:

def cestuj(odkial,kedy,hrana):
    # sme na zastavke "odkial" v case "kedy"
    # chceme ist hranou "hrana" do jej cielovej zastavky
    # kedy najskor tam vieme byt?

    # pockame na najblizsi spoj iduci po linke "hrana"
    if startt % hrana.perioda != hrana.offset:
        cakaj = hrana.offset - (startt % hrana.perioda)
        if cakaj < 0: cakaj += hrana.perioda
    else:
        cakaj = 0

    # odvezieme sa linkou a vysledok vratime
    return kedy + cakaj + hrana.cas

Keď už v nejakom kole nenastanú vôbec žiadne zmeny, celý proces končí. Tvrdíme, že časy, ktoré sme vypočítali, sú najlepšími možnými časmi. Teda ak si pre nejakú zastávku ešte stále pamätáme hodnotu nekonečno, nedá sa na ňu vôbec dostať, a v opačnom prípade čas, ktorý sme vypočítali, je najlepší možný.

Teraz potrebujeme spraviť dve veci: dokázať, že vyššie uvedené tvrdenie platí, a zistiť, akú má tento algoritmus časovú zložitosť.

Všimnime si ľubovoľnú zastávku X, na ktorú sa dá zo zastávky A dostať. Nech je optimálna cesta z A na X tvorená \(k\) hranami a postupne prechádza zastávkami \(X_1\) až \(X_{k-1}\). Čo sa deje v našom algoritme? V prvom kole sa postupne pozeráme na všetky hrany, teda aj na hranu z A do  \(X_1\). Po prvom kole sa teda už určite vieme dostať do \(X_1\) v potrebnom čase. V druhom kole sa opäť postupne pozeráme na všetky hrany, a medzi nimi aj na hranu z \(X_1\) do \(X_2\). Po druhom kole sa teda už vieme v potrebnom čase dostať aj z A do \(X_2\). A postupne ďalej – po \(k\)-tom kole už musí byť vypočítaný čas pre zastávku X rovný optimálnemu.

Náš algoritmus je teda korektný. Navyše si uvedomme, že pre ľubovoľnú zastávku existuje optimálna cesta, pre ktorú platí \(k<n\). To je jednoduché – nikdy sa neoplatí vracať na zastávku, na ktorej sme už boli, takže existuje optimálna cesta, na ktorej sa zastávky neopakujú. Algoritmu teda bude stačiť nanajvýš \(n-1\) kôl. A keďže v každom kole sa pozeráme na \(m\) hrán, je časová zložitosť tohto algoritmu \(O(nm)\).

Implementácia spracovania jednej otázky:

def spracuj_otazku(graf,odkial,kam):

    # pre zastavku kde zaciname je vzdialenost 0
    # pre vsetky ostatne zastavky je to 2 na 60 == nekonecno
    najskorsi_prichod = defaultdict(lambda:2**60)
    najskorsi_prichod[odkial] = 0
   
    zmena = True
    while zmena:
        # zacina nove kolo, postupne sa pozerame na vsetky hrany
        zmena = False
        for odkial in graf:
            for seg in graf[odkial]:
                # zistime, ci hranou "seg" vieme nieco zlepsit

                if najskorsi_prichod[ odkial ] == 2**60: continue

                cas_v_cieli = cestuj( odkial, najskorsi_prichod[odkial], seg )
                if cas_v_cieli < najskorsi_prichod[ seg.kam ]:
                    najskorsi_prichod[ seg.kam ] = cas_v_cieli
                    zmena = True
    
    # a na zaver uz len vypiseme spravnu odpoved 

    if najskorsi_prichod[kam] == 2**60:
        print('neda sa')
    else:
        s = najskorsi_prichod[kam]
        d = s // 86400
        s %= 86400
        h = s // 3600
        s %= 3600
        m = s // 60
        s %= 60
        print('{}d {}h {}m {}s'.format(d,h,m,s))

 Dijkstrov algoritmus

Dijkstrov algoritmus počíta presne tie isté hodnoty ako algoritmus Bellmana a Forda, robí to ale šikovnejším spôsobom, a teda dosiahneme lepšiu časovú zložitosť. Existuje viacero rôznych implementácií Dijkstrovho algoritmu. Tá, ktorú si ukážeme my, bude mať časovú zložitosť \(O(m\log n)\).

Zlepšenie dosiahneme nasledovne: Namiesto toho, aby sme znova a znova prechádzali celý zoznam hrán, budeme každú hranu spracúvať len raz, “v správnej chvíli”. Takisto práve raz budeme spracúvať každú zastávku. Zastávky budeme spracúvať usporiadané podľa optimálneho času, kedy sa na ne vieme dostať. Tieto časy síce na začiatku nepoznáme, ale postupne ich budeme zisťovať a vždy budeme vedieť, ktorú zastávku spracovať ako nasledujúcu v poradí.

Na začiatku zjavne spracujeme zastávku A: pozrieme sa na všetky hrany vedúce z nej a tak zistíme nové spôsoby ako sa dostať na nejaké ďalšie zastávky. Zastávku A si následne označíme ako spracovanú.

Ako bude vo všeobecnosti vyzerať kolo tohto algoritmu? Nejaké zastávky sme už spracovali, tie nás už nezaujímajú. Ak sa už na žiadnu ďalšiu zastávku nevieme dostať, algoritmus končí. Inak sa pozrime na tie, ktoré ešte spracované nie sú, a vyberme spomedzi nich zastávku X, na ktorú sa momentálne vieme dostať (spomedzi všetkých nespracovaných) najskôr. Túto zastávku spracujeme ako nasledujúcu v poradí.

Prečo tento algoritmus funguje? Preto, že v okamihu, keď zastávku spracúvame, tak platí, že čas, ktorý sme pre ňu vypočítali, je už optimálny.

(Formálne by sme napríklad matematickou indukciou dokázali, že platí nasledovné tvrdenie: keď sme už spracovali prvých \(k\) zastávok, tak pre každú nespracovanú zastávku máme nájdený najlepší čas takej cesty na ňu, počas ktorej môžeme prestupovať len na už spracovaných zastávkach. No a následne si už len stačí všimnúť, že pre nami vybranú zastávku X už nemôže existovať ani rýchlejšia cesta, pri ktorej by sme prestupovali aj na nejakých nespracovaných zastávkach.)

Ako to celé dobre implementovať? Kľúčová operácia, ktorú potrebujeme robiť efektívne, je nájdenie zastávky X, ktorú ideme spracovať ako ďalšiu v poradí. Aby sme toto vedeli robiť rýchlo, budeme si zatiaľ nespracované zastávky udržiavať usporiadané podľa doteraz najlepšej vzdialenosti do nich.

V C++ by sme napríklad mohli ako dátovú štruktúru použiť set< pair<int,int> > Q, v ktorom by sme mali záznamy tvaru \((t,z)\) s významom “najlepší známy čas, v ktorom už vieme byť na zastávke \(z\), je \(t\)”. Nájsť nasledovnú zastávku na spracovanie vieme v čase \(O(\log n)\) tak, že sa pozrieme na Q.begin() (teda zastávku s najmenšou vzdialenosťou). Všetky výbery dokopy počas celého algoritmu nám teda budú trvať len \(O(n\log n)\).

Spracovať konkrétnu zastávku vieme v čase \(O(d\log n)\), kde \(d\) je počet hrán vedúcich z nej. Pre každú hranu skúsime zlepšiť čas pre zastávku, kam vedie. A ak sa nám to podarí, tak z Q zmažeme starý záznam pre dotyčnú zastávku a nahradíme ho novým s menšou vzdialenosťou. No a keďže každú zastávku spracujeme počas behu algoritmu najviac raz, nasčítajú sa nám časy ich spracovania na sľubovaných \(O(m\log n)\).

V našej implementácii sme použili trochu lenivejší prístup. Ako dátovú štruktúru použijeme obyčajnú prioritnú frontu (implementovanú ako haldu). Z nej síce nevieme priebežne vymazávať, ale to nám vôbec vadiť nebude – jednoducho to nebudeme robiť a keď zlepšíme čas pre nejakú zastávku, do prioritnej fronty pridáme nový záznam s novým lepším časom. A potom len pri výbere ďalšej zastávky na spracovanie dáme pozor, či nejde o zastávku, ktorú sme už skôr spracovali. Takéto záznamy jednoducho preskočíme (a teda ich vlastne až vtedy zmažeme).

V najhoršom prípade bude naša prioritná fronta obsahovať až \(O(m)\) záznamov naraz. (Totiž každú hranu v grafe spracúvame najviac raz a každé také spracovanie nám pridá najviac jeden záznam.) Všetky operácie s prioritnou frontou budú teda v čase \(O(\log m)\) a teda výsledná časová zložitosť našej implementácie bude \(O(m\log m)\).

def spracuj_otazku(graf,odkial,kam):

    najskorsi_prichod = defaultdict(lambda:2**60) # ak este nepriradil hodnotu, je to 2^60
    najskorsi_prichod[odkial] = 0

    Q = PriorityQueue()
    Q.put( (0,odkial) )
    while not Q.empty():
        kedy, kde = Q.get()
        if najskorsi_prichod[kde] < kedy: continue # uz sme ho spracovali
        for seg in graf[kde]:
            cas_v_cieli = cestuj( kde, kedy, seg )
            if cas_v_cieli < najskorsi_prichod[ seg.kam ]:
                najskorsi_prichod[ seg.kam ] = cas_v_cieli
                Q.put( (cas_v_cieli, seg.kam) )
   
    # vypis riesenia je rovnaky ako v algoritme Bellmana a Forda