A * Çok büyük grafikler için algoritma, kısayol önbelleğe alma konusunda herhangi bir düşünceniz var mı?

OpenStreetMap haritalarına kurye/lojistik simülasyonu yazıyorum ve aşağıda gösterildiği gibi temel A * algoritmasının büyük haritalar (Greater London gibi) için yeterince hızlı olmayacağını anladım.

http://i.imgur.com/u2tVpML.jpg

Yeşil düğümler açık küme/öncelik sırasına yerleştirilenlere karşılık gelir ve devasa sayı nedeniyle (tüm harita 1-2 milyon gibi bir şeydir), resimde gösterilen rotayı bulmak 5 saniye kadar sürer. Maalesef rota başına 100ms mutlak limitim hakkında.

Şu anda, düğümler hem bitişik bir listede hem de uzamsal bir 100x100 2D dizisinde depolanmaktadır.

Daha hızlı sorgular için ön işleme zamanından, alandan ve gerekirse rotanın iyileştirilmişliğinden faydalanabileceğim yöntemler arıyorum. Sezgisel maliyet için düz çizgi Haversine formülü, profilleyiciye göre en pahalı fonksiyondur - Temel A * 'yı mümkün olduğunca optimize ettim.

Örneğin, 2B dizisinin her çeyreğinden rastgele bir X düğümü seçip her birini A * çalıştırıp çalıştırmayacağımı düşünüyordum, izleyen simülasyonlar için yolları diskte saklayabilirim. Sorgulama yaparken, önceden hesaplanmış rota ile X arasında geçiş yapmak için A * aramasını yalnızca kadranlarda çalıştırabilirim.

Yukarıda tarif ettiklerimin daha rafine edilmiş bir versiyonu var mı yoksa belki de takip etmem gereken farklı bir yöntem var mı? Çok teşekkürler!

Kayıt için, sezgisel maliyetin keyfi olarak ağırlıklandırılması ve rastgele seçilmiş 10 çift düğüm arasındaki yolun hesaplanması için bazı temel 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ı bir şekilde katsayısını 1.1'e yükseltmek, aynı rotayı korurken yürütme süresini neredeyse yarıya indirdi.

