Con estos algoritmos vamos a intentar resolver problemas en los que sólo podemos recurrir a realizar una búsqueda exhaustiva recorriendo todas las posibles soluciones hasta encontrar la que buscamos o hasta que la búsqueda finalice.
En muchas ocasiones nos encontramos con problemas en los que no podemos aplicar ningun algoritmo específico para resolverlo, por lo que tenemos que recurrir a realizar una búsqueda exhaustiva de las posibles soluciones.
El esquema de vuelta atrás para resolver un problema realiza un recorrido en profundidad del grafo de un problema, podando aquellas ramas para las que el algoritmo puede comprobar que no hay solución al problema. Las soluciones se van construyendo de forma incremental. En su forma más básica, la vuelta atrás es similar a un recorrido en profundidad dentro de un grafo dirigido. El objetivo de estos algoritmos de vuelta atrás es encontrar una solución o encontrar todas las posibles soluciones al problema dado.
Los pasos que generalmente tiene todo algoritmo de vuelta atrás son: recoger todas las opciones posibles en que se puede extender la solución, comprobar las opciones que quedan por explorar, comprobar que se haya completado la solución al problema y obtener la solución.
Este tipo de esquemas algoritmicos es bueno para realizar problemas de coloreado de grafos, ciclos Hamiltonianos, etc.
Si queréis que profundicemos más en este tipo de algoritmos no dudéis en ponerlo en los comentarios.
Saludos a tod@s!! ;)
No hay comentarios:
Publicar un comentario