21 Nisan 2012 Cumartesi

Prim Algoritması Nedir



Prim Algoritması ağırlıklandırılmış ve bağlı bir çizge üzerinde minimum örten ağaç (minimum spanning tree) problemine çözüm bulma algoritmalardan birisidir.

Çözüm ve sözdekod

Ayrıtların bir alt kümesini, tüm düğümleri kapsayacak ve ayrıtların toplam ağırlığını minimum yapacak şekilde bulur. Bağlı olmayan bie çizgeye uygulandığında sonucu bağlı bileşenlerden yalnız birisi için bulur. Bu algoritma 1930 yılında matematikçi Vojtech Jarnik tarafından bulunmuştur. Daha sonra bağımsız olarak 1957'de bilgisayar bilimcisi Robert C. Prim ve 1959'da Dijkstra tarafından tekrar bulunmuştur. Bu nedenle bu algoritmaya DJP veya Jarnik algoritması da denir.

Sözdekod'u aşağıdaki gibi verilebilir:


 function Prim(çizge N)
T : kapsayan ağaç
B : eklenmiş düğümler
B <- rastgele bir düğüm
while B<>N do
e = (u,v) şeklinde en hafif ayrıtı bul oyle ki u B'nin elemanı olsun ve v N\B 'nin elemanı olsun
T <- T U {e}
B <- B U {v}
endwhile
return T

Örnek

Prim Algorithm 0.svgBu çizgenin orijinal hali. Ayrıtların üzerindeki sayılar ağırlıkları. Ayrıtlardan hiç biri henüz seçili değil ve D düğümü başlangıç düğümü olarak rastgele seçildi.
Prim Algorithm 1.svgİkinci olarak seçilecek düğüm D'ye en yakın olanı. A 5 , B 9, E 15, ve F 6 uzaklıkta. Bunlardan en küçüğü 5 dolayısıyla A düğümünü ve DA ayrıtını işaretliyoruz.
Prim Algorithm 2.svgSeçilecek bir sonraki düğüm D veya A'ya en yakın olanı. B 9 uzakta (D den), E 15, ve F 6. En yakın 6 o yüzden F düğümünü ve DF ayrıtını işaretliyoruz.
Prim Algorithm 3.svgAlgoritma aynı şekilde devam ediyor. B düğümü A'dan 7 uzakta ve işaretli. Burada DB ayrıtı kırmızı olarak işaretlendi çünkü daha önce hem B hem de Ddüğümleri işaretlenmişti. Bu yüzden bu ayrıt kullanılamaz.
Prim Algorithm 4.svgBu durumda CE ve G'den birini seçebiliriz. CB'den 8 uzakta, EB'den 7 uzakta ve GF'den 11 uzakta. En yakın E olduğu için onu ve EB ayrıtını işaretliyoruz. Diğer iki ayrıt kırmızı çünkü onları bağlayan düğümler kullanıldı.
Prim Algorithm 5.svgBurada sadece C ve G düğümlerini inceleyebiliriz. CE'den 5 uzakta ve G ise 9 uzakta. C'yi ve EC ayrıtını seçiyoruz. Ayrıca BC'yi de kırmızı olarak işaretliyoruz.
Prim Algorithm 6.svgG düğümü kalan son düğüm. F'den 11 uzakta ve E'den 9 uzakta. Bu nedenle E'yi ve EG'yi işaretliyoruz. Tüm düğümleri eklediğimize göre en hafif kapsayan ağaç yeşil olarak gözüküyor. Toplam ağırlığı ise burada 39 oldu.



tr.wikipedia.org

0 yorum:

Yorum Gönder

RSS FeedRSS

 
Design by Free WordPress Themes | Bloggerized by Lasantha - Premium Blogger Themes | Macys Printable Coupons