Yazan: Şadi Evren ŞEKER

Asgarai tarama ağacı, ağırlıklık bir ağda (weighted graph, yani her düğümü birbirine bağlayan yolların maliyeti (ağırlığı) olması durumu), bütün düğümleri dolaşan en kısa yolu verir. Örneğim aşağıdaki grafikte bütün düğümlere uğrayan en kısa yol işaretlenmiştir:

asgari tarama ağacı en kısa örten ağaç, minimum spanning tree

asgari tarama ağacını veren en meşhur algoritmalar:
Kruskal Algoritması
Prims Algoritması
Dijkstra Algoritması (Asgari tarama ağacının benzeri olarak bir arama algorimtası örneği)

Yorumlar

  1. yaşar olgan

    en küçük yayılma problemi lingo çözümü:
    İnceleyeceğiniz çoğu kaynaktaki karar modellerini lingoya aktarmada başarısız olursunuz çünkü en küçük yayılmada karar modeline düğümlerin döngü oluşturarak kopmalar oluşturmasını engelleyecek ekstra kısıtlar gerektirir bunu engelleyecek yapıyı vereceğim modelde aştım sizde ödevinizde gerekli yerleri değiştirerek kullanabilirsiniz zaten sadece parametre değerlerini ve sayısını değiştirmeniz gerektir büyük olasılıkla

    model:
    title örten agac;
    sets:
    dugum/1..6/;
    ayrit(dugum,dugum):a,x;
    endsets
    min=@sum(ayrit:a*x);
    @for(dugum(j)|j#ne#1:@sum(dugum(i)|i#ne#j:x(i,j))>=1);
    @for(dugum(i)|i#ne#6:@sum(dugum(j)|j#ne#i:x(i,j))>=0);
    @for(dugum(i):@for(dugum(j)|i#ne#j:x(i,j)+x(j,i)<=1));

    @for(ayrit|a#ne#0:@bin(x));
    data:
    a=0 15 14 35 32 25
    15 0 20 23 22 25
    14 20 0 30 26 21
    35 23 30 0 13 22
    32 22 26 13 0 18
    25 25 21 22 18 0;
    enddata
    end

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


− 6 = iki