İki boyutlu labirentlerde arama algoritmalarının incelenmesi
Investigation of search algorithms in two-dimensional mazes
- Tez No: 905402
- Danışmanlar: DR. ÖĞR. ÜYESİ AYŞE ÖVGÜ KINAY
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: Türkçe
- Üniversite: Dokuz Eylül Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Bilimleri Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- Mekan yanılsamasından resim yüzeyine espas
Space, from illusion to the surface of the painting
DERYA ÜLKER
- İki boyutlu yol modelleri üzerinde elastik dalgaların yayılmasının etüdü
Başlık çevirisi yok
EMİNE AĞAR
- İki boyutlu tek fazlı petrol rezervuar simülasyonu
Başlık çevirisi yok
YAVUZ CABBAR
Yüksek Lisans
Türkçe
1985
Petrol ve Doğal Gaz MühendisliğiAnadolu ÜniversitesiYRD. DOÇ. DR. MUSTAFA KARA
- İki boyutlu çok bantlı doğrusal öngörü modellerinin görüntü kodlama ve tanımaya uygulanması
Başlık çevirisi yok
YUSUF ÖZTÜRK
Doktora
Türkçe
1990
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. EMRAH ORHUN