Backtracking Algorithm

¿Qué es y para qué sirven los algoritmos Backtracking o Retroceso?*

Written by Nicolas Felipe Cardozo Achury on .
Tiempo estimado lectura: 13 minutos

Descubre cómo el backtracking resuelve problemas complejos, desde el n-Queens hasta la Suma de Subconjuntos. Aplicaciones prácticas en la vida real.

¿A qué hace referencia Backtracking cuando se habla de algoritmos?

El backtracking, o retroceso, es un enfoque utilizado en algoritmos para resolver problemas computacionales, especialmente aquellos relacionados con la búsqueda y exploración de soluciones en espacios de estados complejos. Este enfoque se utiliza comúnmente en problemas de optimización, combinación y permutación, así como en la resolución de problemas de decisión.

En el contexto de los algoritmos, el backtracking implica explorar sistemáticamente todas las posibles soluciones de un problema mediante una búsqueda en profundidad, y retroceder (o hacer "backtrack") cuando se determina que la solución actual no puede llevar a una solución completa y válida.

El proceso general del backtracking incluye:

  1. Elección de una opción: Se elige una opción válida para avanzar en la solución del problema.

  2. Exploración: Se explora más profundamente la opción elegida, y se repite el proceso.

  3. Rechazo: Si se determina que la opción elegida no puede conducir a una solución válida, se retrocede (backtrack) al estado anterior y se elige otra opción.

  4. Éxito: Si se encuentra una solución completa y válida, se la registra o se maneja según los requisitos del problema.

Este enfoque es útil en problemas en los que se pueden tomar decisiones en una secuencia, y se quiere encontrar todas las soluciones posibles o una solución específica. Algunos problemas típicos que pueden resolverse eficientemente con el backtracking incluyen el problema de las N reinas, el problema del viajante (Traveling Salesman Problem), y muchos otros problemas de búsqueda y optimización combinatoria. 

Hamiltonean Cycles algorithm o Algoritmo Ciclo Hamiltoneano

Un ciclo hamiltoniano es un concepto en teoría de grafos que se refiere a un ciclo que visita cada vértice de un grafo exactamente una vez y vuelve al vértice de origen. En el contexto del backtracking, resolver el problema del ciclo hamiltoniano implica encontrar un ciclo hamiltoniano en un grafo dado.

El problema específico del ciclo hamiltoniano es un caso particular dentro de los problemas de optimización combinatoria y es un problema conocido como NP-completo. En el contexto del backtracking, la idea es utilizar una búsqueda exhaustiva para explorar todas las posibles permutaciones de vértices y verificar si alguna de ellas forma un ciclo hamiltoniano válido.

El algoritmo de backtracking para el problema del ciclo hamiltoniano puede seguir estos pasos generales:

  1. Comenzar desde un vértice arbitrario como vértice de inicio.
  2. Explorar todas las posibles aristas que pueden ser añadidas al ciclo, eligiendo vértices no visitados.
  3. Marcar el vértice como visitado y agregarlo al ciclo.
  4. Si se llega a un punto donde no es posible agregar más vértices al ciclo, retroceder (backtrack) al vértice anterior y explorar otras opciones.
  5. Continuar este proceso hasta encontrar un ciclo hamiltoniano o explorar todas las posibles permutaciones sin éxito.

Este proceso de backtracking busca sistemáticamente a través de todas las posibles soluciones, evitando la repetición y retrocediendo cuando se alcanza un punto sin salida.

El problema del ciclo hamiltoniano es un ejemplo clásico de aplicación de backtracking en la resolución de problemas de optimización combinatoria en teoría de grafos.

Para ver cómo funciona el Hamiltonean Cycles algorithm puedes visitar Algorithm Visualizer.

