Algoritmia/Vuelta atrás
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 el contrario, 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.
Ejemplo
editarEjercicios resueltos
editarProblema de las ocho reinas
editarhttp://es.wikipedia.org/wiki/Las_ocho_reinas
Problema de las ocho reinas. (2013, 17 de abril). Wikipedia, La enciclopedia libre. Fecha de consulta: 02:48, junio 26, 2013 desde http://es.wikipedia.org/w/index.php?title=Problema_de_las_ocho_reinas&oldid=66297155.
Problema de la mochila
editarhttp://es.wikipedia.org/wiki/Problema_de_la_mochila
Problema de la mochila. (2013, 9 de marzo). Wikipedia, La enciclopedia libre. Fecha de consulta: 23:31, junio 25, 2013 desde http://es.wikipedia.org/w/index.php?title=Problema_de_la_mochila&oldid=64532197.
Problema de las agencias matrimoniales
editarhttp://es.wikipedia.org/wiki/Vuelta_Atrás:_Agencias_Matrimoniales
Problema del viajante
editarhttp://es.wikipedia.org/wiki/Problema_del_viajante
Problema del viajante. (2013, 4 de abril). Wikipedia, La enciclopedia libre. Fecha de consulta: 23:33, junio 25, 2013 desde http://es.wikipedia.org/w/index.php?title=Problema_del_viajante&oldid=65966159.
Problema del reparto del botín
editarhttp://es.wikipedia.org/wiki/Problema_del_reparto_del_botín
Problema del laberinto
editarhttp://es.wikipedia.org/wiki/Problema_del_laberinto http://es.wikipedia.org/wiki/Problema_del_laberinto_con_límite
Problema del dominó
editarhttp://es.wikipedia.org/wiki/Problema_del_dominó
Problema del caballo
editarhttp://es.wikipedia.org/wiki/Problema_de_los_movimientos_de_un_caballo
Problema del caballo. (2013, 9 de marzo). Wikipedia, La enciclopedia libre. Fecha de consulta: 23:38, junio 25, 2013 desde http://es.wikipedia.org/w/index.php?title=Problema_del_caballo&oldid=64532320.
Problema del sudoku
editarhttp://es.wikipedia.org/wiki/Sudoku_backtracking
Sudoku backtracking. (2013, 16 de junio). Wikipedia, La enciclopedia libre. Fecha de consulta: 23:38, junio 25, 2013 desde http://es.wikipedia.org/w/index.php?title=Sudoku_backtracking&oldid=67722892.
Problema de minimización de cableado
editarhttp://es.wikipedia.org/wiki/Minimización_de_cableado_en_placa