6. tréningové zadanie - skúška z 7.6.2017

Vesmírna stanica má pre posádku pripravených N obytných modulov, ktoré sú na začiatku zapečatené. Ak sa posádka do niektorého z týchto modulov nasťahuje, predpokladá sa, že tam bude bývať celý rok a pritom využije všetky pripravené zdroje. Po roku musí posádka tento modul opustiť, lebo tento sa z vesmírnej stanice odpojí ako už vyčerpaný (zahodí sa do vesmíru). Posádka sa teda presťahuje do niektorého ďalšieho modulu a v tomto býva ďalší rok.

Zrejme, takto sa dá na vesmírnej stanici bývať maximálne N rokov. Je tu jeden problém: moduly sú navzájom pospájané prepojovacími chodbami a nie z každého modulu sa dá dostať do ľubovoľného ďalšieho. Asi by vznikol veľký problém, keby posádka bývala v module, z ktorého sa po roku nedá prejsť do žiadneho ďalšieho. Uvedomte si, že každý predtým navštívený modul je už od vesmírnej stanice odpojený.

Máme daný súbor s informáciami o prepojení modulov: moduly majú svoje celočíselné kódy a všetky riadky súboru majú tvar:

123-1749

t.j. modul s prvým kódom 123, je prepojený s nejakým iným modulom, ktorého kód je 1749.

Schéma vesmírnej stanice tvorí neorientovaný neohodnotený graf, v ktorom hrany reprezentujú chodby a vrcholy sú obytné moduly. Program potom pre zadaný štartový vrchol nájde ľubovoľnú maximálne dlhú trasu, ktorou sa prejde cez najväčší možný počet vrcholov a pritom neprejde cez žiaden vrchol viackrát. Niekedy budeme potrebovať nájsť maximálnu trasu, ktorá obíde zadanú množinu vrcholov (napr. zistili sme, že niektoré moduly sú neobývateľné, lebo boli poškodené letiacimi asteroidmi).

Zadefinujte triedu VesmirnaStanica:

class VesmirnaStanica:
    def __init__(self, meno_suboru):
        self.m = []   # zoznam mien modulov
        self.g = []   # tabulka susednosti
        ...

    def moduly(self):
        return set()

    def chodba(self, m1, m2):
        return False

    def zisti(self, m1, bez=None):
        return []

kde

  • metóda __init__(self, meno_suboru): prečíta súbor a vytvorí z neho neorientovaný neohodnotený graf; realizujte ho ako tabuľku susedností (dvojrozmerný zoznam hodnôt True alebo False), pričom v atribúte self.m bude zvolené poradie mien modulov;

  • metóda moduly(self): vráti množinu číselných kódov všetkých vrcholov grafu;

  • metóda chodba(self, m1, m2): zistí, či medzi modulmi m1 a m2 je chodba, t.j. či vrcholy m1 a m2 sú spojené hranou; metóda vráti True alebo False;

  • metóda zisti(self, m1): pomocou backtrackingu nájde ľubovoľnú maximálne dlhú trasu, ktorá prejde cez maximálny počet vrcholov práve raz (výsledok bude typu list); ak takáto cesta neexistuje, metóda vráti [];

  • metóda zisti(self, m1, bez): ďalší parameter bez obsahuje množinu vrcholov, ktoré sa pri hľadaní maximálnej trasy vynechajú; metóda potom rovnako ako verzia bez tohto parametra nájde ľubovoľnú maximálne dlhú trasu, ktorá prejde cez maximálny počet vrcholov ale bez uvedených v množine bez; táto metóda môže byť zavolaná s rôznymi množinami takto zablokovaných vrcholov.

Napr. pre takéto zadanie grafu:

111-112
111-121
122-112
122-121
211-212
211-221
222-212
222-221
111-211
112-212
121-221
122-222

takýto test:

if __name__ == '__main__':
    vs = VesmirnaStanica('subor1.txt')
    print('moduly =', vs.moduly())
    for m1 in vs.moduly():
        pocet = len({m2 for m2 in vs.moduly() if vs.chodba(m1, m2)})
        print(m1, pocet, vs.zisti(m1), vs.zisti(m1, {111, 212}))

vypíše napr.:

moduly = {111, 112, 211, 212, 121, 122, 221, 222}
111 3 [111, 112, 122, 121, 221, 211, 212, 222] []
112 3 [112, 122, 121, 221, 222, 212, 211, 111] [112, 122, 121, 221, 211]
211 3 [211, 212, 112, 122, 222, 221, 121, 111] [211, 221, 121, 122, 112]
212 3 [212, 112, 122, 121, 111, 211, 221, 222] []
121 3 [121, 122, 112, 212, 222, 221, 211, 111] [121, 122, 222, 221, 211]
122 3 [122, 112, 212, 211, 111, 121, 221, 222] [122, 121, 221, 211]
221 3 [221, 121, 122, 112, 111, 211, 212, 222] [221, 121, 122, 112]
222 3 [222, 122, 112, 212, 211, 221, 121, 111] [222, 122, 121, 221, 211]

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

Z úlohového servera L.I.S.T. si stiahnite kostru programu skuska.py. Mali by ste dodržať tieto vlastnosti programu:

  • Nemeňte mená už zadaných atribútov (metód).

  • Do existujúcej triedy môžete pridávať vlastné atribúty a metódy, nepoužívajte ale atribúty typu dict.

  • Pri testovaní vášho riešenia sa bude kontrolovať aj štruktúra vami vytvoreného grafu.

Aby ste mohli spúšťať skúškové testy, riešenie (bez ďalší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ú:

  • 40% bodov za vytvorenie grafu

  • 40% bodov za algoritmus hľadania maximálnej trasy

  • 20% bodov za hľadanie trasy, ktorá bude bez označených vrcholov

  • pozrite si testovacie dáta v súboroch 'subor1.txt', 'subor2.txt', 'subor3.txt', …, ktoré bude používať testovač