35. Backtracking na grafoch

Využijeme mierne upravenú triedu Graf z prednášky 33. Algoritmy prehľadávania grafu:

import tkinter
import random

class Graf:

    class Vrchol:
        canvas = None

        def __init__(self, x, y):
            self.sus = {}
            self.xy = x, y

        def pridaj_hranu(self, v2, vaha):
            self.sus[v2] = vaha

        def kresli(self, farba='gray'):
            x, y = self.xy
            self.id = self.canvas.create_oval(x-15, y-15, x+15, y+15, fill=farba, outline='')

        def zafarbi(self, farba):
            self.canvas.itemconfig(self.id, fill=farba)

        #-----------------------

    def __init__(self, n):
        self.vrcholy = []
        self.canvas = self.Vrchol.canvas = tkinter.Canvas(bg='white', width=600, height=600)
        self.canvas.pack()
        d = (min(600, 600)-60) // (n-1)
        for i in range(n):
            for j in range(n):
                x1, y1 = d*j+random.randrange(20, 40), d*i+random.randrange(20, 40)
                v1 = self.pridaj_vrchol(x1, y1)
                if j > 0 and random.randrange(3):
                    x2, y2 = self.vrcholy[v1-1].xy
                    vaha = round(((x1-x2)**2+(y1-y2)**2)**.5)
                    self.pridaj_hranu(v1, v1-1, vaha)
                if i > 0 and random.randrange(3):
                    x2, y2 = self.vrcholy[v1-n].xy
                    vaha = round(((x1-x2)**2+(y1-y2)**2)**.5)
                    self.pridaj_hranu(v1, v1-n, vaha)
        self.id = {}
        for i in range(len(self.vrcholy)):
            for j in self.vrcholy[i].sus:
                if i < j:
                    self.kresli_hranu(i, j)
        for vrchol in self.vrcholy:
            vrchol.kresli()
        self.canvas.bind('<Button-1>', self.udalost_klik)
        self.klik = []

    def pridaj_vrchol(self, x, y):
        self.vrcholy.append(self.Vrchol(x, y))
        return len(self.vrcholy) - 1

    def pridaj_hranu(self, i, j, vaha):
        self.vrcholy[i].pridaj_hranu(j, vaha)
        self.vrcholy[j].pridaj_hranu(i, vaha)

    def je_hrana(self, i, j):
        return j in self.vrcholy[i].sus

    def kresli_hranu(self, i, j, farba='gray'):
        self.id[i, j] = self.id[j, i] = \
            self.canvas.create_line(self.vrcholy[i].xy, self.vrcholy[j].xy,
                                    fill=farba, width=3)

    def zafarbi_hranu(self, i, j, farba):
        self.canvas.itemconfig(self.id[i, j], fill=farba)

    def udalost_klik(self, event):
        for i in range(len(self.vrcholy)):
            x, y = self.vrcholy[i].xy
            if (x-event.x)**2 + (y-event.y)**2 < 15**2:
                self.vrcholy[i].zafarbi('blue')
                self.klik.append(i)
                return

graf = Graf(7)
print(*[(i, v.sus) for i, v in enumerate(graf.vrcholy)], sep='\n')

Upravili sme:

  • graf je ohodnotený, t.j. pre každú hranu si uchovávame jej váhu (zvolili sme vzdialenosť vrcholov v rovine)

    • namiesto zoznamu množín susedností graf reprezentujeme ako zoznam vrcholov, v ktorom si každý vrchol pamätá susedov v asociatívnom poli (dict) s hodnotami váha hrany

  • generovanie pozícií vrcholov: náhodne sme ich trochu poposúvali

  • pridali sme metódu udalost_klik(), ktorá nielen zafarbuje kliknuté vrcholy, ale si ich aj pamätá v zozname self.klik

Základná schéma backtrackingu

Pripomeňme si, na čo vieme použiť prehľadávanie do hĺbky a do šírky:

  • algoritmus do hĺbky využijeme hlavne na zistenie príslušnosti vrcholov do komponentov

  • algoritmus do šírky slúži na nájdenie vzdialenosti (najkratšej cesty) dvoch vrcholov

    • takáto dĺžka cesty neberie do úvahy váhu na hranách, ale len počet vrcholov na ceste