64
Bunu yapmanın bir yolu olmalı, çünkü çevrimiçi haritalama ürünleri dünya üzerinde anında bir rota hesaplayabilir.
katma yazar usr, kaynak
@IVlad En uygun olduğundan şüpheliyim. OP, optimallik gerektirmiyor. İspanya'nın güneyinden Rusya'nın son miline kadar olan bir rota hakkında düşünüyordum. 40h bir sürücüye ve 4000km'ye sayfa yüklemek için yaklaşık 2 saniye sürdü.
katma yazar usr, kaynak
Grafiği "Arc-Flags" kullanarak önceden işlemeyi deneyin; oldukça basit ve ayrıca size güzel bir hız vermelidir.
katma yazar Mehrdad, kaynak
Bence orada sormayı denemelisin: cs.stackexchange.com
katma yazar Wojciech Kulik, kaynak
Tam bir cevap yazmak için zamanınız yok, ancak sanatın durumu küçük ayırıcılar bulmaktan geçiyor. Yaklaşık sonuçlar için yetinmeyin - hata ayıklamak çok can sıkıcı.
katma yazar David Eisenstat, kaynak
@scai: Popüler yönlendiriciler kesinlikle A * kullanmazlar. Daha önceki işverenimde matematiği yaptık ve sporcular için uzun rotalarda rota yeniden hesaplamanın A * ile açıklanamayacak kadar hızlı olduğunu gördük. Bununla birlikte, Kontraksiyon Hiyerarşileri'ni kullanmadıklarından şüphelendik. Bu biraz modası geçmiş.
katma yazar MSalters, kaynak
Her segment için ağırlıklandırılmasına izin veren algoritmada yapılan bir değişiklik (örneğin, 8 şeritli otoyollar birim mesafe başına 1 maliyete sahipken, asfaltsız kir izleri 50 maliyete sahiptir ve arasındaki her şey ... olası başlangıç ​​noktası. O zaman harita sağlayıcısından aldığınız tüm bölümleri sınıflandırma görevine sahip olsanız da, bunlarla ilgili uygun veriler yoksa, ...
katma yazar twalberg, kaynak
@ usr - optimal olanı? Ve ne tür bir "dünya çapında rota" hakkında konuşuyoruz? Dünyanın her yerinde, muhtemelen arama alanını önemli ölçüde azaltan uçaklardan veya yolcu gemilerinden bahsediyoruz. OP sokaklarla uğraşıyor gibi gözüküyor.
katma yazar IVlad, kaynak
@ usr - ah, eğer optimal değilse, aslında oldukça kolaydır. OP'nin epsilon numarasıyla en uygun olmayan yolları bulmaya ne kadar hızlı başladığını görün. Daha iyi donanım ve başkalarının gönderdiği meraklısı yöntemler ile birlikte, kesinlikle çok çok iyi bir şey yapabilirsiniz.
katma yazar IVlad, kaynak
katma yazar Ordous, kaynak
@ usr Bu yönlendiricilerin yalnızca düz A * kullanmaları gerekmez, bunun yerine Kontraksiyon Hiyerarşileri yerine, onlarca ülkede ve yüzlerce kilometrede gerçekten hızlı bir şekilde rota oluşturmak için GraphHopper ve OSRM'ye bakın.
katma yazar scai, kaynak
code.google.com/p/ai-algorithmplatform/wiki/pathfinding de ilginç ve cayır cayır yanan hızlı çalışıyor. Temelde çok düzeyli A * ve kullanılmayan dörtlüleri kuru erik.
katma yazar Caramiriel, kaynak
Bire bir rotayla veya mesafe matrisini hesaplamakla ilgileniyor musunuz? Belki bazı ipuçlarını burada bulabilirsiniz: stackoverflow.com/questions/430142
katma yazar SebastianK, kaynak
Yer işaretleriyle A * yapabilirsiniz. Buradaki fikir, bir dönüm noktası alıp grafiğinizdeki tüm düğümlere olan uzaklığı dönüm noktasından önceden hesaplamanızdır. Ardından, bir arama sorgunuz olduğunda, bu verileri minimal olarak iyimser bir sezgisel buluşma üretmek için kullanırsınız (bakınız: kabul edilebilir ve tutarlı). Ayrıca "ulaşmayı" araştırmalısınız.
katma yazar Harrichael, kaynak

9 cevap

İyimserlikle işlem yaparak bunu daha hızlı yapabilmelisiniz. Wikipedia'daki Kabul edilebilirlik ve iyimserlik bölümüne bakın.

Buradaki fikir, 1 + epsilon 'dan daha kötü olmayan bir çözüme yol açacak bir epsilon değeri kullanmak; algoritması. Bunun, iade edilen çözümün her zaman en iyi yolun 1 + epsilon katı olacağı anlamına gelmediğini unutmayın. Bu sadece en kötü durum. Sorununuz için pratikte nasıl davranacağını tam olarak bilmiyorum, ama keşfedilmeye değer olduğunu düşünüyorum.

Bu fikre, wikipedia'ya dayanan bir takım algoritmalar verildi. Algoritmayı iyileştirmek için en iyi bahisin bu olduğuna ve hala iyi yollar döndürürken zaman sınırında çalışma potansiyeline sahip olduğuna inanıyorum.

Algoritmanız 5 saniyede milyonlarca düğümle uğraştığından, uygulama için ikili yığınlar kullandığınızı varsayıyorum. Bunları el ile uyguladıysanız, basit diziler olarak uygulandıklarından ve ikili yığınlar olduklarından emin olun.

22
katma
Günümüzde, (bellek kaynaklarındaki kısıtlamalar olmadıkça), kıtasal sorguların milisaniye cinsinden işlenebildiği durumlarda, iyilikle ticaret yapmak anlamsızdır.
katma yazar FrankS101, kaynak
@ drspa44 - .net kullanıyorsanız, paralellik eklemeyi denediniz mi? Belki bir düğümün komşularını güncelleyen kısma eklemeyi dene. Yardımcı olup olmayacağından emin değilim, ancak for döngüsünü bir Parallel.For ile değiştirmeye çalışıyorum.
katma yazar IVlad, kaynak
Orada bir şeyler yanlış olmalı. .net SortedList sıralı bir dizi kullanılarak uygulanır, ekleme/silme için O (n) vardır (her zaman dizinin altına öğeler eklemiyorsanız) ). Bir yığın, uygun şekilde uygulandığında, bunun yerine O (log n) 'ye sahiptir. Daha hızlı olmalı. Oldukça iyi bir max yığın uygulaması için orada kontrol edin: referanslar .microsoft.com/# System.Core/System/Linq/Paral & zwnj; lel/& hellip; A * için tam tersi yapmanız gerekir, ancak uyarlaması kolaydır.
katma yazar tigrou, kaynak
Paralel.ForEach'ı A * kullanacak olan varlıklarda kullanırım, bu nedenle tüm CPU gücü kullanılır. Küçük ölçekli paralelleşmenin, özellikle senkronizasyon ve ek yük ile çok fazla fark yaratacağını düşünmüyorum.
katma yazar drspa44, kaynak
Bir .net SortedList ve bir kütüphaneden bir dizi tabanlı ikili yığın kullanmayı denedim ve liste marjinal olarak daha hızlıydı.
katma yazar drspa44, kaynak
Teşekkürler, denemek için düşünmedim ve çok fazla ceza olmadan hızı biraz artırır. Sezgisel maliyeti 1,5 ile çarpmak, 5 saniyede 88,3km'ye kıyasla 200 ms'de 91,8km verir. Algoritma çalışırken bu değişkenliği daha da deneyeceğim.
katma yazar drspa44, kaynak

