C#'da Floyd-Warshall Algoritması ile Tüm Çiftlerin En Kısa Yollarının "Rotaları" Nasıl Bulunur

giriiş

Önceki yazıda , Floyd-Warshall algoritmasını kullanarak tüm çiftler için en kısa yol probleminin nasıl çözüleceğini gördük. Ayrıca, paralellik ve vektörleştirme kullanarak algoritmanın performansını iyileştirmenin çeşitli yollarını da inceledik.

Ancak, Floyd-Warshall algoritmasının sonuçlarını düşünürseniz, ilginç anı hemen fark edeceksiniz: Bir grafikteki tepe noktaları arasındaki mesafeleri (en kısa yolların değerlerini) biliyoruz ancak "rotaları" bilmiyoruz, yani her bir tepe noktasının en kısa yola hangi katkıda bulunduğunu bilmiyoruz ve bu "rotaları" elde ettiğimiz sonuçlardan yeniden oluşturamıyoruz.

Bu yazıda, Floyd-Warshall algoritmasını genişletmek için bana katılmanızı rica ediyorum. Bu sefer, mesafeyi hesaplayıp "rota"yı yeniden inşa edebileceğimizden emin olacağız.

Bilinen Bir Teoriden Biraz…

Kodlara ve kıyaslamalara dalmadan önce, Floyd-Warshall algoritmasının nasıl çalıştığına dair bir teoriyi gözden geçirelim.

Algoritmanın metinsel açıklaması şöyledir:

1. Boyut N olan bir grafiği ( G ), her hücre W[i,j] i j köşeye kadar olan bir kenarın ağırlığını içeren N x N boyutunda bir matris ( W ) olarak temsil ederek başlıyoruz (bkz. Resim 1). Köşeler arasında kenar olmadığı durumlarda, hücre özel bir NO_EDGE değerine ayarlanır (Resim 1'de koyu hücreler olarak gösterilmiştir).

   
   

2. Şu andan itibaren şunu diyeceğiz: W[i,j] i ve j köşeleri arasında bir mesafe içerir.

   
   

3. Daha sonra, k köşesini alırız ve tüm W[i,j] köşe çiftlerini dolaşarak i ⭢ k ⭢ j mesafesinin, i ve j arasındaki bilinen mesafeden daha küçük olup olmadığını kontrol ederiz.

   
   

4. En küçük değer W[i,j] içinde saklanır ve 3. adım, G tüm köşeleri k olarak kullanılana kadar bir sonraki k için tekrarlanır.

İşte sözde kod:

 algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i,j] = min(W[i,j], W[i,k] + W[k,j]) end for end for end for end algorithm

İşlem tamamlandığında, W matrisinin her hücresi W[i,j] i ve j köşeleri arasındaki en kısa yolun mesafesini veya aralarında bir yol yoksa NO_EDGE değerini içerir.

Başta da belirttiğim gibi – sadece bu bilgiye sahip olmak, bu tepe noktaları arasındaki rotaları yeniden oluşturmayı imkansız hale getiriyor. Peki… bu rotaları yeniden oluşturabilmek için ne yapmalıyız?

Peki... kulağa bariz gelebilir ama... daha fazla veri toplamamız gerekiyor!

… Aynı Teorinin Birazı Ama Farklı Bir Açıdan

Floyd-Warshall algoritmasının özü, i j ara köşe k geçen potansiyel olarak yeni bir yol mesafesine sahip, bilinen mesafe W[i,j] olan bir bölmedir.