Prehľadávanie s návratom

  • pracuje na princípe prechádzania (generovania) všetkých možných ciest v grafe, ktoré vychádzajú z nejakého vrcholu

  • pri tomto generovaní, môžeme zisťovať rôzne parametre týchto vygenerovaných ciest, napr. súčet váh na hranách cesty, alebo, či cesta prešla cez nejaký konkrétny vrchol a pod.

  • uvedomte si, že takéto prehľadávanie (spomínali sme to ako hrubá sila, brute force) bude pre väčšie grafy časovo veľmi náročné, keďže vygenerovaných ciest môže byť obrovské množstvo

  • často závisí od detailov v nejakom teste, ako rýchlo takéto prehľadávanie nájde riešenie (hovoríme tomu, že využijeme nejakú heuristiku)

  • vo vyšších ročníkoch sa zoznámite s algoritmami, ktoré vedia riešiť niektoré z našich úloh aj bez hrubej sily

Základnú schému backtrackingu, môžeme pre graf upraviť napr. takto:

class Graf:
    ...

    def start(self, v1, v2):
        self.visited = set()
        self.backtracking(v1, v2)

    def backtracking(self, v1, v2):
        self.visited.add(v1)
        if v1 == v2:
            ... # spracuj riešenie
        else:
            for v in self.vrcholy[v1].sus:
                if v not in self.visited:
                    # vizualizuj prechádzanú hranu
                    self.backtracking(v, v2)
                    # zruš vizualizovanie prechádzanej hrany
        self.visited.remove(v1)
  • podobne ako pri prechádzaní grafu do hĺbky, aj tu musíme mať nejakú štruktúru visited, aby sme neprechádzali cez nejaký vrchol viackrát

  • parameter v1 označuje práve prechádzaný vrchol, v2 cieľový vrchol, do ktorého sa snažíme dostať

  • tento algoritmus naozaj nájde všetky možné cesty z vrcholu v1 do v2, pričom pri spracovaní riešenia môžeme tieto nájdené cesty nejako pretriediť a vybrať si len tú najvhodnejšiu

Môžeme to otestovať:

graf = Graf(7)
graf.start(0, 48)
print(graf.pocet)

ale dozvieme sa len počet nájdených riešení (počet možných ciest z vrcholu 0 do vrcholu 48).

Vytvorme takýto program:

  • po kliknutí na dva rôzne vrcholy sa naštartuje backtracking

  • samotný algoritmus bude každú prechádzanú hranu prefarbovať a na malú chvíľu pritom spomalí výpočet

  • konkrétne nasledovný program bude počítať počet rôznych ciest a tento počet na záver vypíše

Upravíme aj udalost_klik():

class Graf:
    ...

    def udalost_klik(self, event):
        for i in range(len(self.vrcholy)):
            x, y = self.vrcholy[i].xy
            if (x-event.x)**2 + (y-event.y)**2 < 15**2:
                self.vrcholy[i].zafarbi('blue')
                self.klik.append(i)
                self.canvas.update()
                if len(self.klik) == 2:           # <=== po druhom kliknutí
                    self.start(*self.klik)
                return

    def start(self, v1, v2):
        self.visited = set()
        self.pocet = 0
        self.backtracking(v1, v2)
        # keď skončí backtracking
        print('pocet rieseni =', self.pocet)

    def backtracking(self, v1, v2):
        if v1 == v2:
            self.pocet += 1      # spracuj riešenie
            print('nasiel som cestu')
        else:
            self.visited.add(v1)
            for v in self.vrcholy[v1].sus:
                if v not in self.visited:
                    # vizualizuj prechádzanú hranu
                    self.zafarbi_hranu(v1, v, 'red')
                    self.canvas.update()
                    self.canvas.after(100)
                    self.backtracking(v, v2)
                    # zruš vizualizovanie prechádzanej hrany
                    self.zafarbi_hranu(v1, v, 'gray')
            self.visited.remove(v1)

