Google Haritalar tartışmasız şimdiye kadarki en ünlü harita uygulamalardan biridir. Yıllar geçtikçe, Google Haritalar gezinme şeklimizi değiştirdi ve A noktasından B noktasına ulaşmak için dijital bir harita kullanmayı normal hale getirdi.
Daha önce hiç gitmediğiniz yerleri ziyaret etmek artık çok daha kolay hale geldi. Tek yapmam gereken Google Haritalar’ı çıkarıp yönümü bulmak.
A noktasından B noktasına ulaşmak için bir rota bulma işleminde yer alan algoritmaların hemen hemen hepsinin grafik tabanlı algoritmalar olduğunu unutmayın. Bu nedenle, grafik veri yapısının ve uygulamasının temellerine bakacağız.
Nasıl Çalışır?
Google Haritalar, onu genel olarak bir harita sunucusu olarak tanımlayabileceğimiz bir teknolojiye dayanmaktadır. Harita sunucusu, tüm gezegeni kapsayan geniş bir önceden oluşturulmuş harita döşeme görüntülerinden istenen konum için bir harita oluşturur.
Harita sunucusu bunun üzerine başka veritabanlarından gelen veriyi kaplayabilir. Bir harita görüntüleyici istemcisi ile coğrafi veritabanının birleşimi geleneksel olarak Coğrafi Bilgi Sistemi(Geographical Information System) (GIS) olarak adlandırılır.
Google Haritalar, gezegendeki tüm alanlar hakkında bilgi toplayamadı ve bu nedenle , Google Maps veya Google Earth’ü iyileştirecek yetkili vektör verilerine sahip kuruluşların bunları kullanabilmeleri için sağlamalarına olanak tanıyan bir Temel Harita Ortak Programı geliştirdiler.
Google, Temel Harita Ortak Programının yanı sıra, her caddede, mahallede ve konut kompleksinde devriye gezmek için araçlardan günün her saatinde yararlanıyor ve ayrıntılı dijital görüntüler sağlıyor.
Google Haritalar’da kullanılan algoritmalar
Google Haritalar’da gördüğümüz sonuçlarda yüksek performanstan doğruluğa kadar bugünün sonucuna ulaşmak Google Haritalar ekibinin uzun zaman aldı.
Kullanılan ana haritalama algoritması Grafik Algoritmasıdır. Ancak kullanılan herhangi bir algoritma ile sorun yine de izlenecek rotaların ağırlıklarını bulmak olacaktır.
En iyi rotayı bulma sorunu, aşağıdaki gibi bazı soruları gündeme getirdi:
- Belirli bir rotanın ağırlığı nedir?
- İlk denememse bu ağırlığı nasıl ölçebilirim?
- Ağırlıklar nasıl atanır?
- Sokak türlerine öncelik vermek zorunda mıyız?
Hızlı Rota Planlama Algoritmaları
Yukarıdaki sorular, Dijkstra’nın algoritmasına çok benzeyen, ancak algoritmayı çalıştırmadan önce bazı değişiklikler ve yardımcı işlemlerle özelleştirilmiş algoritmalara yol açtı.
Ana fikir, ileride çok hızlı hesaplanabilmesi için aşağıdaki sorguları hızlandırmak için grafik üzerinde bir kez ön işlem yapmaktır.
Bu algoritmalar hakkında daha fazla ayrıntı öğrenmek için Engineering Fast Route Planning Algorithms * araştırma makalesini okumanızı şiddetle tavsiye ederim .
Google Haritalar ve Diğer Harita sunucularında kullanılan diğer Algoritmalar
1- Dijkstra Algoritması
Dijkstra Algoritması, bir düğüm (hangisini siz seçersiniz) ve grafikteki diğer her düğüm arasındaki en kısa yolu hesaplamanıza olanak tanır .
Çok fazla bahsetmiyorum çünkü ayrıntılı yazısı gelecek 🙂
2- Öncelik Sıraları
Öncelik sırası temel olarak öğelerinin her birine öncelik veren bir kuyruktur.
Bununla birlikte, pratikte, öncelikli kuyrukların büyük kara yol ağlarının performansı üzerindeki etkisi oldukça sınırlıdır.
3- Çift Yönlü Arama
Dijkstra’nın algoritmasını aynı anda kaynaktan ileri ve hedeften geriye doğru yürütür.
Her iki yönden de bazı düğümler ziyaret edildiğinde, en kısa yol halihazırda toplanan bilgilerden türetilebilir.
4- Geometrik Hedefe Yönelik Arama (A *)
Birçok engeli olan kare bir ızgarayı düşünün ve bize bir başlangıç hücresi ve bir hedef hücre verildi.
Hedef hücreye (mümkünse) başlangıç hücresinden olabildiğince çabuk ulaşmak. Burada A * arama algoritması, kullanımını Google Haritalar’da buldu.
Son düşünceler
Haritalar ve algoritmaları, çok zor NP-hard Bilgisayar Bilimleri problemleri içerdiğinden, teknolojinin en karmaşık parçalarından biridir .
Normalde daha fazla hesaplama gücüyle çözülemeyen sorunlar, yalnızca ön işlemeyi içeren tekniklerin karıştırılmasıyla çözülebilir.
Bilgisayar biliminin çözülmemiş en büyük sorunlarından birini anlamak için P vs NP hakkında çok güzel bir Youtube videosu var .