2. Inicio
  3. Artículos
  4. Ingeniería en Computación
  5. Análisis de algoritmos
  6. Backtracking

Backtracking

Análisis de algoritmos Hits: 1453

Backtracking (en español vuelta atrás) es una técnica para encontrar solución esos problemas que tienen que satisfacer ciertas restricciones. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense Derrick Henry Lehmer en la década de 1950.El backtracking gradualmente construye tareas básicas y las inspecciona para determinar si conducen a la solución del problema. Si una tarea no conduce a la solución, retrocede a la tarea original y se prueba otra cosa distinta. Es una prueba sistemática hasta llegar a la solución, o bien determinar que no hay solución por haberse agotado todas las opciones que probar (espacio de búsqueda).

Palabras claves

  • Algoritmo: Conjunto ordenado de operaciones sistemáticas que permite hacer un cálculo y hallar la solución de un tipo de problemas.
  • Fuerza bruta: se generan todos los casos posibles y se testean uno a uno hasta encontrar las soluciones necesarias, a veces basta con encontrar una, en otras ocasiones hay que encontrar todas ellas, o quedarse con la mejor.
  • Retroceso: Método empleado por los algoritmos de búsqueda que ante la posibilidad de cierre de un camino retroceden a un nivel superior para continuar por otro camino. Es equivalente a la búsqueda sistemática en una estructura arborescente.

BACKTRACKING

Cuando un problema no tiene un método algorítmico para resolverse, en general la única forma posible de resolverlo es la búsqueda exhaustiva de soluciones entre todas las posibilidades del problema; este método se conoce como fuerza bruta. Sin embargo, en muchos de estos problemas no es necesario crear completamente un caso para ver si es una solución o no. Cuando resolver un problema puede hacerse por etapas se puede comprobar paso a paso si se está creando una solución o si se han tomado decisiones que no conseguirán resolver el problema: en cada etapa se estudian las propiedades cuya validez ha de examinarse con objeto de seleccionar las adecuadas para proseguir con el siguiente paso.

Definición

Es una técnica usada para resolver problemas que involucran un gran espacio de

búsqueda. La idea es, sistemáticamente, ir explorando y eliminando posibilidades.

Existen tres tipos de problemas a resolver utilizando la técnica de Backtracking:

  • Búsqueda de una solución
  • Búsqueda de todas las soluciones
  • Búsqueda de la solución óptima

Figura 1: Proceso de Backtracking

CÓMO FUNCIONA BACKTRACKING

En su forma básica Backtracking se asemeja a un recorrido en profundidad del árbol de expansión; se recorre en preorden: primero se evalúa el nodo raíz o actual, y después todos sus hijos de izquierda a derecha. Por tanto, hasta que no se termina de generar una solución parcial (sea válida o no) no se evalúa otra solución distinta.

Supondremos que una solución se puede modelar como un vector a = (a1, a2, . . . , an), donde cada elemento a esta tomado de un conjunto ordenado finito Si .

  • Representamos a una solución candidata como un vector a = (a1, . . . , ak).
  • Las soluciones candidatas se extenderán agregando un elemento al final.

Figura 2: Ejemplo de la implementación de backtracking para solucionarlo.

Características

  • Es un esquema recursivo.
  • Cada llamada recursiva abre nuevas opciones para chequear (opciones que hay
  • que generar y pueden no ser siempre la misma cantidad).
  • Mientras queden opciones para verificar, se continúa probando.
  • Cuando todas las opciones fueron negativas, se devuelve que este camino no anduvo.
  • La profundidad de llamadas recursivas depende del problema y del espacio de búsqueda a recorrer

 

PROBLEMAS EN LA REALIZACIÓN DE BACKTRACKING

Al tener una gran carga de recursión y debido al alto paso de parámetros entre las llamadas,

hay que tener en cuenta una serie de consideraciones:

  • El paso de parámetros únicamente como datos de entrada consume memoria y tiempo, ya que realizan copias locales para cada uno de los entornos. Puede evitarse con el uso de parámetros por referencia, pero hay que tener cuidado con las modificaciones ya que afectarán en todos los niveles.

Figura 3: La resolución del problema de 8 reinas requiere muchos recursos

  • Como el espacio de búsqueda es implícito, puede que se tengan que rehacer nodos que ya fueron resueltos, y que obviamente habrá que recalcular. Una forma de evitar esta situación (aunque depende del problema a resolver) es generar las decisiones de manera secuencial y evitar reordenaciones (en determinados problemas tomar la decisión 1 y luego la decisión 2 puede ser equivalente a tomar primero la decisión 2 y después la decisión 1). Si es posible, suele incorporarse a la llamada recursiva un parámetro para indicar el rango de decisiones válidas.

Bibliografía

No comments

Comentarios en artículos

No comments

Nobody has submitted a comment yet.

Gestión de usuarios