Bu ayrıntıya bu kadar dikkat çekmemin sebebi rota bilgisini nasıl koruyabileceğimizin anahtarı olmasıdır. 5 tepe noktasından oluşan önceki grafiği alalım (Resim 2'ye bakın) ve üzerinde Floyd-Warshall algoritmasını uygulayalım.

Başlangıçta tüm grafik kenarlarını biliyoruz ve bu da bize şu yolları veriyor: 0 ⭢ 1 :2 , 0 ⭢ 4 :10 , 1 ⭢ 3 :1 , 2 ⭢ 4 :1 , 3 ⭢ 2 :1 ve 3 ⭢ 4 :3 .

Ayrıca, köşe 0 giden hiçbir kenar olmadığını da biliyoruz, bu nedenle k = 0 için bir algoritma yürütmek anlamsızdır. Ayrıca, köşe 0 köşe 1 giden tek bir kenar ( 0 ⭢ 1 ) olduğu da açıktır, bu da tüm i != 0 ( i burada "from"dur) yürütülmesini oldukça anlamsız hale getirir ve köşe 1 2 ve 4 ile kenarları olduğundan, 2 veya 4 olmayan herhangi bir j için algoritma yürütmek de anlamsızdır ( j burada "to"dur).

Bu nedenle ilk adımımız k = 1 , i = 0 ve j = 2,4 için bir algoritma yürütmek olacak.

İki yol bulduk: yeni bir yol ( 0 ⭢ 1 ⭢ 2 ) ve bir kısayol ( 0 ⭢ 1 ⭢ 4 ). Her ikisi de 1 tepe noktasından geçer. Bu bilgiyi ( 1 2 ve 4 ulaştığımız gerçeğini) hemen bir yerde saklamazsak, sonsuza dek kaybolacaktır (ve bu istediğimizin tam tersidir).

Peki ne yapmalıyız? Matris W yeni değerlerle güncelleyeceğiz (bkz. Resim 3a) ve ayrıca k değerini ( k = 1 olan) matris W ile aynı boyutta ancak NO_EDGE değerleriyle başlatılmış yeni bir matris R R[0,2] ve R[0,4] hücrelerine depolayacağız (bkz. Resim 3b).

Şimdilik, R matrisinin tam olarak ne olduğuna odaklanmayın. Devam edelim ve algoritmayı bir sonraki k = 2 için çalıştıralım.

Burada, k = 1, ancak bu sefer G grafiği yerine W matrisini kullanacağız. Özellikle 2. sütun ve 2. satırdaki W matrisine bakın (Resim 4).

Burada, köşe 2 ve köşe 1 (sütun #2) köşe 2'ye giden iki yol ve köşe 2 köşe 3 ve köşe 4 (satır #2) 0 iki yol olduğunu görebilirsiniz. Bunu bilerek, algoritmayı yalnızca k = 2 , i = 0,1 ve j = 3,4 kombinasyonları için yürütmek mantıklıdır.

Daha önce yaptığımız gibi, W[0,3] , W[0,4] , W[1,3] , W[1,4] hücrelerini yeni mesafelerle ve R[0,3] , R[0,4] , R[1,3] ve R[1,4] hücrelerini k = 2 ile güncelliyoruz (bkz. Resim 5).

İşlenecek sadece k = 3 kaldı (çünkü grafikte 4 köşeden başka herhangi bir köşeye giden kenar yok).

Tekrar W matrisine bakalım (Resim 6).

W matrisine göre, 0 , 1 ve 2 nolu köşelerden 3 köşeye giden üç yol vardır (sütun #3) ve 3 nolu köşeden 4 nolu köşeye giden bir yol vardır (satır #3). Bu nedenle, işlememiz gereken şu yollara sahibiz:

Bu, algoritmanın son yinelemesiydi. Geriye kalan tek şey, W[0,4] , W[1,4] , W[2,4] hücrelerini yeni mesafelerle güncellemek ve R[0,4] , R[1,4] , R[2,4] hücrelerini 3 olarak ayarlamak.

Algoritmanın sonunda karşımıza çıkan görüntü şu şekilde (Resim 7).

Önceki yazıdan bildiğimiz gibi, W matrisi artık G grafiğindeki tüm en kısa yol çiftlerini içeriyor. Peki R matrisinin içinde ne saklanıyor?

Eve dönüş

Her seferinde yeni bir en kısa yol bulduğumuzda, matris R karşılık gelen hücresini k geçerli değeriyle güncelliyorduk. İlk başta, bu eylem gizemli görünebilir ancak çok basit bir anlamı vardır: hedef tepe noktasına ulaştığımız tepe noktasını saklıyorduk: i ⭢ k ⭢ j (burada j doğrudan k ulaşıyoruz).

Bu an kritiktir. Çünkü geldiğimiz bir tepe noktasını bilmek, tepe noktası j ("nereye") tepe noktası i ("nereye") doğru geriye doğru (bir ıstakoz gibi) hareket ederek rotayı yeniden inşa etmemize olanak tanır.

İşte i j giden rotayı yeniden oluşturmak için algoritmanın metinsel açıklaması:

1. Boş dinamik dizi X hazırlayın.
2. R[i,j] hücresinden z değerini okuyarak başlayalım.
3. Eğer z NO_EDGE ise, i j giden rota bulunmuştur ve 7. adıma geçmeliyiz.
4. Dinamik bir dizi olan X önüne z ekleyin.
5. R[i,z] hücresinin değerini z oku.
6. #3'teki çıkış koşuluna ulaşılana kadar #3, #4 ve #5 adımlarını tekrarlayın.
7. X'in önüne i ekleyin.
8. j X ekle.
9. Artık dinamik dizi X i j giden yolu içeriyor.

Sahte kodda daha da basit görünüyor:

 algorithm RebuildRoute(i, j, R) x = array() z = R[i,j] while (z ne NO_EDGE) do x.prepend(z) z = R[i,z] end while x.prepend(i) x.append(j) return x end algorithm

Bunu G grafiğimizde deneyelim ve 0 köşeden 4 köşeye bir rota yeniden oluşturalım (bkz. Resim 8).

Yukarıdaki çizimin metinsel açıklaması şöyledir:

1. R[0,4] değerini okuyarak başlıyoruz, bu da 3 sonucunu veriyor. Algoritmaya göre bu, rotanın 3 köşeden (MAVİ ile gösterilmiştir) 4 köşeye gittiği anlamına geliyor.

   
   

2. R[0,4] değeri NO_EDGE olmadığından, devam edip R[0,3] değerini okuyoruz ve 2 sonucunu elde ediyoruz (YEŞİL renkle gösterilmiştir).

   
   

3. Yine, R[0,3] değeri NO_EDGE olmadığından, devam edip R[0,2] değerini okuyoruz ve 1 sonucunu elde ediyoruz (KIRMIZI ile gösterilmiştir).

   
   

4. Son olarak, NO_EDGE değeriyle sonuçlanan R[0,1] değerini okuruz, yani rotaya katkıda bulunan 0 ve 4 dışında başka tepe noktası yoktur. Bu nedenle, ortaya çıkan rota şudur: 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 ki grafiğe bakarsanız, gerçekten de 0 tepe noktasından 4 tepe noktasına en kısa yola karşılık gelir.

Düşünceli bir okuyucu şunu sorabilir:

Çok iyi bir soru. Eminiz çünkü W matrisindeki en kısa yol değerini güncellediğimizde R matrisini yeni bir değerle güncelliyoruz. Yani sonunda R matrisinin her satırı en kısa yollarla ilgili veri içeriyor. Ne daha fazla, ne daha az.

Artık teoriyi bitirdik, şimdi uygulama zamanı.

C# dilinde uygulama

Önceki yazımızda Floyd-Warshall algoritmasının orijinal versiyonunu uygulamanın yanı sıra çeşitli optimizasyonları da entegre ettik: seyrek grafiklere destek, paralellik ve vektörizasyon ve sonunda bunların hepsini birleştirdik.

Bunların hepsini bugün tekrarlamanın bir nedeni yok. Ancak, rota ezberlemeyi algoritmanın orijinal ve vektörleştirilmiş (seyrek grafikler için destekle) sürümlerine nasıl entegre edeceğinizi göstermek istiyorum.

Orijinal Algoritmaya Entegrasyon

İnanması zor olabilir ama rota ezberlemeyi algoritmaların orijinal versiyonuna entegre etmek için yapmamız gereken tek şey:

1. Fonksiyon imzasını R matrisini ayrı bir parametre olarak içerecek şekilde genişletin – int[] routes .

   
   

2. En kısa yol her değiştiğinde routes k kaydedin (satırlar: 2 ve 14).

İşte bu kadar. Sadece bir buçuk satır kod:

 public void BaselineWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } }

Vektörize Algoritmaya Entegrasyon

Vektörize edilmiş (seyrek grafikler için destek sağlayan) bir versiyona entegrasyon biraz daha fazla çaba gerektiriyor, ancak kavramsal adımlar aynı:

1. Fonksiyon imzasını, R matrisini ayrı bir parametre olarak içerecek şekilde genişletin – int[] routes .

   
   

2. Her yinelemede, k değerinden oluşan yeni bir vektör başlatın (satır: 6).

   
   

3. En kısa yol her değiştiğinde routes k değerli vektör kaydedin (satırlar: 31-32).

   
   

4. Algoritmanın vektörleştirilmemiş bir kısmını, orijinal algoritmayı güncellediğimiz şekilde (satır: 41) güncelleyelim.

 public void SpartialVectorOptimisationsWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { var k_vec = new Vector<int>(k); for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == Constants.NO_EDGE) { continue; } var ik_vec = new Vector<int>(matrix[i * sz + k]); var j = 0; for (; j < sz - Vector<int>.Count; j += Vector<int>.Count) { var ij_vec = new Vector<int>(matrix, i * sz + j); var ikj_vec = new Vector<int>(matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector<int>(-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); var ro_vec = new Vector<int>(routes, i * sz + j); var rk_vec = Vector.ConditionalSelect(lt_vec, ro_vec, k_vec); rk_vec.CopyTo(routes, i * sz + j); } for (; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } }

Karşılaştırmalı değerlendirme

Rota bilgisi toplamak yeterince mantıklı görünüyor çünkü... neden olmasın? Özellikle de mevcut algoritmalara entegre edilmesi çok kolayken. Ancak, varsayılan olarak entegre etmenin ne kadar pratik olduğunu görelim.

İşte iki set kıyaslama: hem ile hem de olmadan (her ikisi de algoritmanın orijinal ve vektörleştirilmiş versiyonlarını yürütür). Tüm kıyaslamalar, Intel Core i5-6200U CPU 2.30GHz (Skylake) işlemciyle donatılmış ve Windows 10 çalıştıran bir makinede BenchmarkDotNet v0.13.1 (.NET 6.0.4 x64) tarafından yürütüldü.

Tüm deneyler, önceki yazıda kullanılan önceden tanımlanmış grafik kümesi üzerinde gerçekleştirildi: 300, 600, 1200, 2400 ve 4800 tepe noktası.

Aşağıda, Baseline ve BaselineWithRoutes yöntemlerinin algoritmanın orijinal versiyonuna, SpartialVectorOptimisations ve SpartialVectorOptimisationsWithRoutes yöntemlerinin ise algoritmanın vektörleştirilmiş (seyrek grafikler için destek sağlayan) versiyonuna karşılık geldiği kıyaslama sonuçları yer almaktadır.

Karşılaştırma sonuçlarının yorumlanması kolay değildir. Daha yakından bakarsanız, rota toplamanın algoritmayı gerçekten daha hızlı veya hiç önemli bir etki yaratmadan çalıştırdığı bir kombinasyon bulacaksınız.

Bu çok kafa karıştırıcı görünüyor (ve eğer öyleyse – ölçümleri etkileyebilecek zor şeylerin ne olduğunu daha iyi anlamak için Denis Bakhvalov ve Andrey Akinshin ile bu programı dinlemenizi şiddetle tavsiye ederim). Buradaki en iyi çıkarımım, "kafa karıştırıcı" davranışın harika CPU önbellek performansından kaynaklandığıdır (çünkü grafikler önbellekleri doyurmak için yeterince büyük değildir). Kısmen, bu teori en büyük grafikte önemli bir bozulma görebildiğimiz " kalın " örneğe dayanmaktadır. Ancak, bunu doğrulamadım.

Genel olarak, kıyaslama, aşırı yüksek performans senaryolarından ve büyük grafiklerden bahsetmiyorsak, varsayılan olarak rota ezberlemeyi her iki algoritmaya entegre etmenin sorun olmadığını gösteriyor (ancak unutmayın, bir yerine iki matris W ve R ayırmamız gerektiğinden bellek tüketimini iki katına çıkaracaktır).

Geriye sadece rota yeniden oluşturma algoritmasının uygulanması kalıyor.

Rota Yeniden Oluşturma Algoritmasının Uygulanması

C# dilinde rota yeniden oluşturma algoritmalarının uygulanması basittir ve daha önce gösterilen sözde kodu neredeyse tamamen yansıtır (dinamik diziyi temsil etmek için LinkedList<T> kullanırız):

 public static IEnumerable<int> RebuildWithLinkedList( int[] routes, int sz, int i, int j) { var x = new LinkedList<int>(); var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x.AddFirst(z); z = routes[i * sz + z]; } x.AddFirst(i); x.AddLast(j); return x; }

