Un algoritmo estocástico para resolver laberintos
Título del documento: Un algoritmo estocástico para resolver laberintos
Revista: Revista de matemáticas
Base de datos: PERIÓDICA
Número de sistema: 000453568
ISSN: 1409-2433
Autors: 1
1
1
1
1
2
Institucions: 1Universidad Autónoma Metropolitana, Departamento de Ingeniería Eléctrica, Iztapalapa, Ciudad de México. México
2Universidad Autónoma Metropolitana, Departamento de Sistemas, Azcapotzalco, Ciudad de México. México
Any:
Període: Jul-Dic
Volum: 26
Número: 2
Paginació: 319-337
País: Costa Rica
Idioma: Español
Tipo de documento: Artículo
Enfoque: Aplicado, descriptivo
Resumen en 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 la otra 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 a100x100 celdas)
Resumen en inglés 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)
Disciplines Matemáticas
Paraules clau: Matemáticas aplicadas,
Optimización combinatoria,
Laberintos cuadrados,
Algoritmos aleatorios
Keyword: Applied mathematics,
Combinatorial optimization,
Square mazes,
Randomized algorithms
Text complet: Texto completo (Ver HTML) Texto completo (Ver PDF)