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.

EjemploEditar

Ejercicios resueltosEditar

Problema de las ocho reinasEditar

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 mochilaEditar

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 matrimonialesEditar

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

Problema del viajanteEditar

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ínEditar

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

Problema del laberintoEditar

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

Problema del dominóEditar

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

Problema del caballoEditar

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 sudokuEditar

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 cableadoEditar

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