3 ejemplos de la vida real donde se podría usar el Hamiltonean Cycles algorithm

  1. Ruta de entrega para un mensajero:

    • Supongamos que un mensajero tiene que entregar paquetes en diferentes ubicaciones de una ciudad. El problema de encontrar un ciclo hamiltoniano puede ser aplicado para determinar la ruta más eficiente que visita cada dirección exactamente una vez y regresa al punto de partida. Esto ayuda a minimizar la distancia recorrida y optimizar la entrega de paquetes.

  2. Secuenciación de operaciones en manufactura:

    • En un entorno de fabricación, donde hay varias estaciones de trabajo y cada pieza debe pasar por todas las estaciones en un orden específico, el problema del ciclo hamiltoniano podría utilizarse para determinar la secuencia más eficiente. Esto garantiza que cada estación sea visitada una vez y que la producción se realice de manera óptima.

  3. Planificación de recorrido en un robot móvil:

    • En robótica móvil, especialmente en aplicaciones como la limpieza o inspección de áreas grandes, un robot puede beneficiarse de la planificación de un ciclo hamiltoniano para cubrir toda el área de manera eficiente. El robot puede visitar cada punto de la región exactamente una vez y regresar al punto de inicio, minimizando el tiempo y la energía utilizados.

Estos son solo ejemplos representativos, pero el problema del ciclo hamiltoniano puede ser aplicado en diversas situaciones donde se requiera visitar ubicaciones o realizar operaciones de manera secuencial y eficiente. La versatilidad del concepto lo hace aplicable en diferentes contextos de la vida real donde se busque optimizar el recorrido o la secuencia de eventos. 

Knight's Tour Problem o problema del recorrido del caballo

El problema del "Knight's Tour" (Recorrido del Caballo) es un problema clásico en el ámbito del ajedrez y también se utiliza como un ejemplo común en el contexto de backtracking y algoritmos de búsqueda. El objetivo es encontrar un recorrido para el caballo en un tablero de ajedrez de tamaño N×N de tal manera que el caballo visite cada casilla exactamente una vez.

Las reglas de movimiento del caballo en el ajedrez son específicas: el caballo se mueve en forma de "L", avanzando dos casillas en una dirección (horizontal o vertical) y luego una casilla perpendicular a la dirección anterior. El problema del Knight's Tour implica encontrar un recorrido válido para el caballo que cubra todo el tablero sin repetir ninguna casilla.

La aplicación del backtracking en el problema del Knight's Tour implica explorar de manera recursiva todas las posibles secuencias de movimientos del caballo, retrocediendo cuando se llega a un punto sin salida. Aquí hay una descripción general de cómo se puede abordar este problema mediante backtracking:

  1. Elección de movimiento:

    • Se elige una posición inicial en el tablero y se realiza el primer movimiento del caballo.

  2. Exploración:

    • Se exploran de manera recursiva todas las posibles secuencias de movimientos del caballo, eligiendo las opciones disponibles en cada paso.

  3. Rechazo (Backtracking):

    • Si se llega a una posición donde no hay movimientos posibles sin repetir casillas o se completa el recorrido, se retrocede (backtrack) al paso anterior y se elige una opción diferente.

  4. Éxito:

    • Si se encuentra un recorrido que cubre todas las casillas del tablero, se considera exitoso y se puede informar o manejar según los requisitos del problema.

El problema del Knight's Tour es un ejemplo interesante para ilustrar cómo el backtracking puede utilizarse para encontrar soluciones a problemas que implican la exploración de opciones en un espacio de estados complejo.

Para ver cómo funciona el Knight's Tour Problem puedes visitar Algorithm Visualizer.

 3 ejemplos de la vida real donde se podría usar el Knight's Tour Problem

Aunque el problema del Knight's Tour puede no tener aplicaciones directas y prácticas en la mayoría de los casos del mundo real, su naturaleza combinatoria y la idea de encontrar un recorrido específico pueden inspirar soluciones para problemas que involucran optimización y secuenciación. Aquí hay tres ejemplos de situaciones en la vida real donde la analogía del Knight's Tour podría ser relevante:

  1. Recorrido Eficiente en un Almacén:

    • En un almacén con estanterías y pasillos, un robot móvil que realiza tareas de recolección puede beneficiarse de la planificación de un recorrido eficiente. El problema del Knight's Tour podría inspirar algoritmos para determinar una secuencia óptima de pasillos y estanterías a visitar, minimizando la distancia total recorrida y optimizando el tiempo de recolección.

  2. Planificación de Rutas para la Distribución de Productos:

    • En la distribución de productos a través de una red de almacenes o puntos de entrega, la planificación de rutas para los vehículos de distribución puede ser un desafío logístico. La analogía del Knight's Tour podría aplicarse para determinar la secuencia más eficiente de entregas, asegurando que cada ubicación se visite exactamente una vez y minimizando la distancia total recorrida.

  3. Secuenciación de Procesos en una Cadena de Producción:

    • En una cadena de producción, especialmente en entornos donde se ensamblan productos complejos o se realizan diversas operaciones en una línea de producción, la planificación de la secuencia de procesos puede ser crucial. El problema del Knight's Tour podría inspirar enfoques para optimizar la secuenciación de tareas, garantizando que cada estación de trabajo se visite en el orden adecuado y minimizando el tiempo total de producción.