graf = Graf(7)
  • volanie self.canvas.after(100) označuje, že tu program zastane na 100 ms, tento riadok môžeme vyhodiť, aby bolo hľadanie ciest rýchlejšie

V niektorých situáciách sa nám môže hodiť, keď po nájdení prvého riešenia, zastavíme beh backtrackingu ale tak, aby táto cesta ostala nakreslená:

class Graf:
    ...

    def backtracking(self, v1, v2):
        if self.pocet > 0:           # aby sa ďalej nevnáral do rekurzie
            return
        if v1 == v2:
            self.pocet += 1          # spracuj riešenie
            print('nasiel som cestu')
        else:
            self.visited.add(v1)
            for v in self.vrcholy[v1].sus:
                if v not in self.visited:
                    # vizualizuj prechádzanú hranu
                    self.zafarbi_hranu(v1, v, 'red')
                    self.canvas.update()
                    self.canvas.after(100)
                    self.backtracking(v, v2)
                    if self.pocet > 0:               # aby sa nezrušilo zafarbenie hrán
                        return
                    # zruš vizualizovanie prechádzanej hrany
                    self.zafarbi_hranu(v1, v, 'gray')
            self.visited.remove(v1)

Častejšie ale budeme prechádzať všetky vygenerované cesty a hľadať medzi nimi jednu s nejakou vlastnosťou, napr. cestu s najmenším ohodnotením: ak je na hranách napr. cena, tak hľadáme najlacnejšiu cestu. Zrejme je rozdiel medzi najkratšou cestou (s najmenej prechádzanými vrcholmi) a najlacnejšou cestou.

Hodnota cesty

Pri generovaní cesty budeme evidovať aj jej hodnotu (ako súčet ohodnotení hrán). Najprv to ukážeme pomocou atribútu hodnota v triede Graf, ktorý sa pri prechode hranou zvyšuje a pri návrate znižuje:

class Graf:
    ...

    def start(self, v1, v2):
        self.visited = set()
        self.pocet = 0
        self.hodnota = 0               # hodnota celej cesty
        self.backtracking(v1, v2)
        print('pocet =', self.pocet)

    def backtracking(self, v1, v2):
        if v1 == v2:
            self.pocet += 1
            print('cesta s hodnotou', self.hodnota)
        else:
            self.visited.add(v1)
            for v in self.vrcholy[v1].sus:
                if v not in self.visited:
                    self.hodnota += self.vrcholy[v1].sus[v]
                    self.zafarbi_hranu(v1, v, 'red')
                    self.canvas.update()
                    #self.canvas.after(100)

                    self.backtracking(v, v2)

                    self.hodnota -= self.vrcholy[v1].sus[v]
                    self.zafarbi_hranu(v1, v, 'gray')
            self.visited.remove(v1)

Hodnotu cesty môžeme vytvárať aj v parametri funkcie backtracking(). Na začiatku je hodnota cesty 0, vždy keď algoritmus prejde po nejakej hrane, tak sa táto hodnota zvýši. Keď cesta dorazí do cieľa (do vrcholu v2), zistí sa, či táto nová vygenerovaná cesta je lepšia (napr. menšia ako doterajšie minimum, alebo väčšia ako doterajšie maximum) ako doteraz uchovávané hodnoty v premenných self.min a self.max. Všimnite si, že takto uchovávanú hodnotu v parametri nemusíme pri návrate z rekurzie znižovať, ako sme to robili v predchádzajúcej verzii:

class Graf:
    ...

    def start(self, v1, v2):
        self.visited = set()
        self.pocet = 0
        self.min = self.max = None
        self.backtracking(v1, v2, 0)
        print('pocet =', self.pocet)
        print('najkratsia =', self.min)
        print('najdlhsia  =', self.max)

    def backtracking(self, v1, v2, hodnota):
        if v1 == v2:
            self.pocet += 1
            # print('cesta s hodnotou', hodnota)
            if self.min is None or self.min > hodnota:
                self.min = hodnota
            if self.max is None or self.max < hodnota:
                self.max = hodnota
        else:
            self.visited.add(v1)
            for v in self.vrcholy[v1].sus:
                if v not in self.visited:
                    self.zafarbi_hranu(v1, v, 'red')
                    self.canvas.update()
                    #self.canvas.after(100)

                    self.backtracking(v, v2, hodnota + self.vrcholy[v1].sus[v])

                    self.zafarbi_hranu(v1, v, 'gray')
            self.visited.remove(v1)

