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

    413244

    Mutual impedance considerations in two dimensional planar acoustic arrays with square piston elements

    İki boyutlu düzlemsel akustik dizinlerde kare piston elemanlar için karşılıklı empedans değerlendirmeleri

    MUSTAFA OĞUZHAN SAÇMA

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

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

    PROF. DR. HAYRETTİN KÖYMEN

  3. Tez No

    413460

    İki boyutlu çerçevelerin matris deplasman metodu ile plastik analizi

    Plastic analysis of two-dimensional frames by matrix displacement method

    YUNUS ÜNAL

    Yüksek Lisans

    Türkçe

    Türkçe

    2015

    İnşaat MühendisliğiDumlupınar Üniversitesi

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

    PROF. DR. MEHMET TEVFİK BAYER

  4. Tez No

    414297

    İki ve üç boyutlu glioblastoma multiforme hücre kültürlerinde (U-87 MG, T98G) kabazitaksel'in hücresel etkilerinin karşılaştırılmalı analizi

    Comparative analysis of cabazitaxel's cellular effects on two- and three-dimensional glioblastoma multiforme (U-87 MG, T98G) cell cultures

    ÖZGE ÖZER

    Yüksek Lisans

    Türkçe

    Türkçe

    2015

    BiyolojiCelal Bayar Üniversitesi

    Biyoloji Ana Bilim Dalı

    PROF. DR. SELİM UZUNOĞLU

  5. Tez No

    243602

    İki boyutlu bir brülörde yanmanın hesaplamalı akışkanlar dinamigi ile incelenmesi

    The analysis of burning in a two dimensional burner with using computational fluid dynamics

    ERMAN ÖZEN

    Yüksek Lisans

    Türkçe

    Türkçe

    2009

    Makine MühendisliğiYıldız Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. OKTAY ÖZCAN

Geri Dön