Algoritmia/Vuelta atrás
De Wikilibros, la colección de libros de texto de contenido libre.
Los algoritmos de vuelta atrás o retroceso (backtracking en inglés) se basan en recorrer el espacio completo de las soluciones posibles al problema planteado. Esta técnica es la aplicación directa del método de búsqueda conocido como primero en profundidad. Típicamente, los algoritmos de vuelta atrás no realizan ningún tipo de optimización y recorren el árbol de soluciones completo. Sin embargo, es posible aplicarles una poda para no descender en aquellas ramas que, de antemano, se sabe que no conducen a una solución. Una mejora de los algoritmos de vuelta atrás son los algoritmos de Ramificación y poda.
Si bien este tipo de algoritmos son por lo general ineficientes, en ocasiones es el único camino posible. Además, pueden considerarse otros métodos algorítmicos, como los algoritmos voraces o la programación dinámica, como optimizaciones de este método.
El algoritmo básico de vuelta atrás es el siguiente:
- Tomar una opción de entre las posibles
- Para cada elección, considerar toda opción posible recursivamente
- Devolver la mejor solución encontrada
Esta metodología es lo suficientemente genérica como para ser aplicada en la mayoría de problemas. Por contra, incluso teniendo cuidado en la implementación, es muy probable que un algoritmo de vuelta atrás sea de tiempo exponencial y no polinómico. Además, el análisis de estos algoritmos puede resultar bastante complejo.
Contenido |
[editar] Ejemplo
[editar] Ejercicios resueltos
[editar] Problema de la mochila
http://es.wikipedia.org/wiki/Problema_de_la_mochila_utilizando_Vuelta_Atrás
[editar] Problema de las agencias matrimoniales
http://es.wikipedia.org/wiki/Vuelta_Atrás:_Agencias_Matrimoniales
[editar] Problema del viajante
http://es.wikipedia.org/wiki/Problema_del_viajante_sobre_grafos_dirigidos
[editar] Problema del reparto del botín
http://es.wikipedia.org/wiki/Problema_del_reparto_del_botín
[editar] Problema del laberinto
http://es.wikipedia.org/wiki/Problema_del_laberinto http://es.wikipedia.org/wiki/Problema_del_laberinto_con_límite
[editar] Problema del dominó
http://es.wikipedia.org/wiki/Problema_del_dominó
[editar] Problema del caballo
http://es.wikipedia.org/wiki/Problema_de_los_movimientos_de_un_caballo
[editar] Problema del sudoku
http://es.wikipedia.org/wiki/Sudoku_backtracking
[editar] Problema de minimización de cableado
http://es.wikipedia.org/wiki/Minimización_de_cableado_en_placa