Zapamätanie celej cesty

Doterajšie verzie algoritmu generovali všetky cesty, ale si ich nikde neuchovávali. Využijeme pomocný zoznam (premenná self.cesta), do ktorého budeme ukladať momentálnu cestu. Tiež si ju uložíme do premennej self.najcesta, keď vyhovuje nejakej podmienke. Po skončení algoritmu backtracking túto cestu vypíšeme:

class Graf:
    ...

    def start(self, v1, v2):
        self.visited = set()
        self.pocet = 0
        self.min = self.max = None
        self.cesta, self.najcesta = [], []
        self.backtracking(v1, v2, 0)
        print('pocet =', self.pocet)
        print('min =', self.min)
        print('max =', self.max)
        print('najkratsia cesta =', self.najcesta)

    def backtracking(self, v1, v2, hodnota):
        self.cesta.append(v1)
        if v1 == v2:
            self.pocet += 1
            #print('nasiel som cestu s hodnotou', hodnota)
            if self.min is None or self.min > hodnota:
                self.min = hodnota
                self.najcesta = self.cesta[:]             # zapamätáme kópiu cesty
            if self.max is None or self.max < hodnota:
                self.max = hodnota
        else:
            self.visited.add(v1)
            for v in self.vrcholy[v1].sus:
                if v not in self.visited:
                    #self.zafarbi_hranu(v1, v, 'red')
                    #self.canvas.update()
                    #self.canvas.after(100)

                    self.backtracking(v, v2, hodnota + self.vrcholy[v1].sus[v])

                    #self.zafarbi_hranu(v1, v, 'gray')
            self.visited.remove(v1)
        self.cesta.pop()
  • pri uchovávaní si najlepšej cesty musíme urobiť kópiu z premennej self.cesta, lebo nestačí urobiť len obyčajné priradenie, ktoré by priradilo len referenciu na premennú

  • aby sme algoritmus urýchlili, odstránili sme aj vykresľovanie hrán

Tento algoritmus nájde najlepšiu cestu, ale ju nevykreslí, len vypíše čísla vrcholov. Ďalšia verzia programu vykresľuje najlepšiu cestu - teraz hľadáme cestu nie s najmenšou hodnotou, ale s najväčšou:

class Graf:
    ...

    def start(self, v1, v2):
        self.visited = set()
        self.min = self.max = None
        self.cesta, self.najcesta = [], []
        self.backtracking(v1, v2, 0)
        print('min =', self.min)
        print('max =', self.max)
        for i in range(len(self.najcesta)-1):
            self.zafarbi_hranu(self.najcesta[i], self.najcesta[i+1], 'blue')

    def backtracking(self, v1, v2, hodnota):
        self.cesta.append(v1)
        if v1 == v2:
            if self.min is None or self.min > hodnota:
                self.min = hodnota
            if self.max is None or self.max < hodnota:
                self.max = hodnota
                self.najcesta = self.cesta[:]
        else:
            self.visited.add(v1)
            for v in self.vrcholy[v1].sus:
                if v not in self.visited:
                    self.backtracking(v, v2, hodnota + self.vrcholy[v1].sus[v])
            self.visited.remove(v1)
        self.cesta.pop()
  • možno vám napadlo, že keď si pamätáme cestu, nepotrebujeme udržiavať množinu self.visited, veď self.cesta obsahuje tie isté vrcholy - je to pravda, len hľadanie vrcholu v množine (typ set) je pre veľa prvkov rýchlejšie ako v zozname (typ list) a takýto program sa môže pre niekoho zdať menej čitateľný

  • podobne ako sme namiesto atribútu self.hodnota pridali nový parameter hodnota do metódy backtracking(), môžeme pridať aj parameter cesta, v ktorom sa vytvára momentálna postupnosť prechádzaných vrcholov

