Zadanie skúšky z 26.6.2019

Policajná hliadka v Kocúrkove by si mala naplánovať svoju trasu zo štartového bodu A do cieľového bodu B tak, aby bola čo možno najdlhšia, ale cez žiadnu ulicu neprešla viackrát.

Máme danú aktuálnu mapu Kocúrkova, ktorú tvoria križovatky (vrcholy grafu) a ulice (hrany grafu). Samotný graf je súvislý neorientovaný ohodnotený, pričom váhami na hranách sú vzdialenosti príslušných dvoch križovatiek so zaokrúhlením pomocou round(). Križovatky sú definované ako súradnice bodov v mape (dvojica celých čísel), ulice sú definované ako dvojice križovatiek (štyri celé čísla pre súradnice dvoch križovatiek). Naprogramujte metódy triedy Kocurkovo:

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

    def krizovatky(self):
        return set()

    def ulica(self, k1, k2):
        return None

    def trasa(self, k1, k2):
        return []

kde:

  • __init__() prečíta textový súbor s popisom Kocúrkova a vytvorí z neho neorientovaný graf; zvoľte si ľubovoľnú reprezentáciu;

  • krizovatky() vráti množinu (súradníc) všetkých križovatiek;

  • ulica() pre dané súradnice (dvojice celých čísel) dvoch križovatiek vráti buď váhu ulice, alebo None, keď neexistuje ulica medzi týmito dvomi križovatkami;

  • trasa() vráti najdlhšiu možnú trasu medzi zadanými dvoma križovatkami (budete počítať súčet váh na hranách trasy); výsledok vráti ako zoznam (list) dvojíc (tuple) celých čísel súradníc križovatiek; zrejme tento zoznam začína križovatkou k1 a končí križovatkou k2; uvedomte si, že trasa môže prechádzať cez niektoré vrcholy aj viackrát (nesmie prechádzať cez tú istú hranu viackrát).

Vstupný súbor, ktorý popisuje mapu Kocúrkova v každom riadku obsahuje definíciu jednej ulice, t.j. jednej hrany grafu, v tvare:

x1 y1 x2 y2

kde x1, y1 sú súradnice jednej križovatky a x2, y2 sú súradnice s ňou susediacej križovatky. Zrejme, v takomto grafe bude treba zabezpečiť, aby boli všetky hrany neorientované, t.j. fungovali oboma smermi.

Napr. pre takýto vstupný súbor:

100 100 200 100
150 50 100 100
200 100 150 50
200 100 120 200
200 100 190 220
190 220 120 200
190 220 50 210
100 100 50 210
100 100 120 200

takýto test:

if __name__ == '__main__':
    k = Kocurkovo('subor1.txt')
    print('krizovatky =', k.krizovatky())
    for k1, k2 in ((120, 200),(100, 100)), ((50, 210),(50, 210)), ((190, 220),(120, 200)):
        print(f'ulica({k1}, {k2}) = {k.ulica(k1, k2)}')
    for k1, k2 in ((50, 210),(150, 50)), ((120, 200),(190, 220)), ((50, 210),(50, 210)):
        print(f'trasa({k1}, {k2}) = {k.trasa(k1, k2)}')

vráti tento výsledok:

krizovatky = {(190, 220), (150, 50), (120, 200), (50, 210), (100, 100), (200, 100)}
ulica((120, 200), (100, 100)) = 102
ulica((50, 210), (50, 210)) = None
ulica((190, 220), (120, 200)) = 73
trasa((50, 210), (150, 50)) = [(50, 210), (190, 220), (200, 100), (120, 200), (100, 100),
                               (200, 100), (150, 50)]
trasa((120, 200), (190, 220)) = [(120, 200), (190, 220), (50, 210), (100, 100), (150, 50),
                                 (200, 100), (120, 200), (100, 100), (200, 100),
                                 (190, 220)]
trasa((50, 210), (50, 210)) = [(50, 210), (190, 220), (200, 100), (120, 200), (100, 100),
                               (150, 50), (200, 100), (100, 100), (50, 210)]

Uvedomte si, že ak existuje viac maximálnych trás, backtracking môže vrátiť ľubovoľnú z nich.

Za vyriešenie skúškovej úlohy môžete získať 60 bodov, pričom:

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

  • 35% je za nájdenie nejakého riešenia, ktoré nemusí mať maximálnu dĺžku

  • 35% za riešenie maximálnej dĺžky

  • 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/.