Estos ejemplos ilustran cómo la idea de encontrar un recorrido específico puede ser adaptada y aplicada de manera más general en situaciones prácticas que involucren la optimización de trayectorias o secuencias.

n-Queens Problem algorithm o problema n-Reinas

El problema de las N reinas (n-Queens problem) es otro problema clásico en la teoría de algoritmos y, específicamente, en el contexto del backtracking. El objetivo del problema es colocar N reinas en un tablero de ajedrez N×N de tal manera que ninguna reina amenace a otra. En otras palabras, ninguna reina debería estar en la misma fila, columna o diagonal que otra reina.

La formulación del problema es encontrar todas las posibles configuraciones de reinas que cumplan con estas restricciones. El enfoque de backtracking es comúnmente utilizado para resolver el problema de las N reinas debido a su naturaleza recursiva y la capacidad de explorar sistemáticamente todas las opciones posibles.

A continuación, se describe de manera general cómo se puede abordar el problema de las N reinas mediante backtracking:

  1. Elección de posición:

    • Se elige una fila y se intenta colocar una reina en cada columna de esa fila.

  2. Validación:

    • Se verifica si la posición actual es válida, es decir, si la reina colocada no amenaza a ninguna otra reina en la misma fila, columna o diagonal.

  3. Exploración:

    • Si la posición es válida, se procede a la siguiente fila y se repite el proceso recursivamente. Si no es válida, se retrocede (backtrack) y se intenta colocar la reina en otra columna de la misma fila.

  4. Éxito:

    • Cuando se ha colocado una reina en cada fila y se cumple con todas las restricciones, se ha encontrado una solución válida.

  5. Backtrack:

    • Si se llega a una situación sin salida en la que no es posible colocar una reina en la posición actual sin violar las restricciones, se retrocede al estado anterior y se intentan otras opciones.

El backtracking continúa explorando todas las posibles combinaciones de colocación de reinas hasta encontrar todas las soluciones válidas o hasta que se hayan explorado todas las opciones.

El problema de las N reinas es un ejemplo clásico que destaca la eficacia del backtracking en la resolución de problemas combinatorios y de búsqueda en espacios de estados complejos.

Para ver cómo funciona el n-Queen Problem puedes visitar Algorithm Visualizer.

3 ejemplos de la vida real donde se podría usar el n-Queens Problem

Aunque el problema de las n-reinas (n-Queens) no tiene aplicaciones directas en la mayoría de los casos del mundo real, su enfoque de abordar restricciones y colocar objetos en posiciones específicas puede inspirar soluciones para problemas más prácticos. Aquí tienes tres ejemplos donde la analogía del n-Queens problem podría ser relevante:

  1. Diseño de Espacios en Oficinas o Hogares:

    • En el diseño de interiores de oficinas o hogares, se podría abordar un problema similar al n-Queens al posicionar elementos como escritorios, sillas, o muebles en un espacio limitado. Las restricciones serían garantizar que ningún elemento esté en la misma "fila" (por ejemplo, en una misma fila de escritorios) o en la misma "columna" (por ejemplo, alineación en una pared) para optimizar el uso del espacio y facilitar la circulación.

  2. Programación de Turnos en un Hospital:

    • En la programación de turnos para personal médico en un hospital, el problema de las N reinas podría ser relevante al asignar turnos a diferentes profesionales de manera que no haya conflictos de horarios. Las "reinas" representarían los turnos asignados, y las restricciones se aplicarían para evitar que dos profesionales estén programados para trabajar al mismo tiempo o en el mismo departamento.

  3. Planificación de Despliegue de Antenas en Redes de Comunicación:

    • En la planificación de despliegue de antenas para mejorar la cobertura de redes de comunicación, el problema de las N reinas podría influir en la ubicación óptima de antenas para evitar interferencias. Las antenas podrían considerarse como "reinas", y se aplicarían restricciones para garantizar que no haya interferencias en la misma "fila", "columna" o "diagonal" (áreas con solapamiento de cobertura).

