logo

TechCodeview

Algoritmo de retroceso

Algoritmos de retroceso son como estrategias de resolución de problemas que ayudan a explorar diferentes opciones para encontrar la mejor solución. Trabajan probando diferentes caminos y si uno no funciona, retroceden y prueban otro hasta encontrar el correcto. Es como resolver un rompecabezas probando diferentes piezas hasta que encajen perfectamente.

granandhra

Retroceder

Tabla de contenidos



¿Qué es el algoritmo de retroceso?

Retroceder Es una técnica algorítmica de resolución de problemas que implica encontrar una solución de forma incremental intentando diferentes opciones y ruina ellos si conducen a una callejón sin salida .

Se usa comúnmente en situaciones en las que necesitas explorar múltiples posibilidades para resolver un problema, como buscar un camino en un laberinto o resolver acertijos como Sudokus . Cuando se llega a un callejón sin salida, el algoritmo retrocede hasta el punto de decisión anterior y explora un camino diferente hasta que se encuentra una solución o se agotan todas las posibilidades.

modelo ip tcp

¿Cómo funciona un algoritmo de retroceso?

A algoritmo de retroceso Funciona explorando recursivamente todas las posibles soluciones a un problema. Comienza eligiendo una solución inicial y luego explora todas las posibles extensiones de esa solución. Si una extensión conduce a una solución, el algoritmo devuelve esa solución. Si una extensión no conduce a una solución, el algoritmo retrocede a la solución anterior e intenta una extensión diferente.

El siguiente es un esquema general de cómo funciona un algoritmo de retroceso:

  1. Elija una solución inicial.
  2. Explore todas las posibles extensiones de la solución actual.
  3. Si una extensión conduce a una solución, devuelva esa solución.
  4. Si una extensión no conduce a una solución, retroceda a la solución anterior y pruebe con una extensión diferente.
  5. Repita los pasos 2 a 4 hasta que se hayan explorado todas las soluciones posibles.

Ejemplo de algoritmo de retroceso

Ejemplo: Encontrar el camino más corto a través de un laberinto

Aporte: Un laberinto representado como una matriz 2D, donde 0 representa un espacio abierto y 1 representa una pared.

Algoritmo:

  1. Comience en el punto de partida.
  2. Para cada una de las cuatro direcciones posibles (arriba, abajo, izquierda, derecha), intente moverse en esa dirección.
  3. Si avanzar en esa dirección lleva al punto final, se regresa por el camino tomado.
  4. Si moverse en esa dirección no conduce al punto final, retroceda a la posición anterior e intente en una dirección diferente.
  5. Repita los pasos 2 a 4 hasta llegar al punto final o hasta que se hayan explorado todos los caminos posibles.

¿Cuándo utilizar un algoritmo de retroceso?

Los algoritmos de retroceso se utilizan mejor para resolver problemas que tienen las siguientes características:

  • Hay múltiples soluciones posibles al problema.
  • El problema se puede dividir en subproblemas más pequeños.
  • Los subproblemas se pueden resolver de forma independiente.

Aplicaciones del algoritmo de retroceso

Los algoritmos de retroceso se utilizan en una amplia variedad de aplicaciones, que incluyen:

primavera y primavera mvc
  • Resolver acertijos (por ejemplo, Sudoku, crucigramas)
  • Encontrar el camino más corto a través de un laberinto
  • Problemas de programación
  • Problemas de asignación de recursos
  • Problemas de optimización de la red

Básico del algoritmo de retroceso:

  • Diferencia entre la técnica Backtracking y Branch-N-Bound
  • ¿Cuál es la diferencia entre retroceso y recursividad?

Problemas estándar sobre el algoritmo de retroceso:

  • El problema de la gira del Caballero
  • Rata en un laberinto
  • Problema de la reina N | Retroceso-3
  • Problema de suma de subconjuntos
  • m Problema de coloración
  • Ciclo hamiltoniano
  • Sudokus | Retroceso-7
  • Rompecabezas magnético
  • Eliminar paréntesis no válidos
  • Un enfoque de retroceso para generar códigos Gray de n bits
  • Escribe un programa para imprimir todas las permutaciones de una cadena determinada.

Problemas sencillos con el algoritmo de retroceso:

  • Retroceder para encontrar todos los subconjuntos
  • Comprobar si una cadena dada es cadena de suma
  • Cuente todos los caminos posibles entre dos vértices.
  • Encuentra todos los subconjuntos distintos de un conjunto dado
  • Encuentre si hay un camino de más de k longitud desde una fuente
  • Imprima todas las rutas desde un origen determinado hasta un destino
  • Imprime todas las cadenas posibles que se pueden hacer colocando espacios.

Problemas medios en el algoritmo de retroceso:

  • Tira y afloja
  • problema de 8 reinas
  • Suma combinacional
  • Algoritmo de Warnsdorff para el problema del recorrido de Knight
  • Encuentra caminos desde la celda de la esquina hasta la celda del medio en el laberinto
  • Encuentre el número máximo posible haciendo como máximo K swaps
  • Rata en un laberinto con múltiples pasos o saltos permitidos.
  • N Reina en el espacio O(n)

Problemas difíciles con el algoritmo de retroceso:

  • Conjunto de poderes en orden lexicográfico
  • Problema de ruptura de palabras al retroceder
  • Partición de un conjunto en K subconjuntos con igual suma
  • La ruta más larga posible en una matriz con obstáculos
  • Encuentra la ruta segura más corta en un camino con minas terrestres
  • Imprime todas las particiones palindrómicas de una cadena.
  • Imprimir todas las soluciones en N-Queen Problem
  • Imprima todas las subsecuencias comunes más largas en orden lexicográfico

Enlaces rápidos :

  • Aprenda la estructura de datos y los algoritmos | Tutorial de DSA
  • Las 20 preguntas principales de la entrevista sobre el algoritmo de retroceso
  • 'Vídeos' sobre el retroceso