Diferència entre revisions de la pàgina «Algorisme de backtracking»

De Cacauet Wiki
Salta a la navegació Salta a la cerca
(Es crea la pàgina amb «El ''backtracking és una tècnica algorísmica per trobar solucions a problemes a base de provar totes les possibles solucions. Aplicacions típiques del ''backtracking…».)
 
Línia 23: Línia 23:
 
     #  false si no hi ha sortida
 
     #  false si no hi ha sortida
 
     #  la llista de cel·les recorregudes quan arribem al final
 
     #  la llista de cel·les recorregudes quan arribem al final
     def backtrack(lab,fila,col):
+
     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: si no anem bé, tornem False
 
         if lab[fila][col]=="F":
 
         if lab[fila][col]=="F":
 
             # final: engeguem la llista que s'anirà omplint amb el recorregut bo
 
             # final: engeguem la llista que s'anirà omplint amb el recorregut bo
Línia 34: Línia 37:
 
             return False
 
             return False
  
         # se suposa que és una cela "I" o ".""
+
         # 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"
 
         assert lab[fila][col]=="I" or lab[fila][col]=="." , "cel·la desconeguda"
  

Revisió del 14:05, 21 nov 2013

El backtracking és una tècnica algorísmica per trobar solucions a problemes a base de provar totes les possibles solucions.

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/

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):
        ...

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: si no anem bé, tornem False
        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 = backtrack(lab,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


Exemple del Sudoku

...ja arribarà...