Çok fazla ön hesaplama yapan bu problem için özel algoritmalar var. Ön hesaplama, bellekten, A * 'nın düz çizgi mesafesinden çok daha doğru bir sezgisel üretmek için kullandığı grafiğe bilgi ekler. Wikipedia, http://en.wikipedia.org/wiki/Shortest_path_problem adresinde bir dizi yöntemin adını verir. #Road_networks ve Hub Etiketlemenin lider olduğunu söylüyor. Bununla ilgili hızlı bir arama, http://research.microsoft.com/pubs/ 142356/HL-TR.pdf . A * kullanarak daha eski bir sürüm http://research.microsoft adresindedir. .com/pub/64505/goldberg-sp-wea07.pdf .

Gerçekten Haversine kullanmaya ihtiyacınız var mı? Londra’yı örtmek için, düz bir dünya kabul edebileceğinizi ve Pisagor’u kullanabileceğinizi ya da her bağlantının uzunluğunu grafikte saklayabileceğinizi düşünürdüm.

9
katma
Basit bir düzlem projeksiyonu var: github.com/graphhopper/graphhopper/blob/master/core/src/main‌/& hellip; Ayrıca yorumdaki bağlantılara bakın.
katma yazar Karussell, kaynak
@ drspa44 - Haritayı yeniden düzenlemelisiniz (yerel merkezli bir enine Mercator projeksiyonu düşünün)!
katma yazar Deer Hunter, kaynak
Yerel olarak neredeyse düz bir Dünya için Haversine'yı öldürmek bir zorunluluktur. Upvoted.
katma yazar Deer Hunter, kaynak
Teşekkürler, onlara bir okuma yapacağım. Pisagor ne yazık ki çok kısa mesafelerden bile uzak olabilir. Dışarı atılması şaşırtıcı şekilde sık sık suboptimal yollara neden olur.
katma yazar drspa44, kaynak
katma yazar drspa44, kaynak

Microsoft Research'ün konuyla ilgili yazdığı gerçekten harika bir makale var:

http://research.microsoft.com/tr /features/shortestpath-070709.aspx

Orijinal kağıt burada barındırılıyor (PDF):

http: //www.cc.gatech. edu/~ thad/6601-gradAI-fall2012/02-arama-Gutman04siam.pdf

Temelde deneyebileceğiniz birkaç şey var:

  1. Hem kaynak hem de varış noktasından başlayın. Bu, kaynaktan dışa doğru hedefe geçerken gerçekleştireceğiniz israfın en aza indirilmesine yardımcı olur.
  2. Yer işaretlerini ve otoyolları kullanın. Temel olarak, her haritada genel olarak kullanılan yolları bulun ve bu noktalar arasında nasıl verimli bir şekilde gezileceğini belirlemek için ön hesaplama yapın. Kaynağınızdan bir yer işaretine, ardından diğer yer işaretlerine, ardından hedefinize bir yol bulabilirseniz, hızlı bir şekilde uygun bir rota bulabilir ve oradan en iyileştirebilirsiniz.
  3. "reach" algoritması gibi algoritmaları keşfedin. Bu, geçerli bir rota bulmak için dikkate alınması gereken tepe noktalarının sayısını en aza indirerek grafiği gezerken yapacağınız iş miktarını en aza indirmeye yardımcı olur.
