Bellman-Ford algoritması - Bellman–Ford algorithm

Bellman-Ford algoritması

Sınıf	Tek kaynaklı en kısa yol problemi (ağırlıklı yönlendirilmiş grafikler için)
Veri yapısı	Grafik
En kötü durumda verim	${ displaystyle Teta (| V || E |)}$
En iyi senaryo verim	${ displaystyle Teta (| E |)}$
En kötü durumda uzay karmaşıklığı	${ displaystyle Teta (| V |)}$

Bellman-Ford algoritması bir algoritma hesaplayan en kısa yollar tek bir kaynaktan tepe bir içindeki diğer tüm köşelere ağırlıklı digraph.^[1]Daha yavaş Dijkstra algoritması aynı problem için, ancak kenar ağırlıklarının bazılarının negatif sayılar olduğu grafikleri işleyebildiği için daha çok yönlü. Algoritma ilk olarak Alfonso Shimbel tarafından önerildi (1955 ), ancak bunun yerine adını alır Richard Bellman ve Lester Ford Jr., kim yayınladı 1958 ve 1956, sırasıyla.^[2] Edward F. Moore ayrıca algoritmanın bir varyasyonunu yayınladı 1959 ve bu nedenle bazen Bellman – Ford – Moore algoritması.^[1]

