Algorisme de backtracking

El backtracking és una tècnica algorísmica per trobar solucions a problemes a base de provar totes les possibilitats de forma sistemàtica.

Introducció

El nom backtrack es sol traduir per tornada enrera. És a dir, intentem explorar totes les combinacions i quan veiem que un determinat camí no pot solucionar el problema, tornem enrera i provem la següent combinació.

Aplicacions típiques del backtracking son els laberints i el Sudoku.

Exemple del laberint

Podem fer una ullada a l'exemple d'aquesta web on surt el típic laberint i on s'expliquen dos algorismes per solucionar-ho: el recursiu (backtrack) i el A* (que ve a ser una optimització).

http://www.laurentluce.com/posts/solving-mazes-using-python-simple-recursivity-and-a-search/

Tens aquí l'enunciat del problema del laberint:

Assumim que tenim un objecte Laberint com s'indica, amb un mètode backtrack (entre d'altres) que retorni la llista de cel·les que ens porten des de l'inici (I) fins el final (F):

class Laberint():
    lab = None # matriu del laberint
    ...
    def backtrack(self,fila,col):
        # cridarem el 1r cop a backtrack amb la fila i col de la cel·la d'inici (I)
        ...

Contingut possible de les cel·les:

• * = mur
• . = buit (es pot passar)
• I = Inici
• F = Final
• v = visitada

Laberint recursiu

L'algorisme RECURSIU que ens ho resol seria aquest.

    # backtrack recursiu
    # retornem
    #   false si no hi ha sortida
    #   la llista de cel·les recorregudes quan arribem al final
    def backtrack(self,fila,col):
        # ens ho posem una mica més fàil per no anar repetint self.lab tota l'estona
        lab = self.lab
        # primer de tot: sortides de la recursió
        if lab[fila][col]=="F":
            # final: engeguem la llista que s'anirà omplint amb el recorregut bo
            return [(fila,col)]
        elif lab[fila][col]=="*":
            # mur, per aquí no podem
            return False
        elif lab[fila][col]=="v":
            # cel·la visitada, passem a la següent
            return False

        # arribats aquí, se suposa que és una cela "I" o "."
        # si no és així, el programa peta
        assert lab[fila][col]=="I" or lab[fila][col]=="." , "cel·la desconeguda"

        if lab[fila][col]==".":
            # marquem com a cel·la visitada
            lab[fila][col] = "v"

        # direccions = dreta, amunt, esq, avall
        direccions = [(0,1),(1,0),(0,-1),(-1,0)]

        # avançem: provem per cadascuna per les diferents direccions
        for d in direccions:
            fila_seg = fila + d[0]
            col_seg = col + d[1]
            # controlem de no sortir del laberint (matriu)
            if fila_seg<0 or fila_seg>=len(lab) or col_seg<0 or col_seg>=len(lab[0]):
                pass
            else:
                # seguim al seguent pas
                cami = self.backtrack(fila_seg,col_seg)
                # hem arribat al final (retorna llista):
                if cami:
                    cami.append( (fila,col) )
                    return cami
        # si arribem aquí és que hem esgotat totes les possibles direccions
        return False

Laberint no recursiu

Tots els algorismes recursius com el vist anteriorment, tenen una implementació alternativa utilitzant una pila (stack).

L'algorisme equivalent a l'anterior en versió no-recursiva podria resoldre's així. Quan trobem el final el camí el tenim enregistrat a la pila.

• Busquem cel·la inici
• Iniciem la pila
• Definim direccions possibles (amunt, esq, avall, dreta, per exemple).
• Afegim cel·la d'inici a la pila, juntament amb la primera direcció que prendrem

  Podem guardar tuples amb 3 elements (fila,columna,direccio)

• Mentre la pila no estigui buida fes:
  1. Mirem el darrer element de la pila (peek)
  2. Si és la cel·la final retornem la pila (conté el camí).
  3. Calculem cel·la següent (en la direcció marcada)
  4. Si la següent està dins els límits, està buida i no l'hem visitat:
     • marquem com a visitada
     • l'afegim a la pila (fila,columna,direccio=0)
  5. Sino:
     • Passem a la següent direcció
     • Si és bona (no hem esgotat les possibles direccions):
       • Mirem següent direccio: pop + push amb la nova direcció
     • Sinó (direccions esgotades):
       • Tronem enrera: Extraiem la cel·la (pop)
• Retornem false (si arribem aquí no hi ha sortida)

Exemple del Sudoku

Per resoldre un Sudoku es pot utiltizar un backtrack, sigui recursiu o amb pila.

Suposem que tenim 2 matrius:

• Matriu del Sudoku (amb els nombres) de 9x9
• Matriu de valors possibles per cada cel·la.

Partim d'un Sudoku generat aleatòriament (entre 20 i 30 nombres que compleixen amb les regles del Sudoku). Aquests nombres son fixes i no es poden canviar. És important tenir en compte que el joc no té perquè tenir solució, encara que els nombres col·locats compleixin d'entrada amb les regles del Sudoku.

Backtrack Sudoku recursiu

funció backtrack(fila,col):

• si és cel·la fixa
  • passa a la següent (return backtrack() <- recursió)
• sino
  1. per tots els valors possibles de la cel·la (de 1 a 9):
     • si compleix regles del Sudoku:
       1. si hem arribat a la darrera cel·la (9,9) retornem TRUE
       2. provem backtrack (recursió) amb la següent cel·la i si torna TRUE, tornem TRUE
       3. sino (backtrack falla) seguim
  2. sino (no ha funcionat amb cap dels valors possibles)
     • esborra la cel·la
     • retorna FALS

Si us funciona comprovareu que triga lo seu.

Hi ha una millora a aquest algorisme que consisteix a no provar tots els valors de 1 a 9, sinó que descartem els què sabem que no hi poden funcionar (mirant fila, columna, quadrant). Accelera la velocitat de l'algorisme bastant.

Backtrack Sudoku amb pila

...proveu vosaltres...