Hľadanie najkratšej cesty môžeme teraz zapísať:

class Graf:
    ...

    def start(self, v1, v2):
        self.naj = None
        self.najcesta = []
        self.backtracking(v1, v2, 0, [v1])        # vo vytváranej ceste je už prvý vrchol
        print('naj =', self.naj)
        for i in range(len(self.najcesta)-1):
            self.zafarbi_hranu(self.najcesta[i], self.najcesta[i+1], 'blue')

    def backtracking(self, v1, v2, hodnota, cesta):
        if v1 == v2:
            if self.naj is None or self.naj > hodnota:
                self.naj = hodnota
                self.najcesta = cesta
        else:
            for v in self.vrcholy[v1].sus:
                if v not in cesta:                # kontrolujeme cestu namiesto visited
                    self.backtracking(v, v2, hodnota + self.vrcholy[v1].sus[v], cesta + [v])

Hľadanie cyklov v grafe

Backtracking môžeme využiť aj na generovanie všetkých cyklov, t.j. takých ciest, v ktorých je posledný vrchol ten istý ako prvý. Využijeme poslednú verziu backtrackingu, v ktorej sme pridali parameter cesta. Pritom zmien v programe pre hľadanie cyklu (hľadáme cyklus s maximálnou hodnotou) je veľmi málo:

class Graf:
    ...

    def udalost_klik(self, event):
        for i in range(len(self.vrcholy)):
            x, y = self.vrcholy[i].xy
            if (x-event.x)**2 + (y-event.y)**2 < 15**2:
                self.vrcholy[i].zafarbi('blue')
                self.start(i)
                return

    def start(self, v1):                      # metóda má iba jeden parameter
        self.naj = None
        self.najcesta = []
        self.backtracking(v1, v1, 0, [])      # backtracking štartujeme s prázdnou cestou
        print('naj =', self.naj)
        for i in range(len(self.najcesta)-1):
            self.zafarbi_hranu(self.najcesta[i], self.najcesta[i+1], 'blue')

    def backtracking(self, v1, v2, hodnota, cesta):
        if cesta != [] and v1 == v2:
            if len(cesta) > 2 and (self.naj is None or self.naj < hodnota):   # hľadáhame maximum
                self.naj = hodnota
                self.najcesta = [v2] + cesta    # k nájdenému riešeniu pridáme na začiatok štartový vrchol
        else:
            for v in self.vrcholy[v1].sus:
                if v not in cesta:
                    self.backtracking(v, v2, hodnota + self.vrcholy[v1].sus[v], cesta + [v])

Zmenili sme:

  • zjednodušili sme metódu udalost_klik(), lebo nepotrebujeme ukladať viac kliknutých vrcholov a metódu start() voláme len s jedným parametrom: začiatkom cyklu, čo je zároveň aj koncom cyklu

  • v metóde start() sme zmenili naštartovanie backtrackingu: posielame ako začiatok aj koniec cesty ten istý vrchol a tiež prvý vrchol nevkladáme do vytváranej cesty (parameter cesta), aby sme ho tam mohli vložiť aj druhýkrát

  • úvodný test v metóde backtracking() kontroluje nielen to, či sme už v cieli (teda v1 == v2), ale aj dĺžku vytvoreného cyklu, ktorá by mala mať aspoň 2 rôzne hrany, t.j. aspoň 3 vrcholy

  • v metóde backtracking(), keď nájdeme nejaké vyhovujúce riešenie, ktoré je lepšie ako doteraz nájdené najlepšie (v atribúte self.najcesta), pridáme k nemu na začiatok štartový vrchol, lebo ten sme úmyselne do cesty nezaradili

Malým zjednodušením tohto riešenie vieme hľadať najdlhší (alebo aj najkratší) cyklus na počet prejdených vrcholov a to bez ohľadu na hodnoty na hranách:

