Zadanie skúšky z 12.6.2020


V Kocúrkove kúpili do mestského parku parkového robota: ten je schopný prejsť po chodníkoch parku a riadne ich pozametať. Lenže výrobcovia tohto robota ho naprogramovali tak, že automaticky sa vypne, ak by mal v jednom dni prejsť druhýkrát po tom istom chodníku (hoci aj opačným smerom). Kvôli tejto komplikácii museli veľmi starostlivo pripraviť trasu pre parkového robota, aby sa nevypol predčasne a pritom pozametal čo nadlhšiu trasu chodníkov parku.

V reči grafov riešime takýto problém: daný je neorientovaný súvislý ohodnotený graf. Pre daný štartový vrchol treba nájsť čo najdlhšiu trasu, ktorá vychádza z tohto vrcholu a cez žiadnu hranu neprechádza viackrát. Dĺžkou trasy rozumieme súčet ohodnotení hrán a nie počet vrcholov, cez ktoré prechádza. Ideálne by bolo nájsť trasu, ktorá prejde cez všetky hrany. Hodnotou hrany je dĺžka úsečky (určenej koncovými bodmi), teda je to vzdialenosť dvoch bodov v rovine.

Celý park (teda samotný graf) je popísaný v textovom súbore takto:

  • každý riadok popisuje jeden chodník (hranu) ako štvoricu celých čísel;

  • každý vrchol, teda koncová súradnica hrany je dvojica celých čísel, preto je chodnik definovaný ako štvorica celých čísel x1, y1, x2, y2.

Napríklad súbor:

238 296 221 419
202 75 238 296
238 296 111 273
193 352 107 421
193 352 238 296
111 273 202 75
221 419 107 421
193 352 221 419
111 273 193 352
107 421 111 273

popisuje graf s 10 hranami, ktoré spájajú 6 vrcholov. Rozloženie vrcholov a hrán s danými súradnicami si môžeš nakresliť do grafickej plochy (to nebude súčasť riešenia úlohy). Uvedom si, že graf je neorientovaný a preto každá hrana definuje oba smery.

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

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

    def start(self, v):
        return [], 0

    def vrcholy(self):
        return set()

    def je_hrana(self, v1, v2):
        return False

kde metódy:

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

  • je_hrana(v1, v2): vráti True, ak existuje hrana medzi týmito vrcholmi, inak vráti False; v1 a v2 sú súradnice dvoch bodov v rovine, teda sú to dvojice celých čísel;

  • vrcholy(): vráti množinu vrcholov (koncových vrcholov chodníkov), teda množinu dvojíc celých čísel;

  • start(v): pomocou backtrackingu nájde najdlhšiu trasu z vrcholu v (kde v je dvojica celých čísel); metóda vráti dvojicu: zoznam vrcholov trasy (list dvojíc celých čísel) a dĺžku trasy (súčet dĺžok hrán); ak žiadna trasa neexistuje, metóda vráti dvojicu [], 0.

Uvedom si, že počas behu backtrackingu nemá zmysel pokračovať vo vytváraní trasy, ak sa už našla trasa, ktorá prechádza cez všetky hrany (tzv. eulerovský ťah). Pre graf s väčším počtom hrán to môže výrazne vylepšiť čas behu riešenia.

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

Program môžeš testovať, napríklad takto:

if __name__ == '__main__':
    p = Park('subor1.txt')
    print('vrcholy =', p.vrcholy())
    for v1 in (107, 421), (193, 352), (202, 75):
        for v2 in (238, 296), (193, 352), (221, 420):
            print(f'je_hrana({v1}, {v2}) =', p.je_hrana(v1, v2))
    for v in (238, 296), (193, 352), (221, 420):
        print(f'start({v}) =', p.start(v))

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

vrcholy = {(107, 421), (193, 352), (238, 296), (111, 273), (202, 75), (221, 419)}
je_hrana((107, 421), (238, 296)) = False
je_hrana((107, 421), (193, 352)) = True
je_hrana((107, 421), (221, 420)) = False
je_hrana((193, 352), (238, 296)) = True
je_hrana((193, 352), (193, 352)) = False
je_hrana((193, 352), (221, 420)) = False
je_hrana((202, 75), (238, 296)) = True
je_hrana((202, 75), (193, 352)) = False
je_hrana((202, 75), (221, 420)) = False
start((238, 296)) = ([(238, 296), (193, 352), (221, 419), (238, 296), (202, 75),
(111, 273), (193, 352), (107, 421), (111, 273), (238, 296)], 1211.690885781633)
start((193, 352)) = ([(193, 352), (107, 421), (111, 273), (193, 352), (238, 296),
(202, 75), (111, 273), (238, 296), (221, 419), (107, 421)], 1253.0930029330182)
start((221, 420)) = ([], 0)

Desatinné čísla, ktoré vyjadrujú dĺžku trasy môžeš zaokrúhliť na 1 desatinné miesto.

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

Praktická časť končí o 16:30.