Greedy Algoritması Nedir?

1. Açgözlü Algoritma Nedir?

Gelecek adım, avlanmaya, üzerine sabitlenmeden ve açgözlü, yani açgözlü algoritma olarak adlandırılan mevcut koşulları hesaba katmadan optimal bir sonuç için yaklaşmaktır. Amacı, şık sonucu yukarıdan aşağıya bir yaklaşımla modellemektir.

2. Greedy bir Algoritma nasıl üretilir?

Kırmak istediğimiz sorunun odağına göre, önce sahip olduğumuz set sıralanmalı. Sorunun odağına göre küme tamamen küçültülmeli ve işlem bu sıralanmış küme üzerinden dibe iner gibi tekrarlanmalıdır. Örnek olarak, bir torbayı maksimum gelirle doldurmak istiyorsanız, ürün değerleri en yüksekten en küçüğe doğru sıralanır ve kapasitemiz temelinde normal torba doldurulmaya başlanır.Örnek olarak, bir efor sıralaması isteniyorsa, koşullandırma bu ortamda bitiş zamanlarına göre sıralanabilir, çünkü öncelik kemikleri

erken bitiş zamanlarına sahip olanlar olacak, bitiş zamanı en başından en arkaya doğru sıralanabilir. Bunun için açgözlü bir yaklaşım karar değişkeni tutulur ve anlaşmalar yapılır, bu ortamda bir hazır giyim tesisinin maksimum etkinliğe sahip ürün dağılımı da modellenebilir, bir süt tesisinin maksimum süt litresini taşıma duygusu da modellenebilir. Verileri sıraladıktan / sıraladıktan sonra, istenen koşul kullanılabilir kümeyle yeniden kullanılmalıdır.

3. Bazı iyi bilinen Greedy Yaklaşımlar şunlardır

En yaygın kullanılan Açgözlü algoritmalar Sırt Çantası, Dijkstra, Huffman, Etkinlik Seçimi, Asal Sayılar ve Kruskal Algoritmaları olarak söylenebilir. Bazılarını biraz daha ayrıntılı olarak açıklayalım. Her şeyden önce, efor Seçimi Problemi için geliştirilen Açgözlü yaklaşım algoritması hakkında konuşalım. Bu problemde bir takım şartlandırmalar vardır ve bu şartlandırmaların başlangıç ve bitiş zamanları bilinmektedir. Aynı zamanda, soru maksimum eforun nasıl seçileceğine odaklanır, böylece sadece bir efor adlandırılabilir. Açgözlü yaklaşımın talep ettiği gibi, sahip olduğumuz kümeden en yakın bitiş zamanı eforunu kaldırdığımızda, bıraktığımız değiştirilmiş kümemiz için optimize edilmiş bir sonuç aramalıyız. Başka bir deyişle, bir S kümemiz olduğunu göstermemiz gerekirse, a’nın en önde gelen zaman bitiş zamanı olan efor olmasına ve B’nin optimize edilmiş sonucumuz olmasına izin verin, böylece bir S – a = S ‘kümesi üretecek ve optimize edilmiş sonuç S B de sonuç olacaktır S ‘ A. Başka bir deyişle, aynı zamanda S – aset.In bu şekilde, optimize edilmiş sonucumuzu yorumlayabiliriz, böylece hiç çaba sarf etmeyene kadar ilerleyebiliriz.Ancak, yasa tasarısı, yorumlamak gerekiyorsapseudocode.İkincisi, Knapscak sorununa Açgözlü yaklaşım hakkında konuşalım. Dinamik programlamada, temeli çantamızdaki / çantamızdaki / kutumuzdaki nesneleri doldurmak olan Sırt çantası problemi de Açgözlü Algoritmada yaklaşık farklılıklar içerir. Dinamik programlamada, ikili( 0- 1) Sırt Çantası modeli olduğunda, işlemler Açgözlü kemikte kesirli, yani kısmi nesnelerle gerçekleştirilir

. Bunun bir örneği, çantamı plaj, altın tozu vb. Gibi aksesuarlarla doldurmaya çalıştığım durumlar olabilir. Benzer durumlarda, malzemenin maksimum değerini dolduracak şekilde ilerlemiştir. Bunun için karşılaştırabileceğimiz verilere ihtiyacımız var, tüm ürünü değerine / kütlesine göre akıcı bir şekilde sıralayabiliriz. Sıralama ile başladığımız açgözlü yaklaşımda, sıralanmış ürünleri doldurmaya başlıyoruz ve kapasitemizin if koşulu ile dolu olup olmadığını kontrol ediyoruz. Ürünleri doldurdukça, kazancımızı ve kapasitemizi revize ediyoruz, biri artacak, diğeri düşecek. Sonunda, kapasitemiz yetersiz kaldığında, sıralamaya göre doldurulacak bir algoritmaya sahip olacağız, yani maksimum karı elde edebiliriz. Sonunda, Huffman yasası algoritması üzerinde durabiliriz. Huffman yasası, etkin veri daralmasını sağlamak için temsili veri sayısını azaltmak için kullanılan bir algoritmadır. tipik olarak, rakamları temsil etmek için bir çift taban üzerinden bit rakamlarını hesaplarken, bunları Huffman yasasında kullanım sıklıklarına dayanan bir ağaç üzerinden bit hesabına dahil etmeniz önerilir. Bu süreç şu şekilde işliyor, k karakterinin 45 bin kez geçtiği bir tren düşünelim, l karakteri 13 bin kez, m karakteri 9 bin kez, n karakteri 16 bin kez, t karakteri 5 bin kez, p karakteri 12 bin kez bu dosyada.Normalde bu 6 karakteri çift hesapla bit hesabına eklemek için en az 3 bit gerekir ( 23 = 8 rakam şeklinde tutulabilir.). Bu, (13bin 12bin 9bin 5bin 45bin 16bin) * 3 bit = 300bit ihtiyacına karşılık gelir. yine de, huffman yasasını sıklık ile eşleştirmek ve bunları ağaca yerleştirmek için kullanırsak, genellikle Huffman temsili bit rakamlarının bulunduğu bir sıklık ağacı elde ederiz, sol ele 0 ve sağa 1 veririz.Bu örnek için, en sık görülenlerden en nadir görülenlere, 0, 111, 101, 100, 1101, 1100 ve frekansları ile çarpıldığında, 300 bin bitten daha düşük bir yer kaplayacaklar.

 

4. Greedy Algoritma ve Dinamik Programlama yorumu

Açgözlü ve Dinamik Programlamanın karşılaştırılmasında, her ikisinde de en uygun sonuç aranır. Açgözlü yaklaşımda bir seçim öğesi tutulur, dinamik programlamada durum böyle değildir. Bu öğe, en iyi sonuç için karar değişkenini temsil eder. Değişken üzerinde seçim yapıldıktan sonra alt problemler cevaplanır ve devam ettirilir. Dinamik programlamada her adımda bir seçenek vardır ve bu seçim alt sorunların en iyi sonuçlarını etkileyebilir. Ancak açgözlü yaklaşımda, bu durum şu anda yaklaşmakta olan yolun seçimlerine veya sonuçlarına bağlı olabilir, çünkü bu şekilde tasarlanmamıştır. Dinamik programlama, ezberlemeye dayalı tam bir aşağıdan yukarıya stratejiye sahipken, açgözlü yaklaşım, ezberlemeye dayalı tam bir yukarıdan aşağıya stratejiye sahiptir. Başka bir deyişle, açgözlü seçim değişkeni her adımda artırılır ve genel olarak azaltılarak hesaplanır, dinamik programlamada bu durum tersine çevrilebilir. Özetle, açgözlü yaklaşım yukarıdan aşağıya bir stratejiye sahipken, dinamik programlama aşağıdan yukarıya bir stratejiye sahiptir.

Bunları da sevebilirsiniz

Bir cevap yazın

E-posta hesabınız yayımlanmayacak.