Skúška 2022/2023 - Variant A


Výstavisko

Prišli sme na veľtrh, pričom na výstavisku každý vystavovateľ rozdáva nejaký reklamný darček, napríklad pero, prívesok, odznak, atď. Radi by sme nazbierali čo najviac rôznych reklamných darčekov. Dostali sme kompletnú mapu (neorientovaný ohodnotený graf), v ktorej boli vyznačené križovatky (vrcholy grafu) a uličky s vystavovateľmi s darčekmi (hrany grafu). V každej uličke preto môžeme získať celú množinu darčekov (sú to hodnoty na hranách grafu). Našou úlohou je prejsť po uličkách výstaviska zo štartového miesta do cieľového, pričom cez križovatky (vrcholy grafu) môžeme prejsť maximálne raz. Samozrejme, že by bolo dobre, keby sme na tejto trase získali čo najviac rôznych darčekov.

Napíš program, ktorý pre danú mapu a štartové a cieľové miesto nájde takú cestu (postupnosť vrcholov), na ktorej nazbiera čo najväčší počet rôznych darčekov 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 jednu uličku (hranu grafu) ako dvojicu vrcholov, na ktorej sa môže nachádzať niekoľko mien darčekov;

  • formátom takéhoto riadku je postupnosť reťazcov oddelených medzerou, pričom prvý a druhý reťazec v riadku sú celé čísla - mená dvoch vrcholov, ktoré tvoria uličku a všetky zvyšné reťazce v riadku sú mená darčekov;

  • na uličke sa môže nachádzať žiaden, jeden ale aj viac darčekov;

  • graf je neorientovaný, preto, ak je vrchol A spojený uličkou s B, tak potom aj vrchol B susedí s vrcholom A, zrejme to platí aj pre darčeky.

Zadefinuj triedu Mapka:

class Mapka:
    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 alebo None

    def hladaj(self, start, ciel):
        ...                   # vráti generátor: postupnosť vrcholov cesty

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


kde

  • metóda __init__(meno_suboru): prečíta súbor a vytvorí z neho neorientovaný ohodnotený graf; zvoľ si ľubovoľnú reprezentáciu grafu, pričom si môžeš 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 darčekov (môže byť aj prázdna);

  • metóda hladaj(start, ciel): pomocou backtrackingu nájde najkratšiu cestu, ktorá zozbiera čo najviac rôznych darčekov; prejde cez každý vrchol maximálne raz; funkcia túto nájdenú cestu vráti ako generátor ;

  • metóda darceky(): vráti množinu všetkých zozbieraných darčekov pri poslednej hľadanej ceste; ak sa cesta nenašla, metóda vráti prázdnu množinu.

Napríklad, pre takéto zadanie grafu:

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

tento test:

if __name__ == '__main__':
    m = Mapka('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),
              '... darceky =', m.darceky())

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 ... darceky = {'ab', 'c', 'b', 'a'}
cesta z 1 do 4 = 1 0 3 6 7 4 ... darceky = {'ab', 'a', 'c', 'b'}
cesta z 2 do 6 = 2 5 4 7 6 ... darceky = {'ab', 'c', 'b', 'a'}

Uvedom si, že ak existuje viac najkratších ciest s maximálnym počtom darčekov, 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/.

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

# skuska 2022/2023 variant A
# autor: Janko Hraško
# datum: 17.5.2024