Skúška 2023/2024 - Variant C - 20.6.2024


Členovia skautského oddielu majú veľký deň - počas pretekov musia nazbierať čo najviac rôznych odznakov zdatnosti (tzv. bobríkov). Každý mladý skaut dostal kompletnú mapu (neorientovaný ohodnotený graf), v ktorej boli vyznačené kontrolné body (vrcholy grafu) a chodníky (hrany). Na každom chodníku skauti môžu získať celú množinu bobríkov (sú to hodnoty na hranách). Úlohou skauta je prebehnúť po chodníkoch zo štartového miesta do cieľového, pričom cez kontrolné miesta (vrcholy grafu) môže prejsť maximálne raz. Samozrejme, že by bolo dobre, keby na tejto trase získal čo najviac rôznych bobríkov.

Napíš program, ktorý pre danú mapu a štartové a cieľové miesto nájde takú cestu, na ktorej nazbiera čo najväčší počet rôznych bobríkov a zo všetkých takýchto ciest je táto najkratšia.

Mapa je zadaná v textovom súbore, ktorý má takúto štruktúru:

  • prvý riadok obsahuje počet vrcholov (menami vrcholov sú celé čísla od 0 po tento počet - 1);

  • každý ďalší riadok popisuje jeden chodník (hranu grafu) ako dvojicu vrcholov, na ktorom sa môže nachádzať niekoľko mien bobríkov;

  • formátom takéhoto riadku je postupnosť reťazcov oddelených medzerou, pričom prvý a posledný reťazec v riadku sú celé čísla - mená dvoch vrcholov, ktoré tvoria chodník a všetky reťazce medzi týmito dvoma vrcholmi sú mená bobríkov;

  • na chodníku sa môže nachádzať žiaden, jeden ale aj viac bobríkov;

  • graf je neorientovaný, preto, ak je vrchol A spojený chodníkom s B, tak potom aj vrchol B susedí s vrcholom A, zrejme to platí aj pre bobríky – možno to budeš musieť do grafu dodefinovať.

Zadefinuj triedu Mapa:

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

    def vrcholy(self):
        return set()          # vráti množinu vrcholov

    def hrana(self, v1, v2):
        return None           # vráti množinu bobríkov jednej hrany alebo None

    def hrany(self):
        return ...            # vráti generátor všetkých hrán

    def hladaj(self, start, ciel):
        return None           # vráti postupnosť vrcholov cesty alebo None

    def bobriky(self):
        return None           # vráti množinu alebo None

kde

  • metóda __init__(meno_suboru): prečíta súbor a vytvorí z neho neorientovaný ohodnotený graf; zvoľte si ľubovoľnú reprezentáciu grafu, pričom si môžete zadefinovať aj vlastné podtriedy, napríklad podtriedu Vrchol;

  • metóda vrcholy(): vráti množinu mien (celé čísla) všetkých vrcholov grafu;

  • metóda hrana(v1, v2): vráti hodnotu na hrane z vrcholu v1 do vrcholu v2; ak takáto hrana neexistuje, metóda vráti None, inak vráti množinu bobríkov (môže byť aj prázdna);

  • metóda hrany(): vráti generátor všetkých hrán ako postupnosť trojíc (tuple), kde pre každú hranu vráti čísla oboch vrcholov a váhu na hrane (typu set); napríklad v tvare (0, 1, {'a', 'b'});

  • metóda hladaj(start, ciel): pomocou backtrackingu nájde najkratšiu cestu, ktorá zozbiera čo najviac rôznych bobríkov; prejde cez každý vrchol maximálne raz (výsledok bude typu tuple); ak takáto cesta neexistuje, metóda vráti None;

  • metóda bobriky(): vráti množinu všetkých zozbieraných bobríkov pri poslednej hľadanej ceste; ak sa cesta nenašla, metóda vráti None.

Napríklad, pre takéto zadanie grafu:

9
0 b a 1
1 2
3 b 4
4 a 5
6 ab 7
7 8
0 a 3
3 a c 6
1 4
4 c a 7
2 a b 5
5 8

tento test:

if __name__ == '__main__':
    m = Mapa('subor1.txt')
    vv = m.vrcholy()
    print(f'vrcholy = {vv}')
    for v1, v2 in (1, 0), (0, 3), (2, 6):
        print(f'm[{v1}][{v2}] = {m.hrana(v1, v2)}')
    for v1, v2 in (0, 8), (1, 4), (2, 6):
        print(f'cesta z {v1} do {v2} = {m.hladaj(v1, v2)}, bobriky = {m.bobriky()}')

vypíše, napríklad:

vrcholy = {0, 1, 2, 3, 4, 5, 6, 7, 8}
m[1][0] = {'b', 'a'}
m[0][3] = {'a'}
m[2][6] = None
cesta z 0 do 8 = (0, 1, 4, 3, 6, 7, 8), bobriky = {'ab', 'b', 'a', 'c'}
cesta z 1 do 4 = (1, 0, 3, 6, 7, 4), bobriky = {'ab', 'b', 'a', 'c'}
cesta z 2 do 6 = (2, 5, 4, 7, 6), bobriky = {'ab', 'b', 'a', 'c'}

Uvedom si, že ak existuje viac najkratších ciest s maximálnym počtom bobríkov, backtracking môže vrátiť ľubovoľnú z nich.

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

Testy postupne na všetkých testovacích súboroch preverujú vlastnosti tvojich algoritmov, pri prvej chybe sa testovanie s daným súborom preruší a ďalšie časti sa netestujú:

  • 35% bodov za vytvorenie grafu

  • 65% bodov za algoritmus hľadania cesty v grafe

Tvoj odovzdaný program musí začínať tromi riadkami komentárov:

# skuska 2023/2024 variant C
# autor: Janko Hraško
# datum: 20.6.2024