BACKTRACKING Y ALGORITMOS AVAROS

¿Qué significa el termino “backtracking”?

•  Avance continuo sin retroceso

  
  

•  Revisión aleatoria de decisiones

• Vuelta atrás para buscar otra solución

• Cálculo exacto desde el inicio

¿Quién creo el término “backtracking”?

• D.H. Lehmer

• Edsger Dijkstra

• Alan Turing

•  Donald Knuth

¿Cómo se representa el proceso de backtracking?

•  Como una matriz de datos

•  Como un árbol de decisiones

• Como una lista de pasos

• Como un conjunto de ecuaciones

¿Qué problema clásico se resuelve con backtracking?

•  Cambio de monedas

  
  

•  Búsqueda binaria

  
  

• Suma de vectores

  
  

•  Las 8 reinas

¿Qué ventaja principal ofrece el backtracking?

• Menor consumo de memoria

  
  

• Exploración completa de soluciones

• Siempre encuentra la solución óptima

  
  

• Evita usar estructuras condicionales

  
  

¿Qué caracteriza a un algoritmo avaro?

• Prueba todas las opciones

  
  

• Evita soluciones óptimas

  
  

• Toma la mejor opción local

• Aumenta la complejidad

  
  

¿Cómo se diferencia un algoritmo avaro de uno backtracking?

• El avaro nunca retrocede

•  El avaro usa más memoria

  
  

• El backtracking es más rápido

  
  

• Ambos siempre encuentran lo óptimo

  
  

¿Cuál es un ejemplo clásico de algoritmo avaro?

• Resolver ecuaciones

• Laberintos

• Cambio de monedas

• Multiplicación de matrices

¿Qué ventaja tiene un algoritmo avaro?

• Siempre encuentra todas las soluciones

  
  

•  Funciona sin restricciones

  
  

• No necesita estructura de datos

  
  

•  Es rápido y fácil de implementar

¿En qué tipo de problemas se usa backtracking?

• Optimización y búsqueda de soluciones

•  Estadísticas simples

  
  

• Resolución de ecuaciones

  
  

• Cálculo de promedio