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: 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
  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ı: 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

  1. Tez No

    190947

    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

    İngilizce

    2006

    Eğitim ve ÖğretimGazi Üniversitesi

    İngiliz Dili ve Edebiyatı Ana Bilim Dalı

    PROF. DR. AYDAN ERSÖZ

  2. Tez No

    215361

    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

  3. Tez No

    92805

    Implementing sheltered content instruction in an ELT classroom

    İçeriğe dayalı öğretimin İngilizce derslerinde uygulanması

    CAROLİNA CYRENİA SAKİNA BWANALI

    Yüksek Lisans

    İngilizce

    İngilizce

    2000

    Eğitim ve ÖğretimGazi Üniversitesi

    İngiliz Dili Eğitimi Ana Bilim Dalı

    DOÇ. DR. ABDULVAHİT ÇAKIR

  4. Tez No

    109627

    Developing the human resources and implementing the personnel information system of the organizations in the restructuring process

    Yeniden yapılanma sürecinde organizasyonların insan kaynaklarının geliştirilmesi ve personel bilgi sisteminin oluşturulması

    ASİL ALKAYA

    Yüksek Lisans

    İngilizce

    İngilizce

    2001

    Endüstri ve Endüstri MühendisliğiDokuz Eylül Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. EDİP TEKER

  5. Tez No

    98382

    Savaş stratejilerinin iş dünyasında uygulanması

    Implementing war strategies in business world

    NACİ ÖZGÜR ÖZEL

    Yüksek Lisans

    Türkçe

    Türkçe

    1999

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    DOÇ.DR. TUFAN KOÇ

Geri Dön