class Graf:
    ...

    def start(self, v1):
        self.najcesta = []
        self.backtracking(v1, v1, [])
        if self.najcesta == []:
            print('nenasiel ziadnu cestu')
        for i in range(len(self.najcesta)-1):
            self.zafarbi_hranu(self.najcesta[i], self.najcesta[i+1], 'blue')

    def backtracking(self, v1, v2, cesta):
        if cesta != [] and v1 == v2:
           if len(cesta) > 2 and len(self.najcesta) < len(cesta):
                self.najcesta = [v2] + cesta
        else:
            for v in self.vrcholy[v1].sus:
                if v not in cesta:
                    self.backtracking(v, v2, cesta + [v])

V prípade, že takýto cyklus prejde cez všetky vrcholy, hovoríme mu Hamiltonovská kružnica (v skutočnosti je Hamiltonovská kružnica podgrafom, ktorý obsahuje všetky vrcholy grafu a len hrany, ktoré sú z tohto cyklu).



Cvičenia

L.I.S.T.


  1. Spojazdni triedu Graf z prednášky - verziu, ktorá nájde a vyznačí najkratšiu cestu medzi dvoma kliknutými vrcholmi.

    • metóda backtracking() má parametre hodnota a cesta:

      class Graf:
          ...
      
          def backtracking(self, v1, v2, hodnota, cesta):
              ...
      

  1. Do triedy Graf dopíš generovanie náhodných hodnôt na hranách grafu z intervalu <1, 4>, túto hodnotu vypíš do stredu príslušnej hrany

    • uprav tieto metódy:

      class Graf:
          ...
      
          def __init__(self, n):
              ...
      
          def kresli_hranu(self, i, j, farba='gray'):
              ...
      
    • otestuj, ako teraz funguje hľadanie najkratšej cesty


  1. Oprav metódu udalost_klik() tak, aby po nájdení a vykreslení cesty ďalšie kliknutie odfarbilo dovtedy vybraté dva vrcholy aj vyznačenú cestu a znovu začalo výber štartového a cieľového vrcholu.

    • dopíšte do metódy odfarbovanie:

      class Graf:
          ...
      
          def udalost_klik(self, event):
              ...
      
    • otestuj opakované hľadanie minimálnej cesty


  1. Do náhodného generovania hrán grafu v inicializácii __init__() pridaj generovanie aj šikmých hrán

    • s nejakou pravdepodobnosťou spojí momentálny vrchol v1 s vrcholom, ktorý je o riadok aj o stĺpec o 1 menší (zrejme to nerobí v prvom riadku ani stĺpci):

      class Graf:
          ...
      
          def __init__(self, n):
              ...
      
    • otestuj, ako teraz funguje hľadanie najkratšej cesty


  1. Uprav backtracking tak, aby hľadal a vyznačil nie minimálnu, ale maximálnu cestu

    • upravte:

      class Graf:
          ...
      
          def backtracking(self, v1, v2, hodnota, cesta):
              ...
      

  1. Uprav backtracking tak, aby hľadal a vyznačil maximálne dlhú cestu (na počet prejdených vrcholov), ale ak je takých viac vyberie tú z nich, ktorá má minimálny súčet váh

    • upravte:

      class Graf:
          ...
      
          def backtracking(self, v1, v2, hodnota, cesta):
              ...
      

  1. Zmeň metódu backtracking() tak, aby po druhom kliknutí na nejaký vrchol našla najkratší (resp. najdlhší) cyklus, ktorý začína (a teda aj končí) vo vrchole v1 a prechádza cez druhý kliknutý vrchol

    • upravte:

      class Graf:
          ...
      
          def start(self, v1, v2):
              ...
              self.backtracking(v1, v1, v2, 0, [])
              ...
      
          def backtracking(self, v1, v2, v3, hodnota, cesta):   # v3 je vrchol, cez ktorý prechádza cyklus
              ...
      
    • backtracking generuje všetky cykly z v1 (do v2) a pre každý ešte skontroluje, či prechádza cez v3


  1. Napíš metódu zisti5(), ktorá pomocou backtrackingu zistí, koľko existuje v danom grafe rôznych cyklov dĺžky presne 5 (zaujíma nás, že počet vrcholov v ceste je 5 a nie aké sú váhy na hranách)

    • zrejme v pôvodnom grafe, v ktorom boli hrany náhodne generované len vodorovne a zvislo, nemôže existovať žiaden cyklus dĺžky 5

    • metóda na záver vypíše tento zistený počet:

      class Graf:
          ...
          def zisti5(self):
              ...
      
      graf = Graf(7)
      graf.zisti5()
      

  1. Pre danú konštantu D a kliknutím na jeden vrchol zafarbi (napr. žltou farbou) všetky také vrcholy, pre ktoré existuje cesta štartujúca zo zadaného (kliknutého) vrcholu a jej hodnota (súčet váh na hranách) je presne D

    • upravte metódy:

      D = 10
      
      class Graf:
          ...
      
          def udalost_klik(self, event):
              ...
      
          def start(self, v1):
              ...
      
          def backtracking(self, ...):
              ...
              self.vrcholy[v1].zafarbi('yellow')
              self.canvas.update()
              ...
      

  1. Zmeň metódu backtracking() tak, aby hľadaná najdlhšia cesta mohla prechádzať cez tie isté vrcholy aj viackrát, len treba strážiť, aby nešla viackrát po tej istej hrane

    • upravte metódy:

      class Graf:
          ...
      
          def start(self, v1, v2):
              ...
      
          def backtracking(self, v1, v2, ...):
              ...
      

  1. Ohodnotený neorientovaný graf je definovaný takto:

    • v každom riadku je popísaná jedna hrana pomocou dvoch čísel vrcholov a váhy (reťazec), napr.:

      1 2 a
      1 4 ma
      1 5 a
      3 4 m
      4 2 am
      6 4 a
      5 6 u
      5 3 am
      4 5 em
      
    • zisti, koľko existuje rôznych ciest (cez vrcholy aj hrany môžeme prechádzať ľubovoľný počet krát), ktorých hodnota je reťazec 'mamamaemuaemamamamu'

    • úlohu rieš prečítaním grafu zo súboru a potom pomocou backtrackingu

    • program vypíše všetky cesty ako postupnosti navštívených vrcholov:

      class Graf:
          def __init__(self, meno_suboru):
              ...
      
          def start(self, retazec):
              ...
      
          def backtracking(self, ...):
              ...
      
      graf = Graf('subor.txt')
      graf.start('mamamaemuaemamamamu')
      


