“Greedy” algoritmalar ve bir örnek: Kruskal Algoritması Böl.1

Elimizde bir problemin çeşitli olası çözümlerini içeren ve parçalayabileceğimiz bir çözüm uzayı olsun. Burada en iyi çözümü arayalım.

Burada ‘Greedy’ algoritma mantığına göre;
en iyi çözüm, bu çözümün büyüklüğünü oluşturacak sayıda iyi küçük parçaların birleşiminden oluşacaktır. Dolayısıyla çözüm kümesi parçalara ayrılır ve parçalar kendi arasında bir büyüklük/önemlilik/iyilik kriterine göre sıralanır. En iyi parçadan başlanarak, çözüm kendiliğinden oluşuncaya kadar iyilik sırasına göre yeni parça seçilir. Burada en iyiden başlayarak çözüm oluşuncaya kadar sürekli iyi parçaları seçtiğimiz için, bulunan çözüm en iyi çözüm olacaktır.

Burada temel prensip aşağıdaki cümlede özetlenmiştir:

A locally optimal choice is globally optimal.

Bu mantığı bir örnek algoritma üzerinde göstererek görselleştirelim.
Kruskal Algoritması, ‘Greedy’ seçim yöntemiyle Min. Spanning Tree bulan bir algoritmadır.

Problem:


Bir G(V,E) ağırlıklı grafı verilsin,
burada V={1,2,3,4} ve E={(1,2),(2,3),(2,4),(1,3),(3,4),(1,4)} olsun.
w=(u,v) olmak üzere, bu kenarların ağırlıkları sırasıyla,
W={5,15,30,20,10,25} olsun.

G(V,E) grafı şu şekildedir.

Bu graftan bir “Spanning Tree” elde etmek isteyelim.
Spanning Tree, bir grafın tüm düğümlerini içeren bir ağaçtır. Yani döngü yoktur ve tüm düğümlerden bir şekilde geçilir.

Eğer bu graftan bir Minimum Spanning Tree bulmak istiyorsak… (bu Spanning Tree’ lerden en az ağırlıklı olanı demektir.)

Bu grafta birden fazla farklı Spanning Tree çıkabilir:
1-2-3-4 ya da 1-2-4-3 gibi…
Bu farklı Spanning Tree’ ler bizim çözüm uzayımızı oluştursun. Buradaki en iyi çözüm min. spanning tree olacaktır.

En iyi çözümden bahsedildiği için ve çözümler parçalanabildiği için Burada Greedy Algoritma yöntemini kullanalım.

Çözüm kümesini yapıtaşlarına ayıralım.
Çözüm Kümesi : Verilen Graftaki Ağaçlar
Burada sorun, “en küçük yapıtaşı ne olarak seçilmeli ?” olacaktır.
Buna şöyle karar verilir:

Aranan çözüm: Bir ağaç.(Çözüm kümesini biraz küçüklttük)
Bir ağaç küçük ağaçlardan oluşur.( Daha da küçüklttük, Ne kadar küçük?)
Problemde Min. diye bahsedilen şey kenar ağırlıklarının min. olması.
O zaman en küçük yapıtaşı en azından bir kenar ağırlığı(iyilik kriteri) olan bir ağaç olmalı.

Dolayısıyla yapıtaşı bir kenar olarak bulunur. Yani,
wi = (ui,vi), i=1,2,3,4 olacaktır.

Min. Spanning Tree(MST) ağırlığı:

Burada n düğüm sayısıdır. Dolayısıyla bir spanning tree de (n-1) kenar vardır.
Burada kenarlar ağırlıklarına göre sıralanmıştır. i, bu sırayı gösterir.

Burada, genel çözüme uğraşmak için bu küçük parçalara bir birleşme kuralı koymalıyız ki ana ağaca oluşabilsin.

Bunu bu yazının 2. Bölümü olan Connected Component Labeling(Bağlı Bileşen Etiketleme) kısmında açıklayacağım.

Not-1: Bazı arkadaşlar, madem ki blogunda teknik konularda ingilizce yazacaktın, neden bunu Türkçe yazdın diyebilir. Bunu diğer bazı arkadaşlar neden teknik konularda İngilizce yazıyorsun dediği için yaptım. Ama, bunun İngilizce halini de farklı bir kategoride yayına koyacağım ;).

Not-2: Copyright © 2010 – Taha Yavuz Bodur

Advertisements

Leave a comment

Filed under Algoritmalar

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s