Page 136 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Retorno sobre la misma ruta (backtracking)

INtroduccIóN

En la búsqueda de los principios fundamentales del diseño de algoritmos, backtracking representa
una de las técnicas más generales. Varios problemas que tratan la búsqueda de un conjunto de solu-
ciones o intentan hallar una solución óptima satisfaciendo algunas restricciones pueden ser resueltos
empleando backtracking.

Para utilizar este método, el problema debe de estar expresado en n tuplas (x , x , x ,…, x ), donde
1 2 3 n
x se escoge desde un conjunto finito S. A veces el problema que se quiere resolver es maximizar o
i i
minimizar una función P (x , x , x ,…, x ). A veces se buscan todos los vectores que satisfacen
1 2 3 n
a P. Por ejemplo, ordenar los enteros localizados en A (1: n) es un problema cuya solución se ex-
presa por n tuplas, donde x es el índice de A, donde se localiza el i-ésimo elemento más pequeño.
i
La función P es la desigualdad A(x) ≤ A(x ) para 1≤ i < n. La ordenación de números no es en sí un
i i+1
ejemplo de backtracking, solo es una muestra de un problema cuya solución se puede formular por
medio de n tuplas. En esta sección se estudiarán algunos algoritmos cuya solución se realiza mejor
con backtracking.

Suponga que m es el tamaño del conjunto S. Entonces existen m = m , m …, m tuplas cuyos po-
i i 1 2, n
sibles candidatos pueden satisfacer la función P. el enfoque de la “fuerza bruta” formaría todas las n
tuplas y evaluaría a cada una con P, salvando a los que producen el óptimo. La virtud de backtracking
es la habilidad para producir la misma respuesta con un menor número de pasos. Su idea básica es
construir un vector y evaluarlo con la función P (x , x , x ,..., x ) para probar si el vector recién formado
1 2 3 n
tiene una oportunidad de ser el óptimo. La gran ventaja de este método es la siguiente: si se observa
que el vector parcial (x , x , x ,..., x ) no tiene la posibilidad de conducir hacia una posible solución
1 2 3 n
óptima, entonces m ,..., m puede ser ignorado completamente.
1+1 n
Varios de los problemas que se resuelven utilizando backtracking requieren que todas las soluciones
satisfagan a un complejo conjunto de restricciones. Estas restricciones pueden ser divididas en dos
categorías: explícitas e implícitas. Las primeras son reglas cuyas restricciones de cada x toman va-
i
lores para un conjunto determinado. Un ejemplo de restricciones explícitas es:

x > 0 o S = {todos los números reales son no negativos}
i i
x =0 o 1 o S = {0, 1}
i i
l < x < u o S = {a: l < a < u}
i i i i i i

130