| Journal: | Revista de matemáticas |
| Database: | PERIÓDICA |
| System number: | 000453568 |
| ISSN: | 1409-2433 |
| Authors: | Cruz Ruiz, Iván Omar1 Lara Velázquez, Pedro1 Gutiérrez Andrade, Miguel A1 De los Cobos Silva, Sergio G1 Rincón García, Eric A1 Mora Gutiérrez, Román A2 |
| Institutions: | 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 |
| Year: | 2019 |
| Season: | Jul-Dic |
| Volumen: | 26 |
| Number: | 2 |
| Pages: | 319-337 |
| Country: | Costa Rica |
| Language: | Español |
| Document type: | Artículo |
| Approach: | Aplicado, descriptivo |
| Spanish abstract | 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) |
| English abstract | 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 |
| Keyword: | Matemáticas aplicadas, Optimización combinatoria, Laberintos cuadrados, Algoritmos aleatorios |
| Keyword: | Applied mathematics, Combinatorial optimization, Square mazes, Randomized algorithms |
| Full text: | Texto completo (Ver HTML) Texto completo (Ver PDF) |
