Açgözlü (Greedy) Algoritmalar

8 min readMay 25, 2020

Açgözlü Algoritmalar, optimizasyon problemlerinde kullanılan basit, uygulanması kolay ve sezgisel algoritmalardır. Sadece optimizasyon problemlerinde kullanılabilmelerine rağmen genel bir tasarım tekniği olarak kabul edilirler. Açgözlü algoritmalar ile problem çözümündeki temel yaklaşım, problemin küçük bir alt kümesi için çözüm oluşturmak ve bu çözümü problemin geneline yaymaktır. Algoritma içerisinde yapılan bir seçim, o an için doğru olsa bile sonraki seçimlerde olumsuz etki yapabilir. En çok kullanılan aç gözlü algoritmalar şunlardır;

⦁ Knapsack Problemi

⦁ Kruskal Algoritması

⦁ Dijkstra Algoritması

⦁ Prims Algoritması

⦁ Huffman Kodu’dur.

Veri Yapıları

Algoritmalardan bahsetmeden önce veri yapılarından bahsetmek gerekir.

Ağaç, verilerin birbirine sanki bir ağaç yapısı oluşturuyormuş gibi sanal olarak bağlanmasıyla elde edilen hiyerarşik yapıya sahip bir veri modelidir; bilgisayar yazılım dünyasında, birçok yerde / uygulamada programcının karşısına çıkar. Ağaca veri yapılarının işletim sistemlerinin dosya sisteminde, oyunların olası hamlelerinde ve şirketlerdeki organizasyon şeması vb. gibi birçok uygulama alanları vardır. Örneğin, NTFS dosya sistemi hiyerarşik dosyalama sisteminde kullanılmaktadır.

Ağaçlar (Trees), verilerin birbirlerine bağlanmasıyla oluşturulan, ağaç yapısına benzer bir yapıya sahip veri modelleridir. Bir ağacın her bir elemanına düğüm (node) denir. Veriler node’larda tutulur. Düğümler birbirlerine kenar (edge) ile bağlanır. Bu bağlantılar iki node arasındaki ilişkiyi gösterir.

Bir çizgenin (graf) ağaç olabilmesi için her iki düğüm arasında sadece bir yol olmalı, çevrim (cycle) olmamalıdır.

Knapsack Problemi

1 . Eşyanın ağırlığı 2, değeri 12.

2 . Eşyanın ağırlığı 1, değeri 10.

3 . Eşyanın ağırlığı 3, değeri 20.

4 . Eşyanın ağırlığı 2, değeri 15.

Hangi eşyanın daha değerli olduğunu değer/ağırlık formülünü uygulayarak bulabiliriz. Örneğin;

eşya 12/2=6$

eşya 10/1=10$

eşya 20/3=6,66$

eşya 15/2=7,5$

Bu durumda birim olarak değerlilik sıralaması eşya2>eşya4>eşya2>eşya1 olacaktır.

İlk olarak 1. eşyayı kontrol edeceğiz. Tabloda her iki tarafın da başına 0 koyarak başlamayı unutmayın. 1. eşyanın ağırlığı 2 imiş. Bu yüzden kapasite bölümünde 2’yi görene kadar 0 yazıyoruz. Kapasite bölümünde 2’yi gördük ve eşyanın kapasitesi de 2. Bu adımda eşyanın değerini yazıyoruz. Satırın sağ tarafına da 12$ yazmaya devam ediyoruz çünkü aynı eşyadan sadece bir kere alınabilir.

2.eşyaya geldiğimizde ise değerinin 1 olduğunu görüyoruz. Kapasite bölümünde 1 olan sütuna eşyanın değerini yazıyoruz, yani 10$. Kapasite 2 olunca bir önceki eşyayı kullanabiliriz. Daha ağır ancak fiyat olarak daha değerli. Bu yüzden 12$ yazıyoruz. Kapasite 3 olunca ise hem 1. hem de 2. eşyayı alabiliyoruz. Bu satırda en fazla 22$ değerinde eşya alabiliyoruz.

Not: Hangi eşyadaysanız o eşyadan önceki eşyaları kullanabilirsiniz. Örneğin 2. eşyada olan biri 1. eşyayı kullanabilir ancak 3. eşyayı kullanamaz.

Kruskal Algoritması

En basit graf algoritmalarından biridir. Amaç bir graf içerisinde tüm düğümleri kapsayan minimum maliyete sahip ağacı elde etmektir.