Negatif kenar ağırlıkları çeşitli grafik uygulamalarında bulunur, dolayısıyla bu algoritmanın faydasıdır.^[3]Bir grafik "negatif döngü" içeriyorsa (ör. döngü Kaynaktan erişilebilen, kenarları toplamı negatif bir değere sahipse, o zaman en ucuz yol: negatif döngüde bir noktası olan herhangi bir yol, bir tane daha ucuza yapılabilir yürümek negatif döngü etrafında. Böyle bir durumda Bellman-Ford algoritması negatif döngüyü algılayabilir ve raporlayabilir.^[1][4]

Algoritma

Bu örnek grafikte, A'nın kaynak olduğunu ve kenarların en kötü sırada, sağdan sola işlendiğini varsayarsak, tam |V|−1 veya mesafe tahminlerinin yakınsaması için 4 yineleme. Tersine, kenarlar soldan sağa en iyi sırada işlenirse, algoritma tek bir yinelemede birleşir.

Sevmek Dijkstra algoritması, Bellman – Ford devam ediyor rahatlama, doğru mesafeye olan yaklaşımların, sonunda çözüme ulaşana kadar daha iyi olanlarla değiştirildiği. Her iki algoritmada da, her bir tepe noktasına olan yaklaşık mesafe, her zaman gerçek mesafenin fazla tahminidir ve eski değerinin minimum değeri ve yeni bulunan bir yolun uzunluğu ile değiştirilir. Bununla birlikte, Dijkstra'nın algoritması öncelik sırası -e açgözlülükle Henüz işlenmemiş en yakın köşeyi seçin ve bu gevşetme işlemini tüm giden kenarlarında gerçekleştirin; aksine, Bellman-Ford algoritması basitçe herşey kenarlar ve bunu yapıyor ${ displaystyle | V | -1}$ zamanlar, nerede ${ displaystyle | V |}$ grafikteki köşe sayısıdır. Bu tekrarların her birinde, doğru hesaplanmış mesafelere sahip köşelerin sayısı artar, bu da sonunda tüm köşelerin doğru mesafelerine sahip olacağı anlamına gelir. Bu yöntem, Bellman-Ford algoritmasının Dijkstra'dan daha geniş bir girdi sınıfına uygulanmasına izin verir.

Bellman-Ford koşuyor ${ displaystyle O (| V | cdot | E |)}$ zaman, nerede ${ displaystyle | V |}$ ve ${ displaystyle | E |}$ sırasıyla köşe ve kenarların sayısıdır.

işlevi BellmanFord (liste köşeler liste kenarlar tepe kaynak) dır-dir    // Bu uygulama şu şekilde temsil edilen bir grafiği alır:    // köşe noktaları ([0..n-1] tamsayı olarak temsil edilir) ve kenar listeleri,    // ve iki diziyi doldurur (uzaklık ve önceki)    // kaynaktan her köşeye en kısa yol    mesafe: = liste boyut n    önceki: = liste boyut n    // 1. Adım: grafiği başlatın    her biri için köşe v içinde köşeler yapmak        mesafe [v]: = inf             // Tüm köşelerden sonsuzluğa olan mesafeyi öncül olarak başlat [v]: = boş         // Ve boş bir öncüle sahip olmak     uzaklık [kaynak]: = 0 // Kaynağın kendisine olan uzaklığı elbette sıfırdır // 2. Adım: kenarları tekrar tekrar gevşetin    tekrar et | V | −1 zamanlar:        her biri için kenar (u, v) ile ağırlık w içinde kenarlar yapmak            Eğer mesafe [u] + w sonra                mesafe [v]: = mesafe [u] + w öncülü [v]: = u // 3. Adım: negatif ağırlıklı döngüleri kontrol edin    her biri için kenar (u, v) ile ağırlık w içinde kenarlar yapmak        Eğer mesafe [u] + w sonra            hata "Grafik bir negatif ağırlık döngüsü içeriyor" dönüş mesafe, önceki

Basitçe söylemek gerekirse, algoritma kaynağa olan mesafeyi 0'a ve diğer tüm düğümleri sonsuza kadar başlatır. Daha sonra tüm kenarlar için, hedefe olan mesafe kenar alınarak kısaltılabiliyorsa, mesafe yeni düşük değere güncellenir. Her yinelemede ben kenarların tarandığına göre, algoritma en fazla uzunluktaki en kısa yolları bulur. ben kenarlar (ve muhtemelen daha uzun bazı yollar ben kenarlar). Döngü olmadan mümkün olan en uzun yol olabileceğinden ${ displaystyle | V | -1}$ kenarlar taranmalıdır ${ displaystyle | V | -1}$ tüm düğümler için en kısa yolun bulunduğundan emin olmak için süre. Tüm kenarların son bir taraması gerçekleştirilir ve herhangi bir mesafe güncellenirse, o zaman bir uzunluk yolu ${ displaystyle | V |}$ Yalnızca grafikte en az bir negatif döngü varsa ortaya çıkabilen kenarlar bulunmuştur.

Doğruluğun kanıtı

Algoritmanın doğruluğu şu şekilde gösterilebilir: indüksiyon:

Lemma. Sonra ben tekrarları için döngü

• Mesafe (sen) sonsuz değildir, bir yolun uzunluğuna eşittir s -e sen; ve
• bir yol varsa s -e sen en fazla ben daha sonra Uzaklık (u), en fazla en kısa yolun uzunluğudur. s -e sen en fazla ben kenarlar.

Kanıt. Tümevarımın temel durumu için, i = 0 ve önceki an için döngü ilk kez yürütülür. Ardından, kaynak köşe için, source.distance = 0, hangisi doğru. Diğer köşeler için sen, u.distance = sonsuzlukbu da doğrudur çünkü kaynak -e sen 0 kenarlı.

Tümevarımsal durum için, önce ilk kısmı ispatlıyoruz. Bir tepe noktasının mesafesinin şu kadar güncellendiği bir an düşünün:v. mesafe: = u. mesafe + uv. ağırlık. Endüktif varsayımla, u. mesafe bir yolun uzunluğu kaynak -e sen. Sonra u.distance + uv.weight yolun uzunluğu kaynak -e v yolu takip eden kaynak -e sen ve sonra gider v.

İkinci kısım için en kısa yolu düşünün P (birden fazla olabilir) kaynak -e v en fazla ben kenarlar. İzin Vermek sen önceki son köşe olmak v bu yolda. Sonra yolun bir kısmı kaynak -e sen en kısa yol kaynak -e sen en fazla i-1 kenarlar, çünkü eğer değilse, o zaman kesinlikle daha kısa bir yol olmalıdır. kaynak -e sen en fazla i-1 kenarları ve daha sonra kenarı ekleyebiliriz uv en fazla bir yol elde etmek için bu yola ben kesinlikle daha kısa olan kenarlar P- bir çelişki. Endüktif varsayımla, u. mesafe sonra ben−1 iterasyon en fazla bu yolun uzunluğu kaynak -e sen. Bu nedenle, uv.weight + u.distance en fazla uzunluğu P. İçinde ben^inci yineleme v. mesafe ile karşılaştırılır uv.weight + u.distanceve buna eşit olarak ayarlanırsa uv.weight + u.distance daha küçük. Bu nedenle, sonra ben yinelemeler, v. mesafe en fazla uzunluğu Pyani en kısa yolun uzunluğu kaynak -e v en çok kullanan ben kenarlar.

Negatif ağırlık döngüleri yoksa, en kısa yol her tepe noktasını en fazla bir kez ziyaret eder, bu nedenle 3. adımda daha fazla iyileştirme yapılamaz. Tersine, hiçbir iyileştirmenin yapılamayacağını varsayalım. Sonra köşeli herhangi bir döngü için v[0], ..., v[k−1],

v [i]. mesafe <= v [i-1 (mod k)]. mesafe + v [i-1 (mod k)] v [i]. ağırlık

Döngü etrafında toplanırsa, v[ben]. mesafe ve v[ben−1 (mod k)]. mesafe terimleri iptal, ayrılma

0 <= 1'den k'ye toplamı v [i-1 (mod k)] v [i]. Ağırlık

Yani her döngünün negatif olmayan ağırlığı vardır.

Negatif döngüleri bulmak

Algoritma en kısa yolları bulmak için kullanıldığında, negatif döngülerin varlığı bir problemdir ve algoritmanın doğru cevabı bulmasını engeller. Ancak, negatif bir döngü bulduktan sonra sona erdiği için, Bellman-Ford algoritması, aranacak hedefin bu olduğu uygulamalar için kullanılabilir - örneğin, döngü iptali teknikler ağ akışı analizi.^[1]

Yönlendirmedeki uygulamalar

Bellman-Ford algoritmasının dağıtılmış bir varyantı, uzaklık vektör yönlendirme protokolleri örneğin Yönlendirme Bilgi Protokolü (HUZUR İÇİNDE YATSIN). Algoritma, bir dizi düğüm (yönlendirici) içerdiği için dağıtılır. Otonom sistem (AS), tipik olarak bir ISP'ye ait olan bir IP ağları koleksiyonu.Aşağıdaki adımlardan oluşur:

1. Her düğüm, kendisi ile AS içindeki diğer tüm düğümler arasındaki mesafeleri hesaplar ve bu bilgileri bir tablo olarak depolar.
2. Her düğüm, tablosunu tüm komşu düğümlere gönderir.
3. Bir düğüm, komşularından uzaklık tablolarını aldığında, diğer tüm düğümlere giden en kısa rotaları hesaplar ve değişiklikleri yansıtmak için kendi tablosunu günceller.

Bellman-Ford algoritmasının bu ayarda temel dezavantajları aşağıdaki gibidir:

• İyi ölçeklenmiyor.
• Değişiklikler ağ topolojisi güncellemeler düğümler halinde yayıldığı için hızlı yansıtılmaz.
• Sonsuza kadar say Eğer bağlantı veya düğüm hataları, bir düğümü diğer bazı düğüm kümelerinden erişilemez hale getirirse, bu düğümler ona olan mesafe tahminlerini kademeli olarak artırarak sonsuza kadar harcayabilir ve bu arada yönlendirme döngüleri olabilir.

İyileştirmeler

Bellman-Ford algoritması, uygulamada (en kötü durumda olmasa da), algoritmanın ana döngüsünün bir yinelemesinin herhangi bir değişiklik yapmadan sonlandırılması durumunda, sonraki yinelemelerde olduğu gibi algoritmanın hemen sonlandırılabileceği gözlemiyle geliştirilebilir. daha fazla değişiklik yapmayın. Bu erken sonlandırma koşuluyla, ana döngü bazı durumlarda şunlardan çok daha azını kullanabilir: |V| − 1 Yinelemeler, algoritmanın en kötü durumu değişmeden kalsa bile. Aşağıdaki iyileştirmelerin tümü, ${ displaystyle O (| V | cdot | E |)}$ en kötü durum zaman karmaşıklığı.

Bellman-Ford algoritmasının bir çeşidi olarak bilinen En Kısa Yol Daha Hızlı Algoritma, ilk olarak tanımlayan Moore (1959), algoritmanın her yinelemesinde gerçekleştirilmesi gereken gevşetme adımlarının sayısını azaltır. Bir köşe v son seferden bu yana değişmeyen bir mesafe değerine sahiptir. v rahatlamıştı, sonra kenarları gevşetmeye gerek yok v ikinci kez. Bu şekilde, doğru mesafe değerlerine sahip tepe noktalarının sayısı arttıkça, her bir yinelemede gevşetilmesi gereken giden kenarlarının sayısı küçülerek, zaman içinde sabit faktör tasarrufuna yol açar. yoğun grafikler.

Yen (1970) Bellman-Ford algoritmasındaki bir başka iyileştirmeyi açıkladı. İyileştirmesi, önce tüm köşelerde bazı rastgele doğrusal sıra atar ve ardından tüm kenarlar kümesini iki alt gruba böler. İlk alt küme, E_f, tüm kenarları içerir (v_ben, v_j) öyle ki ben < j; ikinci, E_b, kenarları içerir (v_ben, v_j) öyle ki ben > j. Her köşe sırasına göre ziyaret edilir v₁, v₂, ..., v_|V|, o köşeden giden her kenarı gevşeterek E_f. Her köşe daha sonra sırayla ziyaret edilir v_|V|, v_|V|−1, ..., v₁, o köşeden giden her kenarı gevşeterek E_b. Algoritmanın ana döngüsünün her yinelemesi, ilkinden sonra, serbest mesafeleri doğru en kısa yol mesafelerine uyan kenarlar kümesine en az iki kenar ekler: E_f ve biri E_b. Bu değişiklik, algoritmanın ana döngüsünün en kötü durumdaki yineleme sayısını azaltır. |V| − 1 -e ${ displaystyle | V | / 2}$.^[5][6]

Başka bir gelişme, Bannister ve Eppstein (2012), Yen'in ikinci iyileştirmesinde kullanılan köşelerin rastgele doğrusal sırasını bir rastgele permütasyon. Bu değişiklik, Yen'in gelişimi için en kötü durumu yaratıyor (en kısa yolun kenarları iki alt küme arasında kesinlikle değişiyor. E_f ve E_b) gerçekleşmesi çok düşük bir ihtimal. Rastgele izin verilen bir köşe sıralamasıyla, beklenen ana döngüde ihtiyaç duyulan yineleme sayısı en fazla ${ displaystyle | V | / 3}$.^[6]

Notlar

Referanslar

Orijinal kaynaklar

• Shimbel, A. (1955). İletişim ağlarında yapı. Bilgi Ağları Sempozyumu Bildirileri. New York, New York: Polytechnic Institute of Brooklyn Polytechnic Press. s. 199–203.
• Bellman, Richard (1958). "Bir yönlendirme probleminde". Üç Aylık Uygulamalı Matematik. 16: 87–90. doi:10.1090 / qam / 102435. BAY  0102435.
• Ford, Lester R. Jr. (14 Ağustos 1956). Ağ Akış Teorisi. Kağıt P-923. Santa Monica, California: RAND Corporation.
• Moore, Edward F. (1959). Bir labirentteki en kısa yol. Proc. Internat. Sempozyumlar. Switching Theory 1957, Kısım II. Cambridge, Massachusetts: Harvard Üniv. Basın. s. 285–292. BAY  0114710.
• Yen, Jin Y. (1970). "Genel ağlarda tüm kaynak düğümlerden belirli bir hedefe giden en kısa yolları bulmak için bir algoritma". Üç Aylık Uygulamalı Matematik. 27 (4): 526–530. doi:10.1090 / qam / 253822. BAY  0253822.
• Bannister, M. J .; Eppstein, D. (2012). Bellman-Ford algoritmasının rastgele hızlandırılması. Analitik Algoritmalar ve Kombinatorikler (ANALCO12), Kyoto, Japonya. sayfa 41–47. arXiv:1111.5414. doi:10.1137/1.9781611973020.6.

İkincil kaynaklar

• Bang-Jensen, Jürgen; Gutin Gregory (2000). "Bölüm 2.3.4: Bellman-Ford-Moore algoritması". Digraphs: Teori, Algoritmalar ve Uygulamalar (İlk baskı). ISBN  978-1-84800-997-4.CS1 bakimi: ref = harv (bağlantı)
• Schrijver, Alexander (2005). "Kombinasyonel optimizasyon tarihi üzerine (1960'a kadar)" (PDF). Ayrık Optimizasyon El Kitabı. Elsevier: 1-68.CS1 bakimi: ref = harv (bağlantı)
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Algoritmalara Giriş. MIT Press ve McGraw-Hill., İkinci baskı. MIT Press ve McGraw-Hill, 2001. ISBN  0-262-03293-7. Bölüm 24.1: Bellman – Ford algoritması, s. 588–592. Problem 24-1, s. 614–615. Üçüncü baskı. MIT Press, 2009. ISBN  978-0-262-53305-8. Bölüm 24.1: Bellman-Ford algoritması, s. 651–655.
• Heineman, George T .; Pollice, Gary; Selkow, Stanley (2008). "Bölüm 6: Grafik Algoritmaları". Özetle Algoritmalar. O'Reilly Media. s. 160–164. ISBN  978-0-596-51624-6.CS1 bakimi: ref = harv (bağlantı)
• Kleinberg, Jon; Tardos, Éva (2006). Algoritma Tasarımı. New York: Pearson Education, Inc.CS1 bakimi: ref = harv (bağlantı)
• Sedgewick, Robert (2002). "Bölüm 21.7: Negatif Kenar Ağırlıkları". Java'da Algoritmalar (3. baskı). ISBN  0-201-36121-3. Arşivlenen orijinal 2008-05-31 tarihinde. Alındı 2007-05-28.CS1 bakimi: ref = harv (bağlantı)