4. tréningové zadanie - skúška z 27.6.2018

Výstavisko

Prišli sme na veľtrh, pričom na výstavisku každý vystavovateľ rozdáva nejaký reklamný darček, napr. 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íšte 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 – možno to budete musieť do grafu dodefinovať.

Zadefinujte triedu Mapka:

class Mapka:
    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 []             # vrati postupnost vrcholov cesty

    def darceky(self):
        return set()          # vrati mnozinu

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 darčekov (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 darčekov; prejde cez každý vrchol maximálne raz (výsledná postupnosť bude typu list alebo tuple); ak takáto cesta neexistuje, metóda vráti prázdnu postupnosť;

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

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

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