OpenStreetMap haritalar kurye/lojistik simülasyon yazıyorum ve aşağıdaki resimdeki gibi Bir* temel algoritma büyük haritalar (Londra gibi) için yeterince hızlı olacak olmadığını anladı.

Yeşil düğümleri karşılık gelecek olanlar vardı koymak aç/set öncelik sırası ve nedeniyle çok sayıda (tüm harita gibi bir şey 1-2 milyon), 5 saniye alır ya da öylesine bulmak için rota resimde. Rota başına 100 MS civarında ne yazık ki benim mutlak sınırı ile ilgili.

Şu anda, düğümler bitişiklik listesi ve 100x100 2B uzamsal bir dizi hem de saklanır.

Eğer daha hızlı sorgular için rota uygulandı, gerekirse önişleme zaman, mekan ve değiş tokuş yapabileceğim yöntemler arıyorum. Tahmini maliyet için düz çizgi Haversine formülü profiler göre en pahalı fonksiyonu - temel benim* elimden geldiğince optimize var.

Örneğin, rasgele bir düğüm X 2 boyutlu dizinin her çeyreğinden seçtim ve her arasında Bir* çalıştırın, sonraki simülasyonları için diske rotaları kaydedebiliyor düşünüyordum. Sorgularken,* Bir arama yalnızca açılarda, önceden hesaplanan güzergah ve X arasında çalıştırabilirsiniz

Yukarıda tarif ettiğim şey daha rafine bir versiyonu ya da devam etmeli miyim farklı bir yöntem olabilir. Çok teşekkürler!

Kayıt için, burada rastgele seçilmiş düğümler 10 çift arasında keyfi tahmini maliyet ağırlık ve yol bilgisayar için bazı deney sonuçları

Weight // AvgDist% // Time (ms)
1       1       1461.2
1.05    1       1327.2
1.1     1       900.7
1.2     1.019658848     196.4
1.3     1.027619169     53.6
1.4     1.044714394     33.6
1.5     1.063963413     25.5
1.6     1.071694171     24.1
1.7     1.084093229     24.3
1.8     1.092208509     22
1.9     1.109188175     22.5
2       1.122856792     18.2
2.2     1.131574742     16.9
2.4     1.139104895     15.4
2.6     1.140021962     16
2.8     1.14088128      15.5
3       1.156303676     16
4       1.20256964      13
5       1.19610861      12.9

Şaşırtıcı 1.1 katsayısı neredeyse yarı yarıya artan yürütme zaman aynı yolu tutmak iken.

Çok daha hızlı ulaşım takas yapmak gerekir. Vikipedi Admissibility and optimality bkz.

Fikir bir çözüm 1 epsilon kez en iyi yol daha kötü bir yol olacak, ama daha az düğüm algoritması tarafından kabul edilmesine neden olacak epsilon değeri kullanmaktır. Bu verilen çözüm her zaman 1 epsilon times en iyi yol olacak anlamına gelmez unutmayın. Bu en kötü durum. Senin sorunun için uygulamada davranacaktı tam olarak bilmiyorum, ama denemeye değer olduğunu düşünüyorum.

Wikipedia'da bu fikri kullanan algoritmaları bir dizi verilir. Bu algoritma geliştirmek için en iyi bahistir ve hala iyi yolları dönerken zaman sınırı içinde çalıştırmak için bir potansiyele sahip olduğuna inanıyorum.

Senin algoritma 5 saniye içinde düğümler milyonlarca ile anlaşma yok çünkü sen de uygulanması için ikili kümeler kullanmak varsayıyorum, doğru mu? Eğer bunları el ile uygulanan, basit bir dizi olarak uygulanır ve ikili kümeler olduğundan emin olun.