giriiş , 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. Önceki yazıda Floyd-Warshall algoritmasını 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: Boyut olan bir grafiği ( ), her hücre köşeye kadar olan bir kenarın ağırlığını içeren boyutunda bir matris ( ) olarak temsil ederek başlıyoruz (bkz. Resim 1). Köşeler arasında kenar olmadığı durumlarda, hücre özel bir değerine ayarlanır (Resim 1'de koyu hücreler olarak gösterilmiştir). N G W[i,j] i j N x N W NO_EDGE Şu andan itibaren şunu diyeceğiz: ve köşeleri arasında bir mesafe içerir. W[i,j] i j Daha sonra, köşesini alırız ve tüm köşe çiftlerini dolaşarak mesafesinin, ve arasındaki bilinen mesafeden daha küçük olup olmadığını kontrol ederiz. k W[i,j] i ⭢ k ⭢ j i j En küçük değer içinde saklanır ve 3. adım, tüm köşeleri olarak kullanılana kadar bir sonraki için tekrarlanır. W[i,j] G k k İş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, matrisinin her hücresi ve köşeleri arasındaki en kısa yolun mesafesini veya aralarında bir yol yoksa değerini içerir. W W[i,j] i j NO_EDGE 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ü, ara köşe geçen potansiyel olarak yeni bir yol mesafesine sahip, bilinen mesafe olan bir bölmedir. i j k W[i,j] 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: , , , , ve . 0 ⭢ 1 :2 0 ⭢ 4 :10 1 ⭢ 3 :1 2 ⭢ 4 :1 3 ⭢ 2 :1 3 ⭢ 4 :3 Yolları yazarken kullandığım “from” ⭢ “to” :”distance” formatını kullanıyorum. önceki yazıda - Yazarın notu Ayrıca, köşe giden hiçbir kenar olmadığını da biliyoruz, bu nedenle için bir algoritma yürütmek anlamsızdır. Ayrıca, köşe köşe giden tek bir kenar ( ) olduğu da açıktır, bu da tüm ( burada "from"dur) yürütülmesini oldukça anlamsız hale getirir ve köşe ve ile kenarları olduğundan, veya olmayan herhangi bir için algoritma yürütmek de anlamsızdır ( burada "to"dur). 0 k = 0 0 1 0 ⭢ 1 i != 0 i 1 2 4 2 4 j j Bu nedenle ilk adımımız , ve için bir algoritma yürütmek olacak. k = 1 i = 0 j = 2,4 Adım Yol Yorum 1 0 ⭢ 1 ⭢ 2 Yol bulundu. Mesafe = 3 (hiçbir şey değildi) 2 0 ⭢ 1 ⭢ 4 Yol bulundu. Mesafe = 8 (önceden 10 idi). İki yol bulduk: yeni bir yol ( ) ve bir kısayol ( ). Her ikisi de tepe noktasından geçer. Bu bilgiyi ( ve ulaştığımız gerçeğini) hemen bir yerde saklamazsak, sonsuza dek kaybolacaktır (ve bu istediğimizin tam tersidir). 0 ⭢ 1 ⭢ 2 0 ⭢ 1 ⭢ 4 1 1 2 4 Peki ne yapmalıyız? Matris yeni değerlerle güncelleyeceğiz (bkz. Resim 3a) ve ayrıca değerini ( olan) matris ile aynı boyutta ancak değerleriyle başlatılmış yeni bir matris ve hücrelerine depolayacağız (bkz. Resim 3b). W k k = 1 W NO_EDGE R R[0,2] R[0,4] Şimdilik, matrisinin tam olarak ne olduğuna odaklanmayın. Devam edelim ve algoritmayı bir sonraki için çalıştıralım. R k = 2 Burada, ancak bu sefer grafiği yerine matrisini kullanacağız. Özellikle 2. sütun ve 2. satırdaki matrisine bakın (Resim 4). k = 1, G W W Burada, köşe ve köşe (sütun #2) köşe 2'ye giden iki yol ve köşe köşe ve köşe (satır #2) iki yol olduğunu görebilirsiniz. Bunu bilerek, algoritmayı yalnızca , ve kombinasyonları için yürütmek mantıklıdır. 2 1 2 3 4 0 k = 2 i = 0,1 j = 3,4 Adım Yol Yorum 1 0 ⭢ 2 ⭢ 3 Yol bulundu. Mesafe = 4 (hiçbir şey değildi) 2 0 ⭢ 2 ⭢ 4 Yol bulundu. Mesafe = 6 (8 idi) 3 1 ⭢ 2 ⭢ 3 Yol bulundu. Mesafe = 2 (hiçbir şey değildi) 4 1 ⭢ 2 ⭢ 4 Yol bulundu. Mesafe = 4 (6 idi) Daha önce yaptığımız gibi, , , , hücrelerini yeni mesafelerle ve , , ve hücrelerini ile güncelliyoruz (bkz. Resim 5). W[0,3] W[0,4] W[1,3] W[1,4] R[0,3] R[0,4] R[1,3] R[1,4] k = 2 İşlenecek sadece kaldı (çünkü grafikte köşeden başka herhangi bir köşeye giden kenar yok). k = 3 4 Tekrar matrisine bakalım (Resim 6). W matrisine göre, , ve nolu köşelerden köşeye giden üç yol vardır (sütun #3) ve nolu köşeden nolu köşeye giden bir yol vardır (satır #3). Bu nedenle, işlememiz gereken şu yollara sahibiz: W 0 1 2 3 3 4 Adım Yol Yorum 1 0 ⭢ 3 ⭢ 4 Yol bulundu. Mesafe = 5 (6 idi) 2 1 ⭢ 3 ⭢ 4 Yol bulundu. Mesafe = 3 (4 idi) 3 2 ⭢ 3 ⭢ 4 Yol bulundu. Mesafe = 2 (3 idi) Bu, algoritmanın son yinelemesiydi. Geriye kalan tek şey, , , hücrelerini yeni mesafelerle güncellemek ve , , hücrelerini olarak ayarlamak. W[0,4] W[1,4] W[2,4] R[0,4] R[1,4] R[2,4] 3 Algoritmanın sonunda karşımıza çıkan görüntü şu şekilde (Resim 7). bildiğimiz gibi, matrisi artık grafiğindeki tüm en kısa yol çiftlerini içeriyor. Peki matrisinin içinde ne saklanıyor? Önceki yazıdan W G R Eve dönüş Her seferinde yeni bir en kısa yol bulduğumuzda, matris karşılık gelen hücresini 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: (burada doğrudan ulaşıyoruz). R k i ⭢ k ⭢ j j k Bu an kritiktir. Çünkü geldiğimiz bir tepe noktasını bilmek, tepe noktası ("nereye") tepe noktası ("nereye") doğru geriye doğru (bir ıstakoz gibi) hareket ederek rotayı yeniden inşa etmemize olanak tanır. j i İşte giden rotayı yeniden oluşturmak için algoritmanın metinsel açıklaması: i j Boş dinamik dizi hazırlayın. X hücresinden değerini okuyarak başlayalım. R[i,j] z Eğer ise, giden rota bulunmuştur ve 7. adıma geçmeliyiz. z NO_EDGE i j Dinamik bir dizi olan önüne ekleyin. X z hücresinin değerini oku. R[i,z] z #3'teki çıkış koşuluna ulaşılana kadar #3, #4 ve #5 adımlarını tekrarlayın. X'in önüne ekleyin. i ekle. j X Artık dinamik dizi giden yolu içeriyor. X i j Lütfen unutmayın, yukarıdaki algoritma yalnızca mevcut yollar için çalışır. Ayrıca performans açısından mükemmel değildir ve kesinlikle optimize edilebilir. Ancak, bu gönderinin kapsamında, anlaşılmasını ve bir kağıt parçası üzerinde yeniden üretilmesini kolaylaştıracak şekilde özel olarak açıklanmıştır. - Yazarın notu 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 grafiğimizde deneyelim ve köşeden köşeye bir rota yeniden oluşturalım (bkz. Resim 8). G 0 4 Yukarıdaki çizimin metinsel açıklaması şöyledir: değerini okuyarak başlıyoruz, bu da sonucunu veriyor. Algoritmaya göre bu, rotanın köşeden (MAVİ ile gösterilmiştir) köşeye gittiği anlamına geliyor. R[0,4] 3 3 4 değeri olmadığından, devam edip değerini okuyoruz ve sonucunu elde ediyoruz (YEŞİL renkle gösterilmiştir). R[0,4] NO_EDGE R[0,3] 2 Yine, değeri olmadığından, devam edip değerini okuyoruz ve sonucunu elde ediyoruz (KIRMIZI ile gösterilmiştir). R[0,3] NO_EDGE R[0,2] 1 Son olarak, değeriyle sonuçlanan değerini okuruz, yani rotaya katkıda bulunan ve dışında başka tepe noktası yoktur. Bu nedenle, ortaya çıkan rota şudur: ki grafiğe bakarsanız, gerçekten de tepe noktasından tepe noktasına en kısa yola karşılık gelir. NO_EDGE R[0,1] 0 4 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 0 4 Düşünceli bir okuyucu şunu sorabilir: matrisinden okuduğumuz tüm verilerin aynı yola ait olduğundan nasıl emin olabiliriz? R - Düşünceli okuyucu Çok iyi bir soru. Eminiz çünkü matrisindeki en kısa yol değerini güncellediğimizde matrisini yeni bir değerle güncelliyoruz. Yani sonunda matrisinin her satırı en kısa yollarla ilgili veri içeriyor. Ne daha fazla, ne daha az. W R R Artık teoriyi bitirdik, şimdi uygulama zamanı. C# dilinde uygulama 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. Önceki yazımızda 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: Fonksiyon imzasını matrisini ayrı bir parametre olarak içerecek şekilde genişletin – . R int[] routes En kısa yol her değiştiğinde k kaydedin (satırlar: 2 ve 14). routes İş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ı: Fonksiyon imzasını, matrisini ayrı bir parametre olarak içerecek şekilde genişletin – . R int[] routes Her yinelemede, değerinden oluşan yeni bir vektör başlatın (satır: 6). k En kısa yol her değiştiğinde değerli vektör kaydedin (satırlar: 31-32). routes k 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; } } } } } Küçük bir hatırlatma – işlemi, değerlerin giriş vektörlerinin iki karşılık gelen değerinden küçük olanına eşit olduğu yeni bir vektör döndürür, yani, vektörünün değeri eşitse, işlem bir değer seçer, aksi takdirde bir değer seçer. Vector.ConditionalSelect lt_vec -1 ij_vec k_vec - Yazarın notu 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 v0.13.1 (.NET 6.0.4 x64) tarafından yürütüldü. BenchmarkDotNet Tüm deneyler, kullanılan önceden tanımlanmış grafik kümesi üzerinde gerçekleştirildi: 300, 600, 1200, 2400 ve 4800 tepe noktası. önceki yazıda Kaynak kodu ve deneysel grafikler GitHub'daki depoda mevcuttur. Deneysel grafikler dizininde bulunabilir. Data/Sparse-Graphs.zip Bu gönderideki tüm kıyaslamalar APSP02.cs dosyasında uygulanmıştır. Aşağıda, ve yöntemlerinin algoritmanın orijinal versiyonuna, ve 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. Baseline BaselineWithRoutes SpartialVectorOptimisations SpartialVectorOptimisationsWithRoutes Yöntem Boyut Ortalama (ms) Hata (ms) Standart Sapma (ms) Temel çizgi 300 40.233 0,0572 0,0477 Rotalarla Temel Hat 300 40.349 0,1284 0,1201 SpartialVektörOptimizasyonları 300 4.472 0,0168 0,0140 SpartialVectorOptimizationsWithRoutes 300 4.517 0,0218 0,0193 Temel çizgi 600 324.637 5.6161 4.6897 Rotalarla Temel Hat 600 321.173 1.4339 1.2711 SpartialVektörOptimizasyonları 600 32.133 0.2151 0,1679 SpartialVectorOptimizationsWithRoutes 600 34.646 0,1286 0,1073 Temel çizgi 1200 2.656.024 6.9640 5.8153 Rotalarla Temel Hat 1200 2.657.883 8.8814 7.4164 SpartialVektörOptimizasyonları 1200 361.435 2,5877 2.2940 SpartialVectorOptimizationsWithRoutes 1200 381.625 3.6975 3.2777 Temel çizgi 2400 21.059,519 38.2291 33.8891 Rotalarla Temel Hat 2400 20.954.852 56.4719 50.0609 SpartialVektörOptimizasyonları 2400 3.029.488 12.1528 11.3677 SpartialVectorOptimizationsWithRoutes 2400 3.079.006 8.6125 7.1918 Temel çizgi 4800 164.869,803 547.6675 427.5828 Rotalarla Temel Hat 4800 184.305.980 210.9535 164.6986 SpartialVektörOptimizasyonları 4800 21.882,379 200.2820 177.5448 SpartialVectorOptimizationsWithRoutes 4800 21.004.612 79.8752 70.8073 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 ve ile bu 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 " " örneğe dayanmaktadır. Ancak, bunu doğrulamadım. Denis Bakhvalov Andrey Akinshin programı kalın 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 ve ayırmamız gerektiğinden bellek tüketimini iki katına çıkaracaktır). W 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 kullanırız): LinkedList<T> 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, boyutunda bir diziyi önceden tahsis etmek ve ters sırada doldurmaktır: sz 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, sıralanmış bir rotaya ihtiyacımız varsa, matrisinden aldığımız verileri her zaman "tersine çevirmemiz" gerekeceğidir ve bundan kaçmanın bir yolu yoktur. i j R 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! Tüm rota algoritmalarının uygulamalarını GitHub'daki Routes.cs dosyasında bulabilirsiniz. Çö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, 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. önceki yazıdan Ç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!
