Palabras clave
square mazes
randomized algorithms
trees and graphs
optimización combinatoria
laberintos cuadrados
algoritmos aleatorizados
árboles y gráficas
Cómo citar
Resumen
El artículo describe un nuevo método para resolver laberintos cuadrados usando una versión aleatorizada de búsqueda a profundidad. El algoritmo propuesto se probó en dos familias de laberintos, una de ellas basada en el método de Aldous-Broder y el otro en el de Backtrack. El algoritmo de solución se compara con el método de Dijkstra, que es una técnica bien conocida para resolver este tipo de problemas. Este encuentra soluciones en menor tiempo en laberintos de gran tamaño (mayores a 100 x 100 celdas).
Citas
D. Ashlock, C. Lee, C. McGuinness, Search-based procedural generation of maze-like levels, IEEE Transactions on Computational Intelligence and Al in Games 3 (2011), no. 3, 260-273.
J. Buck, Mazes for Programmers: Code Your Own Twisty Little Passages, The Pragmatic Bookshelf, Texas, 2015.
D. C. Dracopoulos, Robot path planning for maze navigation, 1998 IEEE International Joint Conference on Neural Networks Proceedings, Vol. 3, IEEE World Congress on Computational Intelligence, 1998.
A. S. Fraenkel, Economic traversal of labyrinths, Mathematics Magazine 43 (1970), no. 3, 125-130.
K. Hamada, A picturesque maze generation algorithm with any given endpoints, Journal of Information Processing 21 (2013), no. 3, 393-397.
G. E. Jan, K-Y. Chang, I. Parberry, A new maze routing approach for path planning of a mobile robot, 2003 IEEE/ASME International Conference on Advanced Intelligent Mechatronics, Vol. 2, The Institute of Electrical and
Electronics Engineers, Inc., Japan, 2003.
M. T. Jones, Artificial Intelligence: A Systems Approach, Infinity Science Press, USA, 2008.
W. H. Matthews, Mazes and Labyrinths: Their History and Development, Dover Publications, New York, 1970.
V. T. Tomás, M. Pozas, J. Hernández, Propuesta para la generación de laberintos ampliados en 2D, Ciencia Huasteca, UAEH, México, 2011.
Comentarios
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Derechos de autor 2019 Iván Omar Cruz-Ruiz, Pedro Lara-Velázquez, Sergio G. De-Los-Cobos-Silva, Eric A. Rincón-García, Román A. Mora-Gutiérrez, Miguel A. Gutiérrez-Andrade