Zadanie skúšky z 29.5.2019

Taxikár

Jediný taxikár v Kocúrkove nejazdí podľa žiadneho plánu a dokonca ignoruje aj správy dopravného servisu, ktorý raz začas hlási ulice, ktoré sú zapchaté zhustenou premávkou. Majiteľ taxislužby sa rozhodol zabudovať do taxíka softvér, ktorý bude taxikárovi radiť optimálnu trasu, ktorá dovedie zákazníka do cieľa za najkratší čas. Keďže nemáme k dispozícii žiadnu mapu mestečka, budeme si musieť vystačiť s históriou jázd taxikára (predpokladáme, že jazdil skoro po všetkých uliciach mesta) a so zaznamenanými správami dopravného servisu.

Sieť ulíc v Kocúrkove je organizovaná tak, že každá križovatka má svoj kód (znakový reťazec) a každá ulica je obojsmerná a spája nejaké dve križovatky. Pre jednoduchosť predpokladáme, že taxikár prejde po jednej ulici (medzi dvoma križovatkami) buď za jednu minútu (ak nie je zápcha) alebo za nejaký násobok minút (podľa informácií dopravného servisu). Tiež budeme predpokladať, že taxikár vozí zákazníkov vždy od nejakej križovatky po nejakú druhú.

Informácie o doterajších jazdách taxikára a niektorých správach dopravného servisu máme dané v textovom súbore:

  • každý riadok obsahuje buď jednu jazdu taxikára alebo jednu informáciu o dopravných obmedzeniach;

  • jazda taxikára je popísaná ako postupnosť prejdených križovatiek (znakové reťazce str) spojené znakom '-';

  • dopravné obmedzenia sú popísané dvojicou križovatiek (spojené znakom '-') a celým číslom za znakom ':', ktoré označuje počet minút pozdržania na tejto ulici; ak je toto číslo 0, označuje to, že ulica je neprejazdná;

  • môžete predpokladať, že súbor je zadaný korektne.

Napr. súbor:

1-2-3-5-7
8-5-4-1
5-8:4
9-8-7-5-8-9-6
3-5:2
4-5-3-6

označuje 4 rôzne jazdy, ktoré postupne popisujú plánik Kocúrkova. Medzitým prišli dve správy dopravného servisu, ktoré dvom uliciam nastavili nejaké časové obmedzenia. Menami križovatiek sú v tomto prípade reťazce s číslami od '1' do '9'. Pre lepšiu predstavu o pláne tohto mesta si môžete nakresliť graf s 3x3 vrcholmi (križovatkami), ktoré postupne (zľava doprava, zhora nadol) očíslujete od 1 do 9.

Z pohľadu dátovej štruktúry graf:

  • križovatky sú vrcholy grafu;

  • ulice sú hrany grafu, pričom ohodnotením (váhou) je časové pozdržanie (1 pre normálny prejazd bez pozdržania, väčšie číslo pre dopravnú zápchu);

  • graf je neorientovaný a preto je každá hrana definovaná pre oba smery (zrejme aj s váhou hrany).

Riešenie zapíšte do triedy Graf s týmito metódami:

class Graf:
    def __init__(self, meno_suboru):
        ...

    def vrcholy(self):
        return set()

    def hrana(self, v1, v2):
        return None

    def nastav(self, v1, v2, h):
        ...

    def cesty(self, v1, v2):
        return []

Kde metódy:

  • __init__(meno_suboru): prečíta súbor a vytvorí z neho reprezentáciu neorientovaného ohodnoteného grafu

  • hrana(v1, v2): vráti hodnotu hrany: buď je to celé číslo (väčšie ako 0), alebo None, ak neexistuje hrana medzi týmito dvoma vrcholmi

  • vrcholy(): vráti množinu názvov všetkých vrcholov (križovatiek)

  • nastav(v1, v2, h): nastaví novú hodnotu hrany (h je celé číslo), pričom, ak je h=0, túto hranu zruší

  • cesty(v1, v2): pomocou backtrackingu nájde všetky najrýchlejšie cesty z vrcholu v1 do vrcholu v2; metóda vráti buď prázdny zoznam (nenašiel žiadne riešenie), alebo zoznam (typ list), ktorý obsahuje všetky najrýchlejšie cesty; cesta je postupnosť (opäť list) mien vrcholov (zrejme všetky tieto cesty majú rovnaký čas prejazdu, ale môžu obsahovať rôzny počet vrcholov)

    • uvedomte si, že počas behu backtrackingu nemá zmysel pokračovať vo vytváraní cesty, ktorá má už horší čas, ako doteraz najrýchlejšia

Môžete si dodefinovať aj ďalšie pomocné metódy. Ak chcete definovať nejaké ďalšie pomocné triedy, zapíšte ich ako vnorené do triedy Graf.

Program môžete testovať napr. takto:

if __name__ == '__main__':
    g = Graf('subor1.txt')
    print('vrcholy =', g.vrcholy())
    for v1, v2 in ('6', '9'), ('5', '3'), ('2', '7'):
        print(f'hrana({v1!r}, {v2!r}) = {g.hrana(v1, v2)!r}')
    print(g.cesty('4', '9'))
    g.nastav('6', '5', 3)
    g.nastav('7', '5', 2)
    print(g.cesty('4', '9'))
    g.nastav('5', '4', 0)
    print(g.cesty('4', '9'))
    g.nastav('6', '9', 0)
    print(g.cesty('4', '9'))
    print(g.cesty('4', '10'))

a pre vyššie uvedený textový súbor by mal vypísať (možno s pozmeneným poradím):

vrcholy = {'9', '2', '6', '1', '7', '4', '5', '8', '3'}
hrana('6', '9') = 1
hrana('5', '3') = 2
hrana('2', '7') = None
[['4', '5', '7', '8', '9']]
[['4', '1', '2', '3', '6', '9'], ['4', '5', '7', '8', '9'],
 ['4', '5', '3', '6', '9'], ['4', '5', '6', '9']]
[['4', '1', '2', '3', '6', '9']]
[['4', '1', '2', '3', '5', '7', '8', '9']]
[]

Z úlohového servera L.I.S.T. si stiahnite kostru programu skuska.py. Pozrite si testovacie dáta v súboroch 'subor1.txt', 'subor2.txt', 'subor3.txt', …, ktoré bude používať testovač. Aby ste mohli spúšťať skúškové testy, program uložte do súboru skuska.py. Riešenie (bez dátových súborov) odovzdajte na úlohový server https://list.fmph.uniba.sk/. Celkovo môžete získať 60 bodov:

  • 30% je za vytvorenie grafu zo súboru, t.j. správne fungovanie metód vrcholy()hrana()nastav()

  • 30% je za nájdenie aspoň jednej najrýchlejšej cesty zo štartu do cieľa

  • 30% za nájdenie všetkých najrýchlejších ciest

  • 10% za správny výsledok takých zadaní, pre ktoré neexistuje ani jedna cesta

Praktická časť končí o 11:00 a skúška pokračuje od 12:00 vyhodnotením v kancelárii m162.