IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i15p2305-d1441185.html
   My bibliography  Save this article

Solving Mazes: A New Approach Based on Spectral Graph Theory

Author

Listed:
  • 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
    CES Don Bosco, Universidad Complutense de Madrid, María Auxiliadora 9, 28040 Madrid, 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
    Geonum Group, 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
    Instituto de Investigación Aplicada a la Industria Aeronáutica, 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
    OMEVA Research Group, 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)

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.

Suggested Citation

  • Marta Martín-Nieto & Damián Castaño & Sergio Horta Muñoz & David Ruiz, 2024. "Solving Mazes: A New Approach Based on Spectral Graph Theory," Mathematics, MDPI, vol. 12(15), pages 1-13, July.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:15:p:2305-:d:1441185
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/15/2305/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/15/2305/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Zhang, Hongyong, 2018. "Political connections and antidumping investigations: Evidence from China," China Economic Review, Elsevier, vol. 50(C), pages 34-41.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. repec:zbw:bofitp:2019_004 is not listed on IDEAS
    2. Ito, Asei & Lim, Jaehwan & Zhang, Hongyong, 2023. "Catching the political leader's signal: Economic policy uncertainty and firm investment in China," China Economic Review, Elsevier, vol. 81(C).
    3. Tan Li & Wei Xiao, 2022. "US antidumping investigations and employment adjustment in Chinese manufacturing firms," Economics of Transition and Institutional Change, John Wiley & Sons, vol. 30(1), pages 159-182, January.
    4. Deng, Yuping & Wu, Yanrui & Xu, Helian, 2019. "Political connections and firm pollution behaviour: An empirical study," BOFIT Discussion Papers 4/2019, Bank of Finland Institute for Emerging Economies (BOFIT).
    5. Yuping Deng & Yanrui Wu & Helian Xu, 2020. "Political Connections and Firm Pollution Behaviour: An Empirical Study," Environmental & Resource Economics, Springer;European Association of Environmental and Resource Economists, vol. 75(4), pages 867-898, April.
    6. Mukunoki, Hiroshi, 2021. "Trade liberalization and incentives to implement antidumping protection," International Review of Economics & Finance, Elsevier, vol. 72(C), pages 422-437.
    7. Evans Opoku-Mensah & Yuming Yin & Bismark Addai, 2021. "Do Mature Firms Gain Higher Economic Value from R&D Investment?," Journal of Industry, Competition and Trade, Springer, vol. 21(2), pages 211-223, June.
    8. Bahoo, Salman, 2020. "Corruption in banks: A bibliometric review and agenda," Finance Research Letters, Elsevier, vol. 35(C).
    9. Liu, Shiyuan & Du, Jiang & Zhang, Weike & Tian, Xiaoli & Kou, Gang, 2021. "Innovation quantity or quality? The role of political connections," Emerging Markets Review, Elsevier, vol. 48(C).
    10. Li, Yue & Li, Wanli, 2022. "Are innovative exporters vulnerable to anti-dumping investigations?," Technovation, Elsevier, vol. 112(C).
    11. Ka Zeng & Yue Lu & Ya‐wei Li, 2021. "Trade agreements and Global Value Chain (GVC) participation: Evidence from Chinese industries," Economics and Politics, Wiley Blackwell, vol. 33(3), pages 533-582, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:12:y:2024:i:15:p:2305-:d:1441185. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.