Matematik Bilimi Tarihi

**Sürmenaj** · 18 Aralık 2024, 06:57

Prim Algoritması

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

Örnek

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.

İ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.

Seçilecek bir sonraki düğüm D veya A'ya en yakın olanı. B 9 uzakta (D den) E 15 ve FF düğümünü ve DF ayrıtını işaretliyoruz.

6. En yakın 6 o yüzden

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.

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ı.

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.

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.

Kaynak:Vikipedi özgür ansiklopedi

Konu Bilgileri
	Konu Basligi Matematik Bilimi Tarihi	Konudaki Cevap Sayisi 0
	Su an Bu Konuyu Goruntuleyenler Bu bilgi üye girişi gerektirir.	Goruntulenme Sayisi 83

18 Aralık 2024, 06:57	# 1
Çevrimiçi Sürmenaj Profil ayrıntılarını görüntüleyebilmek için kayıtlı kullanıcı olmanız ve üye hesabınızla oturum açmanız gerekmektedir.	Matematik Bilimi Tarihi Matematik Bilimi Tarihi Prim Algoritması 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 Örnek 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. İ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. Seçilecek bir sonraki düğüm D veya A'ya en yakın olanı. B 9 uzakta (D den) E 15 ve FF düğümünü ve DF ayrıtını işaretliyoruz. 6. En yakın 6 o yüzden 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. 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ı. 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. 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. Kaynak:Vikipedi özgür ansiklopedi Eğlence ❤Kalp Fırlat 🌸Çiçek Fırlat 💧Su Fırlat 💣Bomba Fırlat ↕Titret Benzer Konular Zaman Makinesi Nasıl Yapılır? Zaman Yolculuğu Bilimi \| Brian Cleg - Kitap Tanıtımları... Sabancı Üniversitesi ve Siro Temiz Enerji İş Birliği ile Yeni Yan Dal Programı: “Bata... Matematik Çocuğa Nasıl Sevdirilir?... Matematik mi Türkçe mi?... Matematik İle İlgili İlginç Bilgiler... 👍❤😂😮😡😢👎👏
	Alıntı Sesli Oku

Şu anda bu konuyu görüntüleyen etkin kullanıcılar: 1 (0 üye ve 1 konuk)

ForumKalbi