Estos ejemplos ilustran cómo la esencia del problema de las N reinas, que implica la colocación de objetos o elementos sujetos a restricciones específicas, puede inspirar enfoques para resolver problemas prácticos en diversas áreas.

Sum of Subset o Suma de Subconjuntos

La Sum of Subsets (Suma de Subconjuntos) es un problema de optimización que se puede abordar utilizando la técnica de backtracking. En este problema, se busca encontrar todos los subconjuntos de un conjunto dado cuya suma sea igual a un valor objetivo específico. La idea principal es explorar sistemáticamente todas las posibles combinaciones de elementos en el conjunto para determinar qué subconjuntos cumplen con el criterio de la suma deseada.

A continuación, se describen los pasos generales de cómo se puede abordar el problema de Suma de Subconjuntos mediante backtracking:

  1. Elección de Elementos:

    • Se elige un elemento del conjunto y se decide si incluirlo o no en el subconjunto actual.

  2. Exploración:

    • Se explora de manera recursiva dos ramas del árbol de decisiones: una rama incluyendo el elemento actual en el subconjunto y otra rama excluyéndolo.

  3. Validación:

    • Se verifica si la suma del subconjunto actual es igual al objetivo deseado.

  4. Éxito:

    • Si la suma es igual al objetivo, se ha encontrado un subconjunto válido y se puede registrar o manejar según los requisitos del problema.

  5. Backtrack:

    • Si la suma es mayor que el objetivo o si no hay más elementos para considerar, se retrocede (backtrack) al estado anterior y se continúa la exploración.

El algoritmo de backtracking continúa explorando todas las posibles combinaciones de elementos, tomando decisiones y retrocediendo cuando sea necesario, hasta que se hayan considerado todas las opciones.

El problema de Suma de Subconjuntos es útil en situaciones donde se busca encontrar todas las combinaciones de elementos que sumen un valor específico, como en problemas de asignación de recursos, planificación financiera, o en la resolución de algunos problemas de particionamiento.

Para ver cómo funciona el n-Queen Problem puedes visitar Algorithm Visualizer.

3 ejemplos de la vida real donde se podría usar el Sum of Subset

El Sum of Subset puede tener muchas aplicaciones en la vida real que buscan optimizar los recursos, por ejemplo:

  1. Optimización de Recursos en Producción:

    • En un entorno de fabricación, se podría utilizar el problema de la Suma de Subconjuntos para optimizar la asignación de recursos. Por ejemplo, si hay diferentes máquinas con tiempos de procesamiento y se busca cumplir con la demanda de producción minimizando el tiempo total, el problema de la Suma de Subconjuntos podría ayudar a identificar combinaciones eficientes de máquinas para realizar las tareas.

  2. Planificación de Viajes y Presupuesto:

    • Al planificar un viaje con un presupuesto limitado, se podría aplicar el problema de la Suma de Subconjuntos para determinar todas las combinaciones posibles de actividades, destinos o gastos que se ajusten al presupuesto disponible. Esto podría ayudar en la toma de decisiones para maximizar la experiencia del viaje dentro de las limitaciones financieras.

  3. Selección de Artículos en Compras en Línea:

    • En el ámbito del comercio electrónico, los clientes a menudo buscan comprar un conjunto de artículos que satisfagan ciertos criterios, como un presupuesto específico o una combinación de características. El problema de la Suma de Subconjuntos podría utilizarse para encontrar todas las combinaciones posibles de artículos que cumplan con los requisitos del cliente, facilitando la toma de decisiones de compra.

*Este artículo es creado con el fin de aprender más sobre los conceptos y plasmarlos en una página web que permita tenerlos a la mano, además, ha sido creado con ayuda de IA.

HABLEMOS SOBRE TU ESTRATEGIA

Las empresas viven en constante cambio, unas van lento, otras van rápido. Las decisiones que tomes cambiarán el futuro de tu compañía. Toma las decisiones correctas y permanece en el tiempo. 

 
Por ello existimos.