Yazılım

Açgözlü Algoritma ( Greedy Algorithm ) – 3

admin20 Mayıs 20180 Comment40

Doğrusal Programlama problemlerinde verimli çalışmayan Greedy(Açgözlü) Algoritmalar Graflarda son derece iyi sonuçlar vermektedir.
Graflarda dolaşma yapılırken bir sonraki düğümü belirlemek için kullanılan bir karar verme seçme yöntemidir.
–Prim’in Minimum Kapsam Ağacı
–Kruskal’ın Minimum Kapsam Ağacı
–Sollin’in Minimum Kapsam Ağacı
–Boruvka’in Minimum Kapsam Ağacı
–Dijkastra’nın En Kısa Yolu Algoritması
–MST için ters silme algoritması
–Dial’in Algoritması
–Dijkstra’nın Komşuluk Listesi Temsili için Algoritması
–Bitişik liste temsili için Prim’in MST’si (Prim’s MST for adjacency list representation)

Greedy Seçim: Lokal olarak optimal seçim global olarak optimum çözümü oluşturur.

MST(Minimum Spanning Tree) Algoritmaları

Minimum Spanning Tree yani Minimum Kapsam Ağacı’nı belirlemek için birçok algoritma geliştirilmiştir. Bunlardan en önemlileri;

Prim Algoritması: En az maliyetli kenardan başlayıp onun uçlarından en az maliyetle genişleyecek kenarın seçilmesine dayanır. Sonuçta 1 tane ağaç oluşur.
Kruskal Algoritması: Daha az maliyetli kenarları tek tek değerlendirerek yol ağacını bulmaya çalışır.
Sollin Algoritması: Doğrudan paralel programlamaya yatkındır. Aynı anda birden çok ağaçla başlanır. İlerleyen adımlarda ağaçlar birleştirilerek tek bir yol ağacına dönüştürülür.

Prim Algoritması

Düğüm tabanlı bir algoritmadır. Bir kök düğüm ile başlar ve bütün düğümleri içine alıncaya kadar ağaç büyütülür. İşlem adımları;

Adım 1: Ağaç oluşturmak için herhangi bir noktayı başlangıç noktası olarak seç.

Adım 2: Oluşturulan ağaca eklemek için şu ana kadar oluşturulmuş ağaç üzerindeki erişilebilen ve daha önce ağaca katılmamış olan en küçük ağırlıklı kenarı seç.

Adım 3: Eğer bu kenarın ağaca katılması bir çember oluşmasına sebep olmuyorsa ağaca ekle.

Adım 4: Ağaçtaki kenar sayısı (N-1)’e ulaşana kadar ikinci adıma geri dön.

Kruskal Algoritması

Kruskal’ın algoritmasında, kenarları tek tek alarak bir MST oluştururuz. Greedy Seçim, şimdiye kadar MST’de bir döngüye neden olmayan en küçük ağırlık kenarını seçmektir.

Yol ağacını oluşturan kenarların tutulduğu A dizisini oluştur.

Graflardaki kenarları içeren K dizisini oluşturur.
Yol uzunluğuna başlangıç değeri verilir.

Sollin Algoritması

Adım 1: Her düğüm en küçük maliyet değerine sahip komşu düğümü belirler.
Adım 2: Belirlediği bu düğüm ile kendisi arasında bir kenar oluşturur. Bu belirleme sürecinde aynı kenarların birden fazla seçildiği durumda, ilkinden sonraki durumlar grafın yönsüz olması sebebiyle önemsiz kabul edilir.
Adım 3: Meydana gelen alt ağaçlar daha sonra kenar maliyeti değeri dikkate alınarak yeniden birleştirilir.
Uygulama sonunda tek bir ağaç elde edilene kadar devam edilir.

Öncelikle tüm ayrıtlar silinir.Yani başlangıç durumu yandaki gibi oluşturulur.

Düğümler sıralanır (a,b,c,d,e,f,g,h,i) ve sıradaki her düğüm için minimum maliyetli yollar seçilir.

a düğümü için (a-b) seçilir (en düşük maliyetli kenar)bu kenar çizilerek maliyeti M dizisine eklenir M={4}
b düğümü için (b-c) seçilir bu kenar çizilerek toplam minimum maliyet M dizisine eklenir. M={4+8}=12
c düğümü için (c-i) seçilir bu kenar çizilerek toplam minimum maliyet M dizisine eklenir, M={12+2}=14
d düğümü için (d-h) seçilir bu kenar çizilerek toplam minimum maliyet M dizisine eklenir, M={14+9}=23
e düğümü için (e-f) seçilir bu kenar çizilerek toplam minimum maliyet M dizisine eklenir, M={23+1}=24
f düğümü için (f-e) seçilir bu kenar daha önce çizildiği için maliyeti toplam minimum maliyet M dizisine eklenmez.
g düğümü için (g-h) seçilir bu kenar çizilerek toplam minimum maliyet M dizisine eklenir, M={24+2}=26. Bu aşamada d-g-haltağacı bulunur. Bu adımdan sonra altağaçlar birleştirilmelidir. Kalan düğümler içinden minimum maliyetlisi seçilerek birleştirme gerçekleştirilir.
g-c düğümleri en düşük olduğu için seçilip birleştirildi. M={26+4}=30
e-f alt ağacı aynı mantıkla f-i düğümü ile birleştirilerek ağacın son hali çizilir. M={30+6}=36.