Un algoritmo estocástico para resolver laberintos

• CRUZ RUÍZ, IVAN OMAR ^[1] ; LARA VELÁZQUEZ, PEDRO ^[1] ; DE LOS COBOS SILVA, SERGIO G. ^[1] ; RINCÓN GARCÍA, ERIC A. ^[1] ; MORA GUTIÉRREZ, ROMÁN A. ^[2] ; GUTIÉRREZ ANDRADE, MIGUEL A. ^[1]
  1. [1] Universidad Autónoma Metropolitana-Iztapalapa, Departamento de Ingeniería Eléctrica, Ciudad de México, México
  2. [2] Universidad Autónoma Metropolitana-Azcapotzalco, Departamento de Sistemas, Ciudad de México, México
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 26, Nº. 2, 2019 (Ejemplar dedicado a: Revista de Matemática: Teoría y Aplicaciones), págs. 319-338
• Idioma: español
• DOI: 10.15517/rmta.v26i2.38322
• Títulos paralelos:
  • A stochastic algorithm for solving mazes
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    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).

  • English

    In this article a new method to solve square mazes using a randomized depth-first search algorithm is described. The algorithm was tested in two families of labyrinths, one of them based on the Aldous-Broder method and the other on Backtrack. The algorithm was compared against the Dijkstra method, a well-known technique to solve this kind of problems. The new method finds solutions in less time for large-size labyrinths(greater than 100 x 100 cells).

• Referencias bibliográficas
  • D. Ashlock, C. Lee, C. McGuinness, Search-based procedural generation of maze-like levels, IEEE Transactions on Computational Intelligence...
  • 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....
  • 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...
  • 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.