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:

1. Tomar una opción de entre las posibles
2. Para cada elección, considerar toda opción posible recursivamente
3. 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.

Ejercicios resueltos

Problema de las ocho reinas

http://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

http://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

http://es.wikipedia.org/wiki/Vuelta_Atrás:_Agencias_Matrimoniales

Problema del viajante

http://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

http://es.wikipedia.org/wiki/Problema_del_reparto_del_botín

Problema del laberinto

http://es.wikipedia.org/wiki/Problema_del_laberinto http://es.wikipedia.org/wiki/Problema_del_laberinto_con_límite

Problema del dominó

http://es.wikipedia.org/wiki/Problema_del_dominó

Problema del caballo

http://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

http://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

http://es.wikipedia.org/wiki/Minimización_de_cableado_en_placa