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: Belirtilmemiş.
- 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ı: 113
Ö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. Anahtar Kelimeler : En Kısa Yol, Dijsktra, Öncelikli Kuyruk, Coğrafi Bilgi Sistemleri (GIS), Zaman Karmaşıklığı. vu
Ö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. Keywords : Shortest Path, Dijsktra, Priority Queue, Geographic Information Systems (GIS), Time Complexity.
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
- Dezavantajlı bireylerin aktivitelerini kontrol eden görüntü algılama platformunun gerçekleştirilmesi
Implementing the image detection platform that controls the activities of disadvantaged individuals
SADRETTİN KABAK
Yüksek Lisans
Türkçe
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ SERKAN AYDIN
- Deprem yalıtım sistemlerinin çok katlı yapılara uygulanması
Implementing the earthquake insulation systems to multistorey buildings
MAHSUM AKTEKİN
Yüksek Lisans
Türkçe
2019
Deprem MühendisliğiFırat Üniversitesiİnşaat Mühendisliği Teknolojileri Ana Bilim Dalı
PROF. DR. CENGİZ POLAT
- 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 general measures of the European Court of Human Rights judgments: The case of Moldova
Avrupa İnsan Hakları Mahkemesi kararlarının genel önlemlerinin uygulanması: Moldova örneği
IRINA CRIVET