Implementing the dijsktra's algorithm with priority queue to the path finding problem in raster gıs
Dijsktra algoritmasının öncelikli kuyruk ile gerçekleştirme yöntemini kullanarak hücresel CBS'de rota bulmak
- Tez No: 153441
- Danışmanlar: YRD. DOÇ. DR. ZUHAL AKYÜREK
- Tez Türü: Yüksek Lisans
- Konular: Jeodezi ve Fotogrametri, Geodesy and Photogrammetry
- Anahtar Kelimeler: En Kısa Yol, Dijsktra, Öncelikli Kuyruk, Coğrafi Bilgi Sistemleri (GIS), Zaman Karmaşıklığı. vu, Shortest Path, Dijsktra, Priority Queue, Geographic Information Systems (GIS), Time Complexity
- Yıl: 2004
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Jeodezi ve Coğrafi Bilgi Teknolojileri Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
oz DIJSKTRA ALGORİTMASININ ÖNCELİKLİ KUYRUK İLE GERÇEKLEŞTİRME YÖNTEMİNİ KULLANARAK HÜCRESEL CBS'DE ROTA BULMAK Hakbilir, Muzaffer Yüksek Lisans, Jeodezi ve Coğrafi Bilgi Teknolojileri Yüksek Lisans Proje Yöneticisi : Yrd. Doç. Dr. Zuhal Akyürek Nisan 2004, 98 sayfa Coğrafi Bilgi Sistemleri (CBS) ile ağ analizleri genellikle ulaşım problemlerine çözümler getirir. Gerçek dünya, CBS ile iki konumsal modelden (vektör-tabanlı, hücre- tabanlı) biri ile ifade edilir. Vektör veya hücre-tabanlı CBS'lerinin tercih edilmesi, hassasiyet probleminden çok tercih problemidir. Hücre tabanlı CBS modeli, önceden tanımlanmış rotaların bulunmadığı zaman arazi üzerinde rota bulma problemi için daha uygun görülmektedir. Bu çalışmada kullanılmış olan yaklaşım, problemin hücresel harita üzerindeki maliyet fonksiyonu ile,“minimum maliyetli yol”grafiği problemine dönüştürülmesidir. Bazen hücre tabanlı CBS'lerinde iki yer arasındaki en kısa yol gerçek zamanlı olarak hesaplanabilir. Bu yüzden gerçek ağlar üzerinde, hangi“en kısa yol bulma”algoritmasının en hızlı çalışacabileceğini bilmek gerekmektedir. Bu gereksinimi karşılayabilmek için, Dijsktra algoritmasının öncelikli kuyruk yapısı ile gerçekleştirimi yöntemi tercih edilmiştir. Çünkü, bu Dijsktra algoritmasının zaman karmaşıklığını“0(V2 log V)”den“0(E log V )”ye düşürmektedir. Farklı sayıda düğüm ve bağlantılardan oluşan belli bir sayıdaki hücre tabanlı CBS katmanı; Dijkstra algoritması, Dijsktra algoritmasının öncelikli kuyruk yapısı ile gerçekleştirimi yöntemi ve ArcMap programının Spatial Analyst aracının çalışma zamanlarına göre karşılaştırılmışlardır. Dijsktra algoritmasının öncelikli kuyruk yapısı ile gerçekleştirme vıyöntemi ve ArcMap programının Spatial Analyst aracında, düğüm sayısı ve zaman arasında doğrusal bir ilişki görülmektedir buna karşın, Dijsktra algoritmasında ikinci dereceden bir ilişki sergilenmektedir. Sonuç olarak, grafik içerisindeki düğüm ve bağlantı sayısı arttıkça, Dijsktra algoritmasının çalışma zamanı performansı belirgin bir şekilde düşmektedir.
Özet (Çeviri)
ABSTRACT IMPLEMENTING THE DIJSKTRA'S ALGORITHM WITH PRIORITY QUEUE TO THE PATH FINDING PROBLEM IN RASTER GIS Hakbilir, Muzaffer M.S.,Geodesy & Geographic Information Technologies Supervisor: Assist.Prof.Dr. Zuhal Akyürek April 2004, 98 pages Network analysis in GIS is often related to finding solutions to transportation problems. In a GIS the real world is represented by either one of two spatial models, vector-based, or raster-based. Prefering raster or vector GIS is more a question of choice than of accuracy. A raster-based GIS model shows a better fit, when the problem is concerned with finding a path across terrain which does not have predefined paths. The approach of this study is to translate the scenario into a 'least-cost path' graph with an associated cost function on the raster-based GIS layer. Sometimes, computation of shortest paths between different locations on a raster-based GIS has to be done in real time. Therefore, knowing which shortest path algorithm runs fastest on real networks is needed. In order to meet this requirement, Dijsktra's algorithm with priority queue implementation is selected, because it reduces the time complexity of Dijsktra's algorithm from 0(V2 log V) to 0(E log V ). The run-time results of Dijsktra's algorithm, Dijsktra's algorithm with priority queue implementation and ArcMap Spatial Analyst Tool are compared for a number of raster GIS layers which have different number of nodes. Dijsktra's algorithm with priority queue implementation and Spatial Analyst tool of ArcMap show a linear relationship between node numbers and time, whereas Dijsktra's algorithm represents a quadratic relationship. Hence, when the IVnumber of nodes and edges in graph is increased, the run-time performance of the Dijsktra's algorithm decreases rapidly.
Benzer Tezler
- Dinamik ortamlar için yeni bir gerçek zamanlı evrimsel seyrüsefer planlama ve güdümleme sistemi
A new real time evolutionary navigation planning and guidance system for dynamic environments
FERHAT UÇAN
Doktora
Türkçe
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. DENİZ TURGAY ALTILAR
- Otonom robot ile iç mekana uygun rota planlama uygulaması
Route planning application for indoor spaces using an autonomous robot
ARDA KÖSEOĞLU
Yüksek Lisans
Türkçe
2026
Elektrik ve Elektronik MühendisliğiSamsun ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ TUNCAY SOYLU
- Implementing the European language passport standards into the advanced reading course at the elt department,Gazi University
Avrupa dili pasaportu standartlarının Gazi Üniversitesi İngiliz Dili Eğitimi bölümündeki ileri okuma derslerine uygulanması
CANAN TERZİ
Yüksek Lisans
İngilizce
2006
Eğitim ve ÖğretimGazi Üniversitesiİngiliz Dili ve Edebiyatı Ana Bilim Dalı
PROF. DR. AYDAN ERSÖZ
- Implementing the European language passport standards into speaking course at the elt department, Gazi University
Avrupa dil pasaportu standartlarınının gazi üniversitesi İngiliz Dili Eğitimi bölümündeki konuşma derslerine uygulanması
BURTAY HATİCE EROĞLU
Yüksek Lisans
İngilizce
2006
İngiliz Dili ve EdebiyatıGazi Üniversitesiİngiliz Dili Eğitimi Ana Bilim Dalı
PROF. DR. AYDAN ERSÖZ
- Implementing the paillier cryptosystem on constrained microcontrollers for smart grid applications
Akıllı şebeke uygulamaları için kısıtlı microcontrollers üzerinde paillier şifrelemesi uygulanması
ABDELRAHMAN ALKHODARY
Yüksek Lisans
İngilizce
2016
Elektrik ve Elektronik MühendisliğiBahçeşehir ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SELÇUK BAKTIR