Un algoritmo estocástico para resolver laberintos

Un algoritmo estocástico para resolver laberintos

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

Descripción completa

Detalles Bibliográficos
Autores principales: Cruz-Ruiz, Iván Omar, Lara-Velázquez, Pedro, De-Los-Cobos-Silva, Sergio G., Rincón-García, Eric A., Mora-Gutiérrez, Román A., Gutiérrez-Andrade, Miguel A.
Formato: Online
Idioma:spa
Publicado: Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2019
Acceso en línea:https://revistas.ucr.ac.cr/index.php/matematica/article/view/38322
id RMTA38322
record_format ojs
spelling RMTA383222022-02-02T15:24:21Z A stochastic algorithm for solving mazes Un algoritmo estocástico para resolver laberintos Cruz-Ruiz, Iván Omar Lara-Velázquez, Pedro De-Los-Cobos-Silva, Sergio G. Rincón-García, Eric A. Mora-Gutiérrez, Román A. Gutiérrez-Andrade, Miguel A. combinatorial optimization square mazes randomized algorithms trees and graphs optimización combinatoria laberintos cuadrados algoritmos aleatorizados árboles y gráficas 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). 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). Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2019-08-01 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf application/postscript application/x-dvi https://revistas.ucr.ac.cr/index.php/matematica/article/view/38322 10.15517/rmta.v26i2.38322 Revista de Matemática: Teoría y Aplicaciones; Vol. 26 No. 2 (2019): Revista de Matemática: Teoría y Aplicaciones; 319-338 Revista de Matemática: Teoría y Aplicaciones; Vol. 26 Núm. 2 (2019): Revista de Matemática: Teoría y Aplicaciones; 319-338 Revista de Matemática; Vol. 26 N.º 2 (2019): Revista de Matemática: Teoría y Aplicaciones; 319-338 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/38322/39083 https://revistas.ucr.ac.cr/index.php/matematica/article/view/38322/39189 https://revistas.ucr.ac.cr/index.php/matematica/article/view/38322/39190 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 https://creativecommons.org/licenses/by-nc-sa/4.0
institution Universidad de Costa Rica
collection Revista de Matemática: Teoría y Aplicaciones
language spa
format Online
author Cruz-Ruiz, Iván Omar
Lara-Velázquez, Pedro
De-Los-Cobos-Silva, Sergio G.
Rincón-García, Eric A.
Mora-Gutiérrez, Román A.
Gutiérrez-Andrade, Miguel A.
spellingShingle Cruz-Ruiz, Iván Omar
Lara-Velázquez, Pedro
De-Los-Cobos-Silva, Sergio G.
Rincón-García, Eric A.
Mora-Gutiérrez, Román A.
Gutiérrez-Andrade, Miguel A.
Un algoritmo estocástico para resolver laberintos
author_facet Cruz-Ruiz, Iván Omar
Lara-Velázquez, Pedro
De-Los-Cobos-Silva, Sergio G.
Rincón-García, Eric A.
Mora-Gutiérrez, Román A.
Gutiérrez-Andrade, Miguel A.
author_sort Cruz-Ruiz, Iván Omar
description 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).
title Un algoritmo estocástico para resolver laberintos
title_short Un algoritmo estocástico para resolver laberintos
title_full Un algoritmo estocástico para resolver laberintos
title_fullStr Un algoritmo estocástico para resolver laberintos
title_full_unstemmed Un algoritmo estocástico para resolver laberintos
title_sort un algoritmo estocástico para resolver laberintos
title_alt A stochastic algorithm for solving mazes
publisher Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate 2019
url https://revistas.ucr.ac.cr/index.php/matematica/article/view/38322
work_keys_str_mv AT cruzruizivanomar astochasticalgorithmforsolvingmazes
AT laravelazquezpedro astochasticalgorithmforsolvingmazes
AT deloscobossilvasergiog astochasticalgorithmforsolvingmazes
AT rincongarciaerica astochasticalgorithmforsolvingmazes
AT moragutierrezromana astochasticalgorithmforsolvingmazes
AT gutierrezandrademiguela astochasticalgorithmforsolvingmazes
AT cruzruizivanomar unalgoritmoestocasticopararesolverlaberintos
AT laravelazquezpedro unalgoritmoestocasticopararesolverlaberintos
AT deloscobossilvasergiog unalgoritmoestocasticopararesolverlaberintos
AT rincongarciaerica unalgoritmoestocasticopararesolverlaberintos
AT moragutierrezromana unalgoritmoestocasticopararesolverlaberintos
AT gutierrezandrademiguela unalgoritmoestocasticopararesolverlaberintos
AT cruzruizivanomar stochasticalgorithmforsolvingmazes
AT laravelazquezpedro stochasticalgorithmforsolvingmazes
AT deloscobossilvasergiog stochasticalgorithmforsolvingmazes
AT rincongarciaerica stochasticalgorithmforsolvingmazes
AT moragutierrezromana stochasticalgorithmforsolvingmazes
AT gutierrezandrademiguela stochasticalgorithmforsolvingmazes
_version_ 1811744104930869248

Ejemplares similares