Zadanie skúšky 5.6.2017

V Kocúrkove majú veľmi zaujímavo organizované všetky pozemky a chodníky:

  • každý pozemok je dookola obkolesený chodníkom
  • ak nejaké dva pozemky susedia, majú spoločnú nejakú časť chodníka
  • chodníky okolo pozemkov (teda hranice pozemkov) sú definované pomocou postupnosti názvov hraničných kameňov – niekto si dal robou a všetkým hraničným kameňom v Kocúrkove pridelil nejaké názvy (väčšinou ako nejaké písmeno a číslo), napr.
    • ak má nejaký pozemok hranicu popísanú názvami kameňov ['a3', 'b1', 'a2'] a nejaký iný názvami ['a2', 'a1', 'a3'], oba pozemky sú trojuholníkového tvaru a majú spoločnú časť chodníka 'a2' - 'a3'
    • zrejme takto popísané hranice pozemkov pomocou názvov hraničných kameňov sú uzavreté oblasti a teda spojený chodníkom je aj prvý a posledný kameň
  • počítajte s tým, že žiadna časť chodníka neprechádza cez vnútro nejakého pozemku – všetky chodníky sú len okolo pozemkov

Ak sa niekto prechádza po chodníkoch Kocúrkova, vždy prechádza okolo aspoň jedného pozemku a niekedy súčasne okolo dvoch rôznych. Pri dlhších prechádzkach niekedy takto môže prejsť aj okolo všetkých pozemkov.

Vašou úlohou bude navrhnúť takú prechádzku z nejakého štartového miesta, pomocou ktorej prejdeme okolo všetkých dopredu určených pozemkov. Samotné rozloženie pozemkov, teda popis chodníkov, prečítate z textového súboru. Ak existuje viac rôznych prechádzok, pomocou ktorých sa dá prejsť okolo určených pozemkov, vyberiete najkratšiu z nich. Dĺžka prechádzky je v tomto prípade definovaná ako počet hraničných kameňov, popri ktorých sa prechádza.

Na navrhnutú prechádzku máme ešte tieto dôležité požiadavky:

  • popri žiadnom hraničnom kameni nesmieme prejsť viac ako raz
  • počas prechádzky akceptujeme návštevu nejakého pozemku len vtedy, keď prejdeme po nejakej časti chodníka okolo neho, teda nestačí prejsť len popri jednom hraničnom kameni daného pozemku

Z pohľadu dátovej štruktúry graf:

  • hraničné kamene sú vrcholy grafu
  • časti chodníkov, teda spojnice medzi kameňmi (vrcholmi) sú hrany grafu
  • každá hrana prechádza okolo nejakého jedného alebo možno dvoch pozemkov – táto informácia (množina pozemkov) je hodnotou (váhou) hrany

Riešenie zapíšte do triedy Graf s týmito metódami:

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

    def pozemky(self):
        return set()

    def vrcholy(self):
        return set()

    def hrana(self, v1, v2):
        return None

    def ries(self, v1, ciel):
        return []

Kde metódy:

  • __init__(meno_suboru) prečíta súbor a vytvorí z neho reprezentáciu neorientovaného ohodnoteného grafu
  • hrana(v1, v2) vráti hodnotu hrany: buď je to jedno alebo dvoj prvková množina mien pozemkov, alebo None, ak neexistuje hrana medzi týmito dvoma vrcholmi
  • vrcholy() vráti množinu názvov všetkých vrcholov (hraničných kameňov)
  • pozemky() vráti množinu názvov všetkých pozemkov
  • ries(v1, ciel) pomocou backtrackingu nájde najkratšiu cestu z vrcholu v1, ktorá prejde okolo všetkých pozemkov špecifikovaných v parametri ciel (typu set) – metóda vráti buď prázdne pole (nenašiel žiadnu cestu), alebo pole (typ list) s nájdenou cestou, teda postupnosť názvov vrcholov (ak je takých viac, vráti ľubovoľnú z nich)

Môžete si dodefinovať aj ďalšie pomocné metódy. Ak chcete definovať nejaké ďalšie pomocné triedy, zapíšte ich ako vnorené do triedy Graf.

Textový súbor obsahuje popis grafu v tvare:

  • každý riadok obsahuje popis jedného pozemku: je to meno pozemku, za ktorým nasleduje postupnosť názvov vrcholov na obvode pozemku (zrejme aj prvý a posledný vrchol sú spojené hranou)
  • uvedomte si, že v neorientovanom grafe by mala byť každá hrana orientovaná oboma smermi
  • môžete predpokladať, že súbor je zadaný korektne

Napr. súbor

p1 a3 b1 a2
p2 a1 b2 a3
p3 a1 b3 a2
p4 a2 a1 a3

označuje graf so šiestimi vrcholmi a 9 hranami, ktoré definujú 4 pozemky. Všimnite si, že pozemok p4 susedí s troma zvyšnými pozemkami, pričom tieto tri pozemky majú len jedného suseda – pozemok p4.

Program môžete testovať napr. takto:

if __name__ == '__main__':
    g = Graf('subor1.txt')
    print('pozemky =', g.pozemky())
    print('vrcholy =', g.vrcholy())
    for v1,v2 in ('a3','b2'),('a2','a1'),('b1','a1'):
        print('hrana({!r},{!r}) = {!r}'.format(v1,v2,g.hrana(v1,v2)))
    print('riesenie =', g.ries('b1',{'p2','p4'}))

a pre vyššie uvedený textový súbor by mal vypísať (existuje viac správnych riešení, toto je jedno z nich):

pozemky = {'p2', 'p3', 'p1', 'p4'}
vrcholy = {'b3', 'a2', 'a3', 'a1', 'b1', 'b2'}
hrana('a3','b2') = {'p2'}
hrana('a2','a1') = {'p3', 'p4'}
hrana('b1','a1') = None
riesenie = ['b1', 'a3', 'a1']

Za vyriešenie skúškovej úlohy môžete získať 60 bodov, pričom:

  • 30% je za vytvorenie grafu zo súboru, t.j. správne fungovanie metód pozemky(), vrcholy() a hrana()
  • 30% je za nájdenie nejakého riešenia, ktoré nemusí mať minimálnu dĺžku
  • 30% za riešenie minimálnej dĺžky
  • 10% za správny výsledok takých zadaní, pre ktoré neexistuje riešenie

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

Skúška pokračuje od 12:00 vyhodnotením v kancelárii m162.