1.   Google Maps ve Yandex Maps

Google Haritalar ve Yandex Haritalar, harita sunucusu olarak tanımlayabileceğimiz bir teknolojiye dayanmaktadır. Harita sunucuları coğrafi veriler içeren bir veritabanı ile birleştirilebilir (Resim 1). Bir harita görüntüleme istemcisi ve coğrafi veritabanının birleşmesi Coğrafi Bilgi Sistemi(Geographical Information System) (GIS) olarak adlandırılır. Coğrafi bilgi sistemi (CBS), her türlü veriyi oluşturan, yöneten, analiz eden ve haritalandıran bir sistemdir. CBS, konum verilerini (nesnelerin olduğu yer) her tür açıklayıcı bilgiyle bütünleştirerek verileri bir haritaya bağlar. Bu, bilimde ve hemen hemen her endüstride kullanılan haritalama ve analiz için bir temel sağlar. CBS, kullanıcıların kalıpları, ilişkileri ve coğrafi bağlamı anlamalarına yardımcı olur. 

Coğrafi veritabanında veriler vektörel olarak saklanır. Vektörel veri modelinde, nokta, çizgi ve poligonlar (x,y) koordinat değerleriyle kodlanarak depolanırlar. Nokta özelliği gösteren bir elektrik direği tek bir (x,y) koordinatı ile tanımlanırken, çizgi özelliği gösteren bir yol veya akarsu şeklindeki coğrafik varlık birbirini izleyen bir dizi (x,y) koordinat serisi şeklinde saklanır. Poligon özelliğine sahip coğrafik varlıklar, örneğin imar adası, bina, orman alanı, parsel veya göl, kapalı şekiller olarak, başlangıç ve bitişinde aynı koordinat olan (x,y) dizi koordinatlar ile depolanır. Vektörel model coğrafik varlıkların kesin konumlarını tanımlamada son derece yararlı bir modeldir.

2. Haritalar Hangi Algoritmaları Kullanıyor?

2.1. Google

Google haritaları, kaynaktan (A noktası) hedefe (B noktası) giden en kısa yolun hesaplanması için Grafik veri yapılarını kullanır[1]. Grafik veri yapısı, çeşitli düğümlerden ve bu düğümleri birbirine bağlayan çoklu kenarlardan oluşur. Dijkstra algoritması, Edsger Dijkstra tarafından belirli bir hedefe ulaşmak için en kısa mesafeyi ve yolu seyretmek için önerilen etkili ve yetkin bir algoritmadır. Grafiğin düğümleri, oraya ulaşmak için geçilmesi gereken mesafeyi temsil eden ağırlıklı kenarlarla birbirine bağlanır. Lakin Google haritaları devasa bir veriyle ilgilenir, bu nedenle grafikteki düğüm sayısı sayısızdır. Bu nedenle, Dijkstra algoritması gibi grafik algoritmaları, artan zaman ve uzay karmaşıklığı nedeniyle başarısız olabilir. Grafiğin boyutundaki büyük artış, algoritmanın verimliliğini sınırlar. A* algoritması gibi buluşsal algoritmaların uygulanabilir olduğu kanıtlanmıştır.

A* Algoritması, daha iyi ve daha verimli bir yolda gezinmek için buluşsal bir işlev kullanan Dijkstra algoritmasına benzer. A* algoritması diğerlerinden daha iyi olduğu varsayılan düğümlere (zaman gereksinimi, mesafe ve diğer parametreler gibi) diğerlerinden daha yüksek öncelik verir, Dijkstra ise tüm düğümleri araştırır. Bu nedenle, Dijkstra algoritmasından daha hızlı olması amaçlanmıştır. Düğüm başına bellek gereksinimi ve işlemler daha fazladır, çünkü çok daha az düğümü araştırır ve kazanç her durumda iyidir. [2]

2.2. Yandex

Yandex Maps  rota hesaplarken Dijkstra Algoritmasını kullandığını açıklamıştır [3].  Rotalar nasıl oluşturulur? Rotalar Dijkstra Algoritmasına göre oluşturulur. Onun yardımıyla sistem, her bölümün uzunluğuna ve bu kısımdaki hareket hızına bağlı olarak en hızlı rotayı hesaplar. Bir kullanıcı trafik sıkışıklığını hesaba katmadan bir rota oluşturmayı seçerse, algoritma her segmentteki ortalama hızı kullanır. Kullanıcı trafik durumunu dikkate alarak bir yere en hızlı nasıl ulaşacağını bilmek isterse, algoritma mevcut trafik koşullarıyla ilgili verileri kullanır. Ayrıca yol durumunda ki değişiklik, yolun kapalı olması gibi durumlarda Yandex kendi algoritmasını kullanır. Bu sistem, bir aracın hareketinin (otomatik olarak sürücüler tarafından sağlanan bilgiler) yol ağı bilgileriyle eşleşmediği durumlarda olayları kaydeder. Bir sürücünün yol kenarına düzensiz bir şekilde durduğu veya beklenmeyen bir dönüş yaptığı tek seferlik bir durum değilse, trafik düzeni değişmiş olabilir. Tüm bu durumlar analiz edilir ve ardından yol grafiğinde değişiklikler yapılır.

REFERANSLAR