12. Domáce zadanie

L.I.S.T.

Zadanie skúšky 3.6.2016: Labyrint

Labyrint je štvorcová sieť veľkosti m x n a dozvieme sa, medzi ktorými políčkami siete sú steny, teda sa tadiaľ nebude dať prechádzať. Na niektorých políčkach sa nachádzajú odmeny (napr. mince). Úlohou je nájsť ľubovoľnú (stačí jednu) trasu zo štartového políčka, ktorá pozbiera všetky odmeny. Treba dať pozor, aby sa na žiadne políčko nestúpilo 2-krát.

Labyrint reprezentujte ako graf, v ktorom sú políčka labyrintu vrcholy grafu a hrany sú priechody medzi políčkami. Uvedomte si, že každý vrchol môže mať maximálne štyroch susedov (nemusí mať žiadneho).

Súbor má tvar:

  • prvý riadok obsahuje dve čísla: počet riadkov a počet stĺpcov labyrintu

  • ďalej nasledujú riadky so stenami a odmenami (v ľubovoľnom poradí)

  • ak riadok obsahuje iba 2 čísla, označuje to políčko s odmenou (riadok, stĺpec), riadky aj stĺpce číslujeme o 0

  • inak riadok obsahuje postupnosť aspoň dvoch políčok (riadok1, stĺpec1, riadok2, stĺpec2, …) - touto postupnosťou definuje nejaké steny v labyrinte: stena je medzi prvým a druhým políčkom, aj druhým a tretím, … atď.

Zadefinujte triedu Labyrint:

class Labyrint:
    class Vrchol:
        def __init__(self, riadok, stlpec):
            self.sus = []      # zoznam susedov, susedia sú typu Vrchol
            self.poloha = riadok, stlpec
            self.odmena = False

        def __repr__(self):
            return '<{},{}>'.format(*self.poloha)

    def __init__(self, meno_suboru):
        self.g = ...           # zoznam vrcholov grafu – obsahuje objekty typu Vrchol
        ...

    def daj_vrchol(self, riadok, stlpec):
        return ...

    def zmen_odmeny(self, *post):
        ...

    def start(self, riadok, stlpec):
        return ...

