Geri Dön

İki boyutlu labirentlerde arama algoritmalarının incelenmesi

Investigation of search algorithms in two-dimensional mazes

PDF İndir

  1. Tez No: 905402
  2. Yazar: MERVE MENEVŞE
  3. Danışmanlar: DR. ÖĞR. ÜYESİ AYŞE ÖVGÜ KINAY
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2024
  8. Dil: Türkçe
  9. Üniversite: Dokuz Eylül Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Bilimleri Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Bilimleri Bilim Dalı
  13. Sayfa Sayısı: 71

Ö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

  1. Tez No

    375316

    Mekan yanılsamasından resim yüzeyine espas

    Space, from illusion to the surface of the painting

    DERYA ÜLKER

    Yüksek Lisans

    Türkçe

    Türkçe

    2014

    Güzel SanatlarAnadolu Üniversitesi

    Resim Ana Sanat Dalı

    DOÇ. DR. RIDVAN COŞKUN

  2. Tez No

    82457

    Electron-electron interactions in a two dimensional quantum dot

    İki boyutlu kuvantum noktasındaki elektron-elektron etkileşimleri

    NURTEN AKMAN

    Doktora

    İngilizce

    İngilizce

    1999

    Fizik ve Fizik MühendisliğiOrta Doğu Teknik Üniversitesi

    Fizik Ana Bilim Dalı

    PROF.DR. MEHMET TOMAK

  3. Tez No

    82882

    Water quality assesment of İzmit bay by to dimensional modeling

    İki boyutlu modelleme ile İzmit Körfezi'nin su kalitesinin değerlendirilmesi

    KAĞAN DENGİLİ

    Yüksek Lisans

    İngilizce

    İngilizce

    1999

    İnşaat MühendisliğiBoğaziçi Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    PROF. DR. EROL GÜLER

  4. Tez No

    83096

    İki boyutlu bağıl kafes yapılı süreç ile uyarlamalı görüntü restorasyonu

    Two-dimensional joint process lattice for adaptive restoration of images

    ALİ ŞİR OLGAÇ

    Yüksek Lisans

    Türkçe

    Türkçe

    1999

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. AHMET HAMDİ KAYRAN

  5. Tez No

    84468

    İki boyutlu tonlamadan üç boyutlu görüntünün oluşturulması

    Formation of three dimentional image from two dimentional shading

    SELÇUK CANBEK

    Doktora

    Türkçe

    Türkçe

    1999

    MatematikEskişehir Osmangazi Üniversitesi

    Uygulamalı Matematik Ana Bilim Dalı

    PROF. DR. M. ŞAHİN KOÇAK

Geri Dön