Taula de continguts:
Definició: què significa Backtracking?
El backtracking és un algorisme per capturar algunes o totes les solucions a problemes computacionals donats, especialment per als problemes de satisfacció de restriccions. L’algoritme només es pot utilitzar per a problemes que puguin acceptar el concepte de “solució parcial del candidat” i permet fer una prova ràpida per veure si la solució candidata pot ser una solució completa. El backtracking es considera una tècnica important per resoldre problemes de satisfacció de restriccions i trencaclosques. També es considera una gran tècnica per analitzar i també forma la base de molts llenguatges de programació lògics.
Techopedia explica Backtracking
El retrocés ajuda a resoldre un problema global mitjançant la cerca d’una solució al primer sub-problema i, després, intentant de manera recursiva resoldre altres sub-problemes basats en la solució del primer problema. Si el problema actual no es pot resoldre, el pas es retrocedeix i la següent solució possible s'aplica als passos anteriors, i continua més endavant. De fet, una de les coses més importants en el backtracking és la recursivitat. També es considera com un mètode de cerca exhaustiva mitjançant dividi i conquesta. Un algorisme de retrocés s’acaba quan ja no hi ha més solucions al primer sub-problema.
El backtracking és un algorisme que pot ajudar a aconseguir la implementació del no determinisme. Es necessita una cerca en profunditat d'un espai de problema determinat. S'utilitza principalment en llenguatges de programació lògica com Prolog. En qualsevol cas que es pugui aplicar el backtracking, és més ràpid que la tècnica de la força bruta, ja que elimina un gran nombre de candidats amb una única prova.
