Backtracking

El Backtracking és una estratègia per trobar solucions a problemes que satisfan restriccions. El terme "backtrack" va ser encunyat per primera vegada pel matemàtic nord-americà Derrick Henry Lehmer en la dècada de 1950.

Exemple d'arbre de cerca. L'arbre no necessàriament ha de ser binari.

Enfocaments

Els problemes que han de satisfer un determinat tipus de restriccions són problemes complets, on l'ordre dels elements de la solució no importa. Aquests problemes consisteixen en un conjunt (o llista) de variables on a cadascuna se l'ha d'assignar un valor subjecte a les restriccions del problema. La tècnica va creant totes les possibles combinacions d'elements per obtenir una solució. La seva principal virtut és que en la majoria de les implementacions es pot evitar combinacions, establint funcions d'acotació (o poda) reduint el temps d'execució.

Backtracking està molt relacionat amb la cerca combinatòria.

Disseny i implementació

Essencialment, la idea és trobar-hi la millor combinació possible en un moment determinat, per això, es diu que aquest tipus d'algorisme és una cerca en profunditat. Durant la cerca, si s'hi troba una alternativa incorrecta, la cerca retrocedeix fins al pas anterior i pren la següent alternativa. Quan s'han acabat les possibilitats, s'hi torna a l'elecció anterior i s'hi pren la següent opció (fill [si ens referim a un arbre]). Si no hi ha més alternatives la cerca falla. D'aquesta manera, s'hi crea un arbre implícit, en el qual cada node és un estat de la solució (solució parcial en el cas de nodes interiors o solució total en el cas dels nodes fulla).

Normalment, s'hi sol implementar aquest tipus d'algorismes com un procediment recursiu. Així, en cada trucada al procediment es pren una variable i se li assignen tots els valors possibles, cridant al seu torn al procediment per a cadascun dels nous estats. La diferència amb la cerca en profunditat és que s'hi solen dissenyar funcions de cota, de manera que no es generen alguns estats si no condueixen a cap solució, o a una solució pitjor de la que ja es té. D'aquesta forma s'estalvia espai en memòria i temps d'execució.

Heurístiques

Algunes heurístiques són comunament usades per accelerar el procés. Com que les variables es poden processar en qualsevol ordre, generalment és més eficient intentar ser el més restrictiu possible amb les primeres (això és, les primeres amb menors valors possibles). Aquest procés poda l'arbre de cerca abans que s'hi prenga la decisió i es cride a la subrutina recursiva.

Quan es tria quin valor es va a assignar, moltes implementacions fan un examen cap a davant (FC, Forward Checking), per veure quin valor restringirà el menor nombre possible de valors, de manera que s'anticipa en:

a) Preservar una possible solució.

b) Ta que la solució oposada no tinga restriccions destacades.

Algunes implementacions molt sofisticades usen una funció de cotes, que examina si és possible trobar una solució a partir d'una solució parcial. A més, s'hi comprova si la solució parcial que falla pot incrementar significativament l'eficiència de l'algorisme. Per l'ús d'aquestes funcions de cota, s'ha de ser molt minuciós en la seva implementació de manera que siguen poc costoses computacionalment parlant, ja que el més normal és que s'executen per a cada node o pas de l'algorisme. Cal destacar, que les cotes eficaces s'hi creen de forma semblant a les funcions heurístiques, això és, relaxant les restriccions per aconseguir major eficiència.

Amb l'objectiu de mantenir la solució actual amb cost mínim, els algorismes tornada enrere mantenen el cost de la millor solució en una variable que va variant amb cada nova millor solució oposada. Així, si una solució és pitjor que la que s'acaba de trobar, l'algorisme no actualitzarà la solució. D'aquesta forma, retornarà sempre la millor solució que haja trobat.

Exemples de problemes comuns resolts usant Backtracking

• Sudoku
• Problema dels moviments d'un cavall
• Les vuit reines

Backtracking s'usa en la implementació dels llenguatges de programació tals com a Llenguatge de programació Planner i Prolog. A més, s'usa en les anàlisis sintàctiques dels compiladors. El seu ús en intel·ligència artificial ha estat molt important, donant lloc a nous tipus de cerques com l'A estrella.

Branch & Bound (Ramificació i poda)

Aquest mètode busca una solució com en el mètode de backtracking, però cada solució té associat un cost i la solució que s'hi busca és una de mínim cost anomenada òptima. A més de ramificar una solució pare (branch) en fills es tracta d'eliminar de la consideració aquells fills que on seus descendents tenen un cost que supera a l'òptim buscat fitant el cost dels descendents del fill (bound). La forma de fitar és un art que depèn de cada problema. L'acotació redueix el temps de cerca de la solució òptima en podar (pruning) els subarbres de descendents costosos.