bakimliyiz
Sponsor Reklamlar
Geri git   Bakimliyiz.Com > GENEL KÜLTÜR > Eğitim ve Öğretim

Kadın Portalı Kayıt Ol İletişim Forumları Okundu Kabul Et
Alt 24-05-2013, 04:50   #1 (permalink)
 
ebush - ait Kullanıcı Resmi (Avatar)
 
Standart Prim algoritması konu anlatımı

Prim algoritması konu anlatımı-Prim algoritması hakkında bilgi



Prim Algoritması ağırlıklandırılmış ve bağlı bir çizge üzerinde minimum örten ağaç (minimum spanning tree) bulan algoritmalardan birisidir. 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 = (uv) ş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


Prim algoritması konu anlatımı

Bu ç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 algoritması konu anlatımı


İ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 algoritması konu anlatımı

Seç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 algoritması konu anlatımı


Algoritma 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 D düğümleri işaretlenmişti. Bu yüzden bu ayrıt kullanılamaz.


Prim algoritması konu anlatımı

Bu durumda C E ve G'den birini seçebiliriz. C B'den 8 uzakta E B'den 7 uzakta ve G F'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 algoritması konu anlatımı


Burada sadece C ve G düğümlerini inceleyebiliriz. C E'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 algoritması konu anlatımı

G 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. Toplan ağırlığı ise burada 39 oldu.


ebush isimli Üye şimdilik offline konumundadır  





Hızlı Cevap

Doğrulama Sorusu
Mesajınız:
Yazı şeklini sil
Kalın
Eğik yazı
Altı çizik

Grafik ekle
Alıntı yap [QUOTE]
 
Alanı Küçült
Alanı Büyült

Seçenekler
Stil


Prim algoritması konu anlatımı

Prim algoritması konu anlatımı konusu, GENEL KÜLTÜR / Eğitim ve Öğretim forumunda tartışılıyor.



Benzer Konular

Konu Konuyu Başlatan Forum Cevap Son Mesaj
Ses konu anlatımı ebush Eğitim ve Öğretim 0 22-05-2013 08:43
Çözünürlük konu anlatımı ebush Eğitim ve Öğretim 0 18-05-2013 11:29
İvme konu anlatımı-Hız değişimi konu anlatımı ebush Eğitim ve Öğretim 0 17-05-2013 11:34
Çekim ekleri konu anlatımı-Yapım ekleri konu anlatımı ebush Eğitim ve Öğretim 0 13-05-2013 11:22
Can-Cant konu anlatımı ebush Eğitim ve Öğretim 0 13-04-2013 08:18

Üye olmadan soru sorabilirsiniz!

Bütün Zaman Ayarları WEZ +4 olarak düzenlenmiştir. Saat şuan 10:34 .


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
SEO by vBSEO 3.5.2 ©2010, Crawlability, Inc.
Web Stats