Los algoritmos recursivos de vuelta atrás (backtracking) explicados y con ejemplos

Your ads will be inserted here by

Easy AdSense.

Please go to the plugin admin page to paste your ad code.

Puzzle Tetris

Andrea Iacono publicó un buen artículo sobre los algoritmos de «vuelta atrás»: Backtracking Explained. Se trata de una estrategia normalmente recursiva para resolver problemas como los de los laberintos, la colocación de piezas y similares, en los que mediante una búsqueda en profundidad se puede dar con la solución.

El nombre vuelta atrás (backtracking) viene del hecho de que en la búsqueda de la solución se va volviendo a un punto anterior para probar alternativas.

Backtracking

Imaginemos un laberinto: al llegar a una encrucijada (1, 2, 3) se prueba con una dirección. Si con eso se llega a la solución, problema resuelto. Si no, se vuelve atrás a la encrucijada anterior y se prueba con otra, repitiendo el proceso cuantas veces sea necesario. (Si se agotan todas las opciones y no se ha llegado, es que no existe solución: no hay salida)

Normalmente las combinaciones de este tipo de problemas son muchas, pero se aplican ciertas restricciones, lo que suele hacer el total de opciones a probar algo computable en un tiempo razonable. También se puede buscar revisar todas planteando obtener «una solución mejor»; de este modo se puede llegar a la solución óptima.

Algunos ejemplos típicos en los que se puede aplicar este método son los laberintos, el Sudoku (para uno normal de 9×9, entre 15.000 y 90.000 ciclos) o en ajedrez el problema del recorrido del caballo o el de las ocho damas. En terrenos más prácticos el problema de la mochila es uno de los ejemplos más clásicos: optimizar qué objetos meter que maximicen la ocupación de un espacio de una forma determinada (quizá lo hayas experimentado en el maletero del coche en los Tetris 3D de las vacaciones.)

El rompecabezas de madera de la imagen –uno de los muchos puzles de madera chinos sin nombre, similar al de los pentominós 2D– inspiró a Lacono a crear un programa para resolver llamado GoShapesPuzzle [en Github] usando el lenguaje Go (y gotk3), tal y como está explicado y en el código del que se puede aprender.

# Enlace Permanente

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

*