Yukarıdaki algoritma mükemmel değil ve kesinlikle geliştirilebilir. Yapabileceğimiz en basit geliştirme, sz boyutunda bir diziyi önceden tahsis etmek ve ters sırada doldurmaktır:

 public static IEnumerable<int> RebuildWithArray( int[] routes, int sz, int i, int j) { var x = new int[sz]; var y = sz - 1; // Fill array from the end x[y--] = j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x[y--] = z; z = routes[i * sz + z]; } x[y] = i; // Create an array segment from 'y' to the end of the array // // This is required because 'sz' (and therefore length of the array x) // equals to the number of vertices in the graph // // So, in cases when route doesn't span through // all vertices - we need return a segment of the array return new ArraySegment<int>(x, y, sz - y); }

Bu "optimizasyon" tahsis sayısını bire düşürse de, algoritmayı bir öncekinden "daha hızlı" yapmaz veya "daha az bellek tahsis etmez". Buradaki nokta, i j sıralanmış bir rotaya ihtiyacımız varsa, R matrisinden aldığımız verileri her zaman "tersine çevirmemiz" gerekeceğidir ve bundan kaçmanın bir yolu yoktur.

Ancak verileri ters sırada sunabiliyorsak, o zaman LINQ'dan faydalanabilir ve gereksiz tahsislerden kaçınabiliriz:

 public static IEnumerable<int> RebuildWithReverseYield( int[] routes, int sz, int i, int j) { yield return j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { yield return z; z = routes[i * sz + z]; } yield return i; }

Bu kodun nasıl "değiştirilebileceği" veya "geliştirilebileceği" konusunda çok daha fazla varyant olabilir. Buradaki önemli an, şunu hatırlamaktır: Herhangi bir "değişikliğin" bellek veya CPU döngüleri açısından dezavantajları vardır.

Deney yapmaktan çekinmeyin! Olasılıklar neredeyse sınırsız!

Çözüm

Bu yazıda, Floyd-Warshall algoritmasının ardındaki teoriye derinlemesine bir dalış yaptık ve bunu en kısa yollar olan "rotaları" ezberleme olasılığıyla genişlettik. Ardından, önceki yazıdan C# uygulamalarını (orijinal ve vektörleştirilmiş) güncelledik. Sonunda, "rotaları" yeniden oluşturmak için algoritmanın birkaç sürümünü uyguladık.

Çok tekrarladık ama aynı zamanda bunda yeni ve ilginç bir şeyler bulduğunuzu umuyorum. Bu, tüm çiftler için en kısa yollar probleminin sonu değil. Bu sadece başlangıç.

Umarım okumaktan keyif almışsınızdır, bir sonrakinde görüşmek üzere!