Solving Mazes: A New Approach Based on Spectral Graph Theory

Marta Martín-Nieto, Damián Castaño, Sergio Horta Muñoz and David Ruiz ()
Additional contact information
Marta Martín-Nieto: Escuela de Ingeniería Industrial y Aeroespacial de Toledo, Universidad de Castilla-La Mancha, Av. Carlos III, Campus Fábrica de Armas, 45004 Toledo, Spain
Damián Castaño: Escuela de Ingeniería Industrial y Aeroespacial de Toledo, Universidad de Castilla-La Mancha, Av. Carlos III, Campus Fábrica de Armas, 45004 Toledo, Spain
Sergio Horta Muñoz: Escuela de Ingeniería Industrial y Aeroespacial de Toledo, Universidad de Castilla-La Mancha, Av. Carlos III, Campus Fábrica de Armas, 45004 Toledo, Spain
David Ruiz: Escuela de Ingeniería Industrial y Aeroespacial de Toledo, Universidad de Castilla-La Mancha, Av. Carlos III, Campus Fábrica de Armas, 45004 Toledo, Spain

Mathematics, 2024, vol. 12, issue 15, 1-13

Abstract: The use of graph theory for solving labyrinths and mazes is well known, understanding the possible paths as the connections between the nodes that represent the corners or bifurcations. This work presents a new idea: minimizing the length of the optimal path formulated as a topology optimization problem. The maze is mapped with finite elements, and then, through the eigenvalues of the Laplacian matrix of the graph, a constraint is imposed over the connectivity between the input and the output. Several 2D examples are provided to support this approach, allowing for unequivocally finding the shortest path in mazes with multiple connections between entrance and exit, resulting in an nonheuristic algorithm.

Keywords: mazes; topology optimization; graph theory; eigenproblem; connectivity constraints (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/15/2305/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/15/2305/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:15:p:2305-:d:1441185

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().