Nasıl harita sağlayıcıları (Google veya Yahoo! Haritalar) tarifi? öneririz

Muhtemelen kesinlikle mesafeler ama aynı zamanda sürüş hızları, kaldırımlar varlığı, tren programları, vs. gibi şeyler de dahil olmak üzere belki de bir şekilde gerçek-dünya veri var. Ama veriler daha kolay bir biçimde olduğunu varsayalım, diyelim ki kenar ağırlıkları mesafeler yansıtan çok geniş yönlendirilmiş bir grafik. Hızlı bir şekilde başka bir keyfi noktasından yön hesaplamak için güçlü olmak istiyorum. Bazen bu noktalar bazen birbirinden uzak (cross-country) olacak iken birlikte (şehir içinde) yakın olacaktır.

Dijkstra'nın algoritması gibi grafik algoritmaları grafik çok büyük olduğu için çalışmaz. Neyse ki, Bir* gibi sezgisel algoritmalar muhtemelen çalışacaktır. Ancak, bizim veri çok yapısal ve belki de katmanlı yaklaşım bir çeşit işe yarayabilir? (Örneğin, deposu "anahtar" birbirinden uzak noktalar, bazı yerel yön olarak. bazı yönleri arasında önceden hesaplanan O zaman daha uzak noktaları iki yön için anahtar nokta, bir başka önemli nokta küresel yön, ve sonra yerel yol tarifi için yerel yöne tekrar içerecektir.)

Algoritma aslında pratikte ne kullanılır?

PS. Bu soruyu çevrimiçi harita yön bulma acayip motive oldu. Üçgen eşitsizliği tersine, bazen Google Maps X-Z daha uzun sürer ve daha uzağa daha X-Y-Z gibi bir ara nokta olduğunu düşünüyor. Ama belki de onların yürüyen başka bir parametre için de optimize yönde?

PPS. Burada katmanlı yaklaşım bir çeşit kullanın önerir Üçgen eşitsizliği başka bir ihlali (bana): X-Z karşı X-Y-Z. Eski biraz yoldan bile olsa ünlü Boulevard de Sebastopol kullanmak gibi görünüyor.

EditBu örneklerin hiçbiri artık çalışmıyor gibi görünüyor, ama her ikisi de orijinal yazı sırasında yaptı.

18 ay yönlendirme algoritması üzerinde çalışan dahil eşleme bir şirkette çalışarak geçiren biri olarak söylüyorum... Evet, Dijkstra's çalışır, değişiklikleri bir çift ile:

• Dijkstra's daha iyi bir kaynak için hedef yapmak yerine, her sondan başlar, ve onlar karşılayacak kadar iki taraf da genişletmek ortada. Bu kabaca işin yarısını (2*pi*(r/2)^2 vs pi*r^2) ortadan kaldırır.
• Önlemek için keşfetmek Arka Sokaklar her şehir arasında kaynak ve hedef, sen-ebilmek var birkaç tabakadan harita verileri: 'Karayolları' katmanı içeren tek Karayolları, bir 'ikincil' katman içeren yalnızca ikincil sokaklar ve benzeri. Sonra, daha ayrıntılı katmanları, gerektiği gibi genişleyen küçük bölümler sadece keşfetmek. Belli ki bu açıklama bir çok detay dışında bırakır, ama fikir olsun.

Bu doğrultuda değişiklikler, hatta cross-country çok makul bir zaman dilimi içinde yönlendirme yapabilirsiniz.