3. tréningové zadanie - skúška z 18.6.2018

Skauti a bobríci

Členovia skautského oddielu majú veľký deň - počas preteku 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íšte 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 budete musieť do grafu dodefinovať.

Zadefinujte triedu Mapa:

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

    def vrcholy(self):
        return set()          # vrati mnozinu vrcholov

    def hrana(self, v1, v2):
        return None           # vrati mnozinu alebo None

    def hladaj(self, start, ciel):
        return None           # vrati postupnost vrcholov cesty alebo None

    def bobriky(self):
        return None           # vrati mnozinu alebo None

kde

  • metóda __init__(self, 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. podtriedu Vrchol;

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

  • metóda hrana(self, 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 hladaj(self, 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 list alebo tuple); ak takáto cesta neexistuje, metóda vráti None;

  • metóda bobriky(self): 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. 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.:

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'}

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

Testy postupne na všetkých testovacích súboroch preverujú vlastnosti vašich 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