Primerjava algoritmov za izdelavo in reševanje labirintov

KERŽAN, ŽIGA (author), Rožanc, Igor (mentor)

V diplomski nalogi predstavljamo algoritme, ki tvorijo in rešujejo labirinte. Po predstavitvi značilnosti labirintov smo najprej predstavili njihovo povezavo z grafi. Izbrali smo pet znanih algoritmov iz literature in dva naša izvirna algoritma za tvorbo ter dva algoritma za reševanje labirintov. Vse algoritme smo opisali, izpostavili njihove dobre in slabe strani ter jih implementirali. Združili smo jih v aplikaciji, v kateri lahko labirinte rešujemo ali pa opazujemo njihovo tvorbo z različnimi algoritmi. Aplikacija je bila spisana v programskem jeziku Pyhton. V zadnjem delu je prikazana še analiza časovne in prostorne zahtevnosti. Ta kaže, da je za tvorbo labirintov najhitrejši in najmanj potraten algoritem z uporabo dvojiških dreves, naša algoritma pa tudi ne zaostajata veliko.

• Language: Slovenian
• Keywords: labirint, algoritem, minimalna vpeta drevesa, Kruskalov algoritem, Primov algoritem, BFS, DFS, časovna analiza, prostorska analiza
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2024
• PID: 20.500.12556/RUL-155261
• COBISS.SI-ID: 190814211
• Publication date in RUL: 22.03.2024

KERŽAN, ŽIGA, 2024, Primerjava algoritmov za izdelavo in reševanje labirintov [online]. Bachelor’s thesis. [Accessed 17 May 2025]. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=155261

Secondary language

• Language: English
• Title: Comparison of algorithms for maze creation and solving

Abstract

In this thesis, we present algorithms for creating and solving of labyrinths. We presented the characteristics of labyrinths and how are they related to the graphs. We selected five known algorithms from the literature, two of our own for creation and two algorithms for solving labyrinths. All algorithms are described, presented with their good and bad sides and implemented. All algorithms are part of an application which allows labyrinth solving and presentation of step by step construction. The application is written in Python programming language. In the last part, an analysis of time and space complexity is shown, which proves binary tree algorithm is the fastest and least expensive algorithm for creating labyrinths. Our two algorithms have similar performance, too.

• Keywords: labrynth, algorithm, minimum spanning trees, Kruskal's algorithm, Prim's algorithm, BFS, DFS, time analysis, space analysis