İki boyutlu labirentlerde arama algoritmalarının incelenmesi
Investigation of search algorithms in two-dimensional mazes
Yazar: MERVE MENEVŞE
Danışman: DR. ÖĞR. ÜYESİ AYŞE ÖVGÜ KINAY
Dokuz Eylül Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Bilimleri Ana Bilim Dalı / Bilgisayar Bilimleri Bilim Dalı
Derece: Yüksek Lisans, 2024
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Arama algoritmaları, akıllı elektrikli süpürgeler, oyunlarda yol bulma ve arama 
kurtarma robotları gibi çeşitli uygulamalarda yaygın olarak kullanılmaktadır.
Bunlardan labirent çözümü için kullanılan DFS (Derinlik Öncelikli Arama), BFS
(Genişlik Öncelikli Arama) ve A* (A Yıldız) algoritmaları ise farklı yaklaşımlarla en 
kısa yolun bulunmasını amaçlar. Labirentlerde DFS algoritması, yolları gezerek bir 
çözüm bulduğu için daha kısa bir yol varsa bile bu yola ulaşmayabilir. BFS, 
başlangıç düğümünden hedef düğüme olan en kısa yolu daha etkili bir şekilde bulur 
ancak haritadaki tüm düğümleri keşfetmesi gerekebileceğinden yavaştır. A* 
algoritması ise BFS'ye benzer şekilde en kısa yolu bulmada etkilidir ancak önceden 
belirlenmiş bir sezgisel fonksiyon kullanarak hedefe daha hızlı ilerler. Bu fonksiyon, 
A* algoritmasının daha az düğümü ziyaret etmesini ve bu nedenle daha hızlı 
sonuçlar üretmesini sağlar. A* algoritması ise diğer iki algoritmaya göre daha etkin 
en kısa yol bulunmasını sağlar. 
Bu tez çalışması kapsamında büyük labirent boyutları için bahsedilen 
algoritmalarının performansları incelenmiştir. Farklı boyutlarda ve zorluk 
seviyelerinde rastgele oluşturulan labirentlerde yol, yol uzunluğu ziyaret edilen hücre 
sayıları, bellek kullanımı ve süre incelenmiştir. Hesaplamalar Pycharm kod analiz 
aracı üzerinden Python program dili kullanılarak yapılmıştır. Yöntemler arası 
farklılıklar istatistiksel olarak anlamlı farklılık olup olmadığı spss ile incelenmiştir.

Abstract:
Search algorithms are commonly used in various applications, such as smart 
vacuum cleaners, pathfinding in games, and search and rescue robots. DFS (Depth 
First Search), BFS (Breadth First Search) and A* (A Star) algorithms used for maze 
solution aim to find the shortest path with different approaches. Since the DFS 
algorithm in mazes finds a solution by traveling paths, it may not reach that path 
even if there is a shorter path. BFS efficiently finds the shortest path from the starting 
node to the target node, but it can be slow because it might need to explore all nodes 
on the map. On the other hand, the A* algorithm is effective in finding the shortest 
path, similar to BFS, but it advances towards the target more quickly by using a 
predetermined heuristic function. This function allows the A* algorithm to visit 
fewer nodes and therefore produce faster results. The A* algorithm provides a more 
efficient shortest path than the other two algorithms.
In this thesis, the performances of the mentioned algorithms for large maze sizes 
were examined. The paths, path lengths, number of cells visited, ram and time using
were analyzed in randomly generated mazes of varying sizes and difficulty levels. 
Calculations were made using the Python programming language via the Pycharm 
code analysis tool. The differences between the methods were analyzed for statistical 
significance using SPSS.