kde

  • vnorená definícia triedy Vrchol má už zadefinované nejaké metódy aj atribúty – tieto atribúty využite pre reprezentáciu grafu; atribút sus bude obyčajný zoznam (typu list), ktorý bude obsahovať zoznam susediacich vrcholov, teda prvkami tohto zoznamu budú opäť objekty typu Vrchol;

  • metóda __init__(meno_suboru): prečíta súbor a vytvorí z neho graf: atribút g bude obsahovať všetky vrcholy grafu, teda objekty typu Vrchol; pre atribút g si môžete zvoliť buď obyčajný zoznam vrcholov (list), alebo dvojrozmerný zoznam vrcholov (list of list, teda dvojrozmernú tabuľku) alebo asociatívne pole (dict), v ktorom kľúčom je poloha políčka (riadok, stĺpec) a príslušnými hodnotami sú samotné vrcholy;

  • metóda daj_vrchol(riadok, stlpec): vráti referenciu (typ Vrchol) na príslušný vrchol grafu, ktorý reprezentuje zadané políčko;

  • metóda zmen_odmeny(*post): parameter post je postupnosť (list alebo tuple) dvojíc (riadok, stĺpec); metóda zmení na všetkých zadaných políčkach to, či sa na nich nachádza odmena: ak na políčku bola odmena, odstráni ju, inak na políčko umiestni odmenu;

  • metóda start(riadok, stlpec): pomocou backtrackingu hľadá správnu trasu; metóda vráti postupnosť navštívených políčok (zrejme prvé políčko v tejto postupnosti bude zadaný (riadok, stĺpec)); ak trasa, ktorá prejde cez všetky políčka s odmenou sa skonštruovať nedá, metóda vráti prázdny zoznam []; testovač môže zavolať túto metódu viac krát s rôznymi štartovými políčkami.

Napr. pre takéto zadanie labyrintu:

_images/35_1.png
3 3
1 0 1 1
2 2
0 2
1 2 0 2

tento test:

if __name__ == '__main__':
    lab = Labyrint('subor1.txt')
    v = lab.daj_vrchol(1, 0)
    print('vrchol:', v, 'susedia:', v.sus, 'odmena:', v.odmena)
    v = lab.daj_vrchol(0, 2)
    print('vrchol:', v, 'susedia:', v.sus, 'odmena:', v.odmena)
    print(lab.start(0, 0))
    print(lab.start(0, 2))
    lab.zmen_odmeny((2, 2))
    print(lab.start(0, 0))

vypíše:

vrchol: <1,0> susedia: [<0,0>, <2,0>] odmena: False
vrchol: <0,2> susedia: [<0,1>] odmena: True
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (1, 1), (0, 1), (0, 2)]
[(0, 2), (0, 1), (1, 1), (1, 2), (2, 2)]
[(0, 0), (0, 1), (0, 2)]

Prvé z riešení nájde túto trasu:

_images/35_2.png

Obmedzenia

Vaše riešenie odovzdajte v súbore riesenie12.py, pričom prvé tri riadky súboru budú obsahovať:

# 12. zadanie: labyrint
# autor: Janko Hrasko
# datum: 15.5.2019

zrejme ako autora uvediete svoje meno.

Testovač:

  • odkontroluje, či sa vo vašom module nachádzať len jedna definícia triedy Labyrint s vnorenou triedou Vrchol (do existujúcich tried môžete pridávať vlastné atribúty a metódy)

  • bude kontrolovať štruktúru vami vytvoreného grafu (atribút g) s rôznymi textovými súbormi, ktoré si môžete stiahnuť z L.I.S.T.u

  • postupne preveruje vlastnosti vašich algoritmov, pri prvej chybe sa testovanie preruší a ďalšie časti sa netestujú:

    • 50% bodov za vytvorenie grafu

    • 50% bodov za algoritmus hľadania trasy v grafe