Maze Router: Collected Techniques

Abstract

ABSTRACT: In this thesis, Maze Router Problem (MRP) solved by using Connected Component Labeling, Depth First Search, Lee and A* Algorithms. The main goal of this research is to find a complete set of path which directs an agent to move from the Source node in the Maze towards a Target node in a Single-layer routing environment. In experiments different sized Maze Router Problem (MRP) instances are solved by using different Algorithms. From the results obtained we can conclude that Lee and A* Algorithms finds the shortest path for all the problem instances. It can also be concluded that A* Algorithm is the fastest Algorithm that finds the shortest path. Keywords: Maze, Maze Router, Maze Router Problem, Connected Component Labeling Algorithm, Depth First Search Algorithm, Lee Algorithm, A* Algorithm. ………………………………………………………………………………………………………………………… ÖZ: Bu tezde, Labirent Yönlendirici Problemi (LYP) Bağlı Bileşen Etiketleme, Derin Öncelikli Arama, Lee ve A* Algoritmaları kullanılarak çözülmüştür. Bu araştırmanın temel amacı, tek katmanlı Labirent yönlendirme ortamında başlangıç düğümünden hedef düğümüne ulaşılabilecek tam bir yolun bulunmasıdır. Farklı boyutlarda bulunan Labirent Yönlendirme problemlemi örnekleri farklı algoritmalar kullanılarak çözüldü. Elde edilen sonuçlara göre Lee ve A* algoritmaları kullanılan örnekler için en kısa youlu veren algoritmalar olmuşlardır. Aynı zamanda A* algoritmasının en kısa youlu en hızlı zamanda bulduğu tesbit edilmiştir. Anahtar Kelimeler: Labirent, Labirent Yönlendirme, Labirent Yönlendirme Problemi, Bağlı Bileşen Etiketleme Algoritması, Derin Öncelikli Arama Algoritması, Lee Algoritması, A* Algoritması.