Geri Dön

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

  1. Tez No: 153441
  2. Yazar: MUZAFFER HAKBİLİR
  3. Danışmanlar: YRD. DOÇ. DR. ZUHAL AKYÜREK
  4. Tez Türü: Yüksek Lisans
  5. Konular: Jeodezi ve Fotogrametri, Geodesy and Photogrammetry
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2004
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Jeodezi ve Coğrafi Bilgi Teknolojileri Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    Türkçe

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. DENİZ TURGAY ALTILAR

  2. 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

    Türkçe

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ SERKAN AYDIN

  3. 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

    Türkçe

    2019

    Deprem MühendisliğiFırat Üniversitesi

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

    PROF. DR. CENGİZ POLAT

  4. 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

    İngilizce

    2006

    İngiliz Dili ve EdebiyatıGazi Üniversitesi

    İngiliz Dili Eğitimi Ana Bilim Dalı

    PROF. DR. AYDAN ERSÖZ

  5. 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

    Yüksek Lisans

    İngilizce

    İngilizce

    2016

    HukukKoç Üniversitesi

    Kamu Hukuku Ana Bilim Dalı

    DOÇ. DR. BAŞAK ÇALI