2. tréningové zadanie - skúška z 6.6.2018

Turistická kancelária

Turistická kancelária organizuje prehliadky po starom meste a maximálne sa snaží vychádzať v ústrety požiadavkám turistov. Turisti si môžu vybrať ľubovoľné pamiatky a sprievodca s nimi prejde zvolenú prehliadku, pričom kancelária si účtuje jednotný poplatok za každú navštívenú pamiatku. Majiteľ kancelárie je zvedavý, aké rôzne prehliadky sa dajú zostaviť, ak prehliadka začne aj skončí na tom istom mieste a prejde cez presne zadaný počet pamiatok.

Mapu starého mesta máme uloženú v tvare neorientovaného grafu, v ktorom vrcholy reprezentujú pamiatky a hrany sú ulice. Program pre zadaný štartový vrchol a dĺžku trasy nájde ľubovoľný cyklus. Cyklom je taká cesta v grafe, ktorá začína aj končí v tom istom vrchole a pritom prechádza len cez navzájom rôzne vrcholy.

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

  • každý riadok popisuje jeden vrchol a skladá sa z jednej alebo viacerých dvojíc celých čísel;

  • prvá dvojica čísel označujú súradnice pamiatky na mape (bude to pre nás meno vrcholu);

  • za týmito súradnicami nasledujú súradnice ďalších pamiatok, ktoré sú spojené s danou pamiatkou ulicou;

  • graf je neorientovaný, preto, ak má pamiatka A susednú pamiatku B, tak potom aj B susedí s A – možno to bude treba do grafu doplniť.

Zadefinujte triedu Graf:

class Graf(object):
    class Vrchol:
        def __init__(self):
            self.sus = set()

    def __init__(self, meno_suboru):
        self.g = {}
        ...

    def najdi(self, start, dlzka):
        ...
        return set()

kde

  • vnorená definícia triedy Vrchol má atribút sus, ktorý bude obsahovať množinu (typ set) všetkých susediacich vrcholov (teda ich mien), to znamená, že sus je množina dvojíc (tuple) celých čísel;

  • metóda __init__(self, meno_suboru): prečíta súbor a vytvorí z neho graf: atribút g (typu dict) bude ako hodnoty obsahovať všetky vrcholy grafu, teda objekty typu Vrchol; kľúčmi budú polohy vrcholov na mape, teda dvojice (tuple) celých čísel;

  • metóda najdi(self, start, dlzka): pomocou backtrackingu nájde ľubovoľný cyklus zadanej dĺžky, ktorý začína (a končí) v zadanom vrchole start; metóda vráti cyklus ako postupnosť (tuple alebo list) mien vrcholov (dvojíc čísel); ak neexistuje žiaden cyklus, ktorý by spĺňal tieto podmienky, metóda vráti None; testovač zavolá túto metódu viac krát s rôznymi štartovými vrcholmi a aj dĺžkami.

Napr. pre takéto zadanie grafu:

_images/sk2018l2.png
(70, 10) (40, 10) (70, 40)
(10, 10) (10, 40) (40, 10)
(10, 40) (10, 10) (40, 40)
(40, 10)
(40, 40) (10, 40) (40, 10) (70, 40)
(70, 40) (70, 10) (40, 40)

tento test:

if __name__ == '__main__':
    g = Graf('subor1.txt')
    for key, value in g.g.items():
        print('vrchol =', key, 'sus =', value.sus)
    print(g.najdi((70, 10), 3))
    print(g.najdi((10, 40), 4))
    print(g.najdi((40, 40), 4))

vypíše napríklad:

vrchol = (10, 40) sus = {(40, 40), (10, 10)}
vrchol = (40, 40) sus = {(10, 40), (70, 40), (40, 10)}
vrchol = (70, 40) sus = {(70, 10), (40, 40)}
vrchol = (10, 10) sus = {(10, 40), (40, 10)}
vrchol = (70, 10) sus = {(70, 40), (40, 10)}
vrchol = (40, 10) sus = {(70, 10), (40, 40), (10, 10)}
None
[(10, 40), (40, 40), (40, 10), (10, 10), (10, 40)]
[(40, 40), (10, 40), (10, 10), (40, 10), (40, 40)]

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ú:

  • 40% bodov za vytvorenie grafu

  • 60% bodov za algoritmus hľadania cyklu v grafe