6
katma
@ Yer işaretleri ile MSalters farklı bir canavar -> ALT
katma yazar Karussell, kaynak
Adım 2, Kontraksiyon Hiyerarşileri olarak bilinir.
katma yazar MSalters, kaynak
Teşekkürler. Bu makaleyi okudum ve bugün bazı önemli noktalar yaklaşımını uygulamak için yollar bulmaya çalışıyordum. Benim için sorun, sahip olduğum verilere dayanarak yer işaretlerinin nasıl seçileceğini bilmiyordu. Karayolları da benim için teşhis etmek o kadar kolay değil. Ulaşmayı denedim ama performans kazanımlarının önemsiz olduğunu gördüm. Microsoft'un resimlerine baktığımızda, iki yönlü Djikstra ve A *, şu an sahip olduklarımdan çok daha hızlı görünmüyor, ancak henüz uygulama yapmamıştım.
katma yazar drspa44, kaynak

GraphHopper does two things more to get fast, none-heuristic and flexible routing (note: I'm the author and you can try it online here)

  1. Çok açık olmayan bir optimizasyon, OSM düğümlerinin iç düğümlerle 1: 1 eşleşmesini önlemektir. Bunun yerine GraphHopper yalnızca düğümler olarak düğümleri kullanır ve kabaca çaprazlanan düğümlerin 1/8'ini kaydeder.
  2. A *, Dijkstra veya benzeri için etkili araçlara sahiptir. bir-çok Dijkstra. Bu, tüm Almanya'da 1 yaşın altındaki bir rotayı mümkün kılar. A * 'nın (sezgisel olmayan) çift yönlü sürümü bunu daha da hızlı hale getirir.

Bu yüzden size daha büyük Londra için hızlı yollar elde etmek mümkün olmalıdır.

Ek olarak, varsayılan mod, her şeyi bir büyüklük sırasına göre daha hızlı (örn. Avrupa geniş rotaları için 30ms) yapan ancak ön işleme gerektirdiğinden daha az esnek olan hız modudur ( Kasılma Hiyerarşileri ). Bundan hoşlanmıyorsanız, sadece devre dışı bırakın ve ayrıca arabanızın caddelerine ince ayar yapın veya kamyonlar için yeni bir profil oluşturun; örneğin; % 30 daha fazla artış sağlayacak servis sokaklarını ve izleri hariç tut. Her iki yönlü algoritmada olduğu gibi kolayca paralel bir arama yapabilirsiniz.

5
katma

Sanırım fikrini "kadran" ile hesaplamaya değer. Daha kesin olarak, buna düşük çözünürlüklü bir rota araması diyebilirim.

Yeterince yakın olan X bağlı düğümleri seçebilir ve bunları tek bir düşük çözünürlüklü düğüm olarak kabul edebilirsiniz. Tüm grafiğinizi bu tür gruplara ayırın ve düşük çözünürlüklü bir grafik elde edin. Bu bir hazırlık aşamasıdır.

Kaynaktan hedefe bir rota hesaplamak için önce ait oldukları düşük çözünürlüklü düğümleri tanımlayın ve düşük çözünürlüklü rotayı bulun. Ardından, yüksek çözünürlüklü grafikte rotayı bularak sonucunuzu iyileştirin, ancak algoritmayı yalnızca düşük çözünürlüklü rotanın düşük çözünürlüklü düğümlerine ait olan düğümlerle sınırlandırın (isteğe bağlı olarak, aynı zamanda bir derinliğe kadar olan komşu düşük çözünürlüklü düğümleri de düşünebilirsiniz ).

Bu aynı zamanda sadece yüksek/düşük değil çoklu çözünürlüklerde de genelleştirilebilir.

Sonunda optimal için yeterince yakın bir rota almalısınız. Yerel olarak en uygunudur, ancak çözünürlük atlayışına (yani bir düğüm grubu tek bir düğüm olarak tanımlandığında yaptığınız yaklaşım) bağlı olarak bir dereceye kadar küresel olarak optimalden biraz daha kötü olabilir.

4
katma
Teşekkürler, bu yaklaşımı takip edersem bu cevabı aklımda tutarım.
katma yazar drspa44, kaynak

Büyük bir Navigasyon şirketinde çalıştım, bu yüzden güvenle 100 msn Londra'da Atina'ya gömülü bir cihazda bile bir rota alması gerektiğini söyleyebilirim. Büyük Londra bizim için bir test haritası olurdu, çünkü elverişli bir şekilde küçük (RAM'e kolayca uyuyor - bu aslında gerekli değil)

Öncelikle, A * tamamen eskidir. Başlıca yararı, "teknik olarak" ön işleme tabi tutulmamasıdır. Uygulamada, yine de bir OSM haritasını önceden işlemeniz gerekir, bu yüzden bu anlamsız bir avantajdır.

Size büyük bir hız artışı vermek için ana teknik ark bayrakları. Haritayı 5x6 bölümlere bölerseniz, her bölüm için 32 bit tam sayıda 1 bit konum atayabilirsiniz. Artık her kenar için ile bölümüne {X, Y} başka bir bölümden seyahat etmenin hiç yararlı olup olmadığını belirleyebilirsiniz. Genellikle, yollar iki yönlüdür ve bu, iki yönden yalnızca birinin yararlı olduğu anlamına gelir. Böylece iki yönden biri bu bit ayarına sahip, diğeri ise temizlemiş. Bu gerçek bir fayda olarak görünmeyebilir, ancak birçok kesişme noktasında göz önünde bulundurmanız gereken seçenek sayısını 2'den sadece 1'e düşürmeniz anlamına gelir ve bu yalnızca tek bir işlem gerektirir.

3
katma
Londra için en büyük avantajlardan biri, bu bitlerin köprüde ayarlanmasıdır. A * gereksiz yere nehri geçip diğer kıyıda sıkışıp kalmaktan biraz acı çekebilir.
katma yazar MSalters, kaynak

Buradaki tasarıya uygun düzinelerce A * varyasyonu var. Yine de kullanım durumlarını düşünmelisin.

  • Hafıza- (ve ayrıca önbellek-) kısıtlı mısın?
  • Aramayı paralel hale getirebilir misiniz?
  • Algoritma uygulamanız yalnızca tek bir yerde mi kullanılacak (ör. Greater London ve NYC veya Mumbai değil veya her yerde)?

Sizin ve işvereninizin özel olduğu tüm detayları bilmemizin imkanı yok. Bu nedenle ilk durağınız CiteSeer veya Google Akademik: olmalıdır; sizin gibi kısıtlamalar.

Ardından üç veya dört algoritmaya kadar aşağı inin, prototipleme yapın, nasıl ölçeklendiklerini test edin ve bunları ince ayar yapın. Noktalar, kalan süre veya diğer faktörler arasındaki mesafeye bağlı olarak aynı algoritmayı aynı büyük yol bulma rutininde birleştirebileceğinizi unutmayın.

Daha önce de belirtildiği gibi, hedef bölgenizdeki küçük çaplı ölçeğe göre Haversine'i düşürmek, muhtemelen pahalı trig değerlendirmelerinde değerli zaman kazandıran ilk adımınızdır. NOT: Öklid mesafesini lat, lon koordinatlarında kullanmanızı önermiyorum - haritanızı ör. Merkeze yakın enine Mercator ve metre veya metre cinsinden Kartezyen koordinatlarını kullanın!

Önceden hesaplamak ikincisidir ve derleyicileri değiştirmek açık bir üçüncü fikir olabilir (C veya C ++ 'a geçin - bkz. https://benchmarksgame.alioth.debian.org/ Ayrıntılar için).

Ekstra optimizasyon adımları arasında dinamik bellek tahsisini kurtulmak ve düğümler arasında arama yapmak için etkili indekslemeyi kullanmak (R-tree ve türevleri/alternatifleri olduğunu düşünebilirsiniz) içerebilir.

3
katma

Genellikle A *, zaman aşımına uğramak yerine çok fazla bellek tüketimi ile birlikte gelir.

Bununla birlikte, ilk önce, yalnızca genellikle küçük bir sokaktan geçen bir otoyol seçeceğiniz “büyük caddelerin” bir parçası olan düğümlerle hesaplamanın faydalı olabileceğini düşünüyorum.

Sanırım bunu kilo fonksiyonunuz için zaten kullanıyor olabilirsiniz, ancak daha sonraki seyahatlerde hangi düğümü test edeceğinize karar vermek için bazı öncelik Sıralarını kullanırsanız daha hızlı olabilirsiniz.

Ayrıca, grafiği yalnızca düşük maliyetli kenarların bir parçası olan düğümlere indirgemeyi deneyebilir ve ardından bu düğümlerin en yakınından başlayıp sonuna kadar bir yol bulabilirsiniz. Yani baştan sona "büyük caddeye" ve "büyük caddeye" kadar 2 yol var. Şimdi "büyük caddelerin" bir parçası olan iki düğüm arasındaki en iyi yolu, azaltılmış bir grafikte hesaplayabilirsiniz.

0
katma