Kruskal algoritmasında bir graf yapısındaki tüm kenarlar küçükten büyüğe doğru sıralanır. En küçük kenarlardan başlayarak ağaç oluşturulur. Ağaç yapısını bozacağı için cycle oluşmasına neden olan kenar tarama ağacına eklenmez. Cycle oluşması demek, kenarı çizdiğimizde kapalı bir alanın oluşmasına sebebiyet verilmesi demektir. Bu algoritmada temel kriter, kapalı alandaki tüm düğümlerin ziyaret edilmiş olması ve iki düğümü cycle oluşturmadan birleştirmektir.

NOT: Graf üzerinde bir noktadan başlayıp aynı noktaya tekrar ulaşabiliyor isek cycle var demektir.

Örnek:

İlk önce tüm kenarlar (düğümleriyle birlikte) maliyetlerine göre küçükten büyüğe sıralanır.

İlk adımda ilk sıradaki H-G düğümünü ekleriz.

İkinci Adımda G-F kenarını ağacımıza ekleriz. G düğümü zaten ağacımızda olduğu için F düğümünü bağlarız.

Bu adımda üçüncü sıradaki kenarımız olan I-C kenarını ayrık bir biçimde ekleriz. Çünkü bu kenarın mevcut düğümlerle bağı (henüz) yok.

Kenar listemize bakarsak bu adımda A — B kenarımız bulunuyor. Bu kenarı da ağacımıza ekliyoruz.

C-F arasına kenarını da ağacımıza ekliyoruz.

Listeye bakacak olursak sırada I-G kenarı var ama bu kenarı eklemeyiz. Çünkü I-G kenarını eklersek Cycle oluşturmuş oluruz. Eğer ekleseydik I-G-F-C içinde cycle oluşturmuş olacaktık ve yapımız ağaç niteliğini kaybedecekti.

I-H kenarı var, yine cycle oluşturuyor, bu yüzden bu kenarı eklemeyiz.

Bu adımda C-D kenarımız bulunuyor. (8. sıradaki kenar) C düğümümüz ekli ama D düğümü henüz eklenmemiş.

Sıradaki adımda B-C kenarımız bulunuyor. Her iki düğümde ziyaret edildiği için ekleme yaparken dikkatli olacağız. Baktığımızda cycle oluşturmadığını görüyoruz. Bu yüzden ekleyebiliriz.

A-H kenarı var. Ancak bu kenarı ekleyemeyiz. Tekrar Cycle oluşturmuş oluruz. Kontrol edelim A-H-G-F-C-B-A cycle oluşturuyor.

D-E kenarı var. D düğümü ziyaret edilmiş ancak E henüz eklenmemiş. E düğümünü ekleyip kenarı birleştiriyoruz.

Tüm düğümleri ziyaret etmiş olduk. Diğer adımlarda her kenar cycle oluşturacağı için eklenmeyecektir.

Dijkstra Algoritması

Komşu düğümlerden en yakın olan seçilerek hedefe ulaşılmaya çalışılır.

Dijkstra algoritmasında bir tane başlangıç noktası seçilir. Geri kalan tüm düğümler sanki sonsuz uzaklıktaymış gibi düşünülmelidir. Biz düğümlere ulaştıkça uzaklıkları güncelleriz. Dijkstra’da her adımda bir düğümden çıkan komşulara bakılır ve daha kısa bir yol bulunmuşsa uzaklıklar güncellenir. Ve yine kendisine en yakın olan düğüme gidilir. Bu şekilde tüm graf üzerindeki düğümler dolaşılır ve en kısa yol bulunmuş olur.

Örnek:

Aşağıdaki graf üzerinden algoritmayı anlamaya çalışalım. A’dan F’ye en kısa yolu bulalım.

A düğümünden başlayarak değerleri tablomuza yazalım. A’ya bağlantısı olmayan düğümler için tabloya sonsuz değerini yazıyoruz.

Ardından E düğümü için B ve F düğümlerine bağlantısı olmadığı için sonsuz değerini yazıyoruz. İlk tablomuzda E düğümüne 2 değerini vermiştik. E’den C’ye gidiş değeri 1+2=3 olur. E’den D’ye gidiş değeri 2+10=12 olur.

C düğümünden gidilemeyen tek düğüm F düğümü olduğu için tabloya sonsuz değeri yazıyoruz. C’den B düğümüne gidiş maliyeti 3+3=6 olur. C düğümünden D düğümüne gidiş maliyeti 3+8 = 11 olur. E düğümü daha önce ziyaret edildiği için tabloya yazılmaz.

B düğümünden F’ye gidiş maliyeti 6+6 = 12 olur. B düğümünden D düğümüne gidiş maliyeti 6+2 = 8’dir.

D düğümünden F düğümüne gidiş maliyeti 8+3 = 11’dir.

Son olarak A’dan F’ye giden en kısa yol A — E — C — B — D — F’dir. Yol 11 adımda bulunur. Grafın son hali aşağıdaki gibidir.

Prims Algoritması

Prims algoritmaları hem graflar hem de ağaçlar üzerinde uygulanabilir. Algoritmanın amacı sistem içerisindeki tüm düğümleri en az maliyetle dolaşmaktır. İlk olarak ağaçlara yönelik oluşturulmuştur. Zaten algoritmanın çalışma mantığı Asgari tarama ağacı (MST-Minimum Spanning Tree) oluşturarak tüm düğümleri gezmektir. Yani kaç tane düğümümüz olursa olsun, prims algoritmasının hedefi o graf yapısı içerisinde bir tarama ağacı oluşturarak tüm düğümlere varmayı hedefler.

⦁ Başlangıç olarak herhangi bir düğüm seçilir.

⦁ Her adımda bulunulan düğüme en yakın (ağaca önceden dahil olmamış) düğüm ağaca dahil edilir.

⦁ Eşit mesafede iki düğüm varsa belirlenen kurala göre biri tercih edilir.

⦁ n düğüm için n-1 adet iterasyon gerçekleşir.

Örnek:

Alttaki graf yapısına Prims algoritmasını uygulayalım.

Başlangıç düğümü olarak A düğümü seçiyoruz. A’nın komşuları B ve C’dir. C düğümü en düşük maliyetli olduğu için C düğümünü işaretliyoruz.

Grafa baktığımızda D ve B düğümünü bağlayabileceğimizi görüyoruz. D düğümünün maliyeti az olduğu için D düğümünü de işaretliyoruz.

Tekrar grafa baktığımızda ekleyebileceğimiz düğümler B, C ve D olduğunu görüyoruz. B düğümünü ekliyoruz. Burada hangi düğümü eklediğimiz fark etmiyor sadece çevrim (cycle) oluşmamasına dikkat ediyoruz.

F düğümü çevrim oluşturmaya çok müsait gözükmekte. En az maliyete sahip ve çevrim oluşturmayacak düğümü noktası C olarak gözüküyor. F düğümünü de ekliyoruz.

F düğümüne artık bir düğüm daha ekleyemiyoruz çünkü direk çevrim oluşturmakta. Geriye B ve D düğümü kalmakta. E düğümüne giden en az maliyet B’den giden kenar olduğu için o kenarı işaretliyoruz.

Artık daha düğüm ekleyemiyoruz çünkü diğer kenarlardan çevrim oluşmakta. Toplam uzunluğu hesaplayacak olursak;

A-B-C-D-F-E

1+1+2+2+2= 8.

Huffman Kodu

Huffman Kodu, veri sıkıştırma için kullanılan kayıpsız bir algoritmadır. David A. Huffman tarafından 1952 yılında bulunmuştur. Bu kodlama değişken uzunlukta bir kodlama olup bu kodlama mors kodlamasının tersine veri setindeki karakterlerin frekansına bağlıdır. Algoritma, bir veri setinde daha çok rastlanan bir sembolü daha düşük uzunluktaki kodla, daha az rastlanan sembolü ise daha büyük uzunluktaki kodla temsil edilmesine dayanmaktadır.

Veri setindeki sembol sayısına ve bu sembollerin tekrarlama sayısına bağlı olarak %10 ile %90 arasında değişen oranlarda bir sıkıştırma elde edilebilir.

⦁ İlk olarak, veri setine ait frekans tablosu oluşturulur.

⦁ Ardından, hangi karakterin hangi bitlerle temsil edileceğini gösteren Huffman ağacı oluşturulur.

Örnek:

Veri setine ait frekans tablosu aşağıdaki gibi olsun.

SEMBOL FREKANS

A 60

B 40

C 25

D 20

E 10

Huffman ağacındaki en son düğümleri oluşturacak olan bütün semboller frekanslarına göre küçükten büyüğe doğru sıralanırlar.

En küçük frekansa sahip olan iki sembolün frekansları toplanarak yeni bir düğüm oluşturulur. Oluşturulan bu yeni düğüm var olan düğümler arasında uygun yere yerleştirilir. Bu yerleştirme frekans bakımından küçüklük veya büyüklüğe göredir.