Category Archives: Algoritmalar

Greedy algoritmalar …, Böl. 2: Bağlı Bileşen Etiketleme


Önceki bölümde Kruskal Algoritması ile “Minimum Spanning Tree” bulurken;
1. Çözümü oluşturan küçük bileşenleri en iyiden en kötüye sıralamıştık.
2. Çözümü oluşturmak üzere birleştirmeye başlamıştık.

Bu yazıda birleştirme kuralı üzerinde duracağım:
En iyi parçaları alıp en az ağırlıklı ağacı oluştururken, birden fazla küçük ağaçlar(fidanlar 🙂 ) oluşacaktır.

Bu oluşumu takip edebilmek için, graftan aldığımız her yeni kenarı, var olan ağaçlar içinde ait olduğu ağacın etiketiyle etiketlemeliyiz. Yani o ağaca birleştirmeliyiz.

Başlangıçta, ilk aldığımız ağaç, herhangi bir ağaca ait olmayacağı için buna bir etiket verilir. Mesela 1. Ağaç denir. Daha sonra farklı bir ağaç oluştuğunda ona sırayla yeni numaralar verilerek farklı ağaç olduğu etiketlenir. Burada farklı bir ağaçtan kastettiğim şey, yeni eklenen kenarın var olan bir ağacın devamı olmayıp, ayrık olmasıdır.

Oluşan farklı ağaçları birleştirirken, graftan yeni alınan kenarın(ağacın);

  • var olan bir ağacın devamı,
  • iki farklı ağacı birleştirdiği,

kriterlerine bakarız.
Bu durumlar oluştuğunda, ağaçlar birleştirilir. Yani, farklı iki etiket, tek etiketle ifade edilir.

Bu etiketleme işleminin mantığı, aynı özellikte olan ve birbirine bağlı bileşenlerin bir grupta ifade edilmesidir. Bu işleme “Bağlı Bileşen Etiketleme” (Connected Component Labeling) adı verilir.

Bu yöntemin uygulanmasıyla döngü oluşmadan “min. spanning tree” oluşması sağlanır.

Sonuç:

“Greedy” algoritmaları bir anlamda “Recursive” algoritmalara benzetebiliriz.
Bir durma koşulu olması kaydıyla, temel bir işlem tekrar eder.

-- The End --

Copyright © 2010 – Taha Yavuz Bodur

Advertisements

Leave a comment

Filed under Algoritmalar

“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

Leave a comment

Filed under Algoritmalar