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
Autores: 1
1
1
1
1
2
Instituciones: 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
Año:
Periodo: Jul-Dic
Volumen: 26
Número: 2
Paginación: 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)
Disciplinas: Matemáticas
Palabras clave: Matemáticas aplicadas,
Optimización combinatoria,
Laberintos cuadrados,
Algoritmos aleatorios
Keyword: Applied mathematics,
Combinatorial optimization,
Square mazes,
Randomized algorithms
Texto completo: Texto completo (Ver HTML) Texto completo (Ver PDF)