Çizgi Roman: Resmin en kısa yolu nasıl bulunur? | Teknik Başlıklar
Yazar | Programcı Xiaohui
Bu makale, programcı Xiaohui'nin izni ile yeniden basılmıştır (ID: chengxuyuanxiaohui)
----- sonraki gün -----
Xiao Hui'nin fikirleri aşağıdaki gibidir:
İlk adım, A köşesinden diğer köşelere en kısa mesafeyi bulmak için Dijkstra algoritmasının uzaklık tablosunu kullanmaktır:
İkinci adım, B köşesinden diğer köşelerin her birine en kısa mesafeyi bulmak için Dijkstra algoritmasını kullanmaya devam etmektir.
Üçüncü adım, tepe C'den her bir tepe noktasına en kısa mesafedir.
Tepe D'den başlayarak dördüncü adım ...
.......
Aynen bunun gibi, tepe G'ye geçildi.
Bu fikrin zaman karmaşıklığı nedir?
Grafikte n tane köşe varsa, yığın optimizasyonu dikkate alınmazsa, Dijkstra algoritmasının zaman karmaşıklığı O (n ^ 2) olur. Bu nedenle, her tepe noktasını bir kez hesaplamak için toplam zaman karmaşıklığı O (n ^ 3) olur.
Bir kestane ver:
Yukarıdaki şekilde, tepe A ve tepe C'nin doğrudan bağlı kenarları yoktur ve aralarındaki doğrudan mesafe sonsuzdur.
B "röle tepe noktası" olarak alınırsa, A'dan C'ye en kısa yol A-B-C'dir ve en kısa mesafe 3 + 2 = 5'tir.
Bir kestane daha ver:
Yukarıdaki şekilde A tepe noktası ve C tepe noktası doğrudan bağlıdır ve mesafe 6'dır. Ama "dairesel" bir A-B-C yolu var, mesafe 3 + 2 = 5 < 6.
Bu nedenle, röle tepe noktası B'den sonra, A'dan C'ye en kısa mesafe 5 olabilir.
Floyd'un algoritmasının ayrıntılı adımlarına bir göz atalım.
1. Floyd algoritmasını uygulamak için önce ağırlıklı bir grafik içeren bir bitişik matris oluşturmanız gerekir:
Bitişik matrisinde, her sayı bir tepe noktasından başka bir tepe noktasına doğrudan mesafeyi temsil eder, bu mesafe herhangi bir röle tepe noktası içermez.
2. Bir röle tepe noktası olarak sadece A tepe noktasına izin verildiğini varsayarsak, köşeler arasındaki mesafe neye benzeyecektir?
B ve C arasındaki mesafe başlangıçta sonsuzdu, şimdi röle olarak A kullanılarak, mesafe AB mesafesi + AC mesafesi =
5 + 2 = 7.
İlgili matris öğelerini güncelleyin (turuncu alan, tepe A'dan diğer köşelere olan geçici mesafeyi temsil eder):
3. Ardından, A ve B köşelerini röle köşeleri olarak kullanarak, köşeler arasındaki mesafe nasıl görünecek?
A ve D arasındaki mesafe başlangıçta sonsuzdu Bu sırada röle olarak B ile mesafe AB mesafesi + BD mesafesi = 5 + 1 = 6 olacak şekilde kısaltılır.
A ve E arasındaki mesafe başlangıçta sonsuzdu.Bu sırada röle olarak B kullanılarak, mesafe AB mesafesi + BE mesafesi = 5 + 6 = 11 olacak şekilde kısaltılır.
İlgili matris öğelerini güncelleyin (turuncu alan, köşe B'den diğer köşelere olan geçici mesafeyi temsil eder):
4. Ardından, A, B ve C köşelerini röle köşeleri olarak kullanarak, köşeler arasındaki mesafe nasıl görünecek?
A ve F arasındaki mesafe başlangıçta sonsuzdu.Bu sırada, röle olarak C kullanılarak, mesafe AC mesafesi + CF mesafesi = 2 + 8 = 10 olacak şekilde kısaltılır.
İlgili matris öğelerini güncelleyin (turuncu alan, C köşesinden diğer köşelere olan geçici mesafeyi temsil eder):
Benzetme yaparak, sürekli olarak yeni röle köşeleri tanıtıyoruz ve matristeki geçici mesafeyi sürekli yeniliyoruz.
Son olarak, tüm köşeler röle köşeleri olarak kullanılabildiğinde, uzaklık matrisimiz şu şekilde güncellenir:
Şu anda, matristeki her öğe, bir tepe noktasından başka bir tepe noktasına en kısa mesafeye karşılık gelir.
Neden öyle diyorsun? Dinamik programlamanın iki unsurunu gözden geçirelim:
Sorunun ilk hali
Problem durumu geçiş denklemi
Grafiğin tüm köşeleri arasındaki mesafeyi bulma problemi için, başlangıç durumu bitişik matris olan köşeler arasındaki doğrudan mesafedir.
Ve sorunun durum geçiş denklemi nedir?
Yeni tanıtılan röle köşesinin n olduğunu varsayarsak, o zaman:
Tepe i'den tepe j'ye yeni mesafe j = Min (tepe noktasından j tepe noktasına olan eski mesafe, tepe noktası i'den tepe noktasına olan mesafe n + köşe n'den j köşesine olan mesafe)
