Algoritma üretme yöntemlerinden birisi olan açgözlü yaklaşımına göre mümkün olan ve sonuca en yakın olan seçim yapılır. Açgözlülük, parça parça bir çözüm parçası oluşturan bir algoritmik paradigmadır. Her zaman en açık ve acil yararı sunan bir sonraki parçayı seçer. Bir seçim yapılması gerektiğinde sonuca en çok yaklaştıracak olan seçimin yapılmasını önerir. Ancak bu seçim her zaman için en iyi seçim değildir. Yerel optimum daima global optimum anlamına gelmez. Dolayısıyla en iyi sonuca götürmeyebilir. Fakat bazı durumlarda en iyi sonuca götürür.(MST, En Kısa Yol Alg. ve Huffman Coding)
Açgözlü algoritmalar optimizasyon problemleri için kullanılır. Her adımda, şu anda en iyi görünen bir seçim yapabiliriz ve tüm problemin optimal çözümünü elde ederiz. Ancak açgözlü algoritmalar her zaman uygulanamaz. Örneğin, Fractional Knapsack problemi Greedy kullanılarak çözülebilir, ancak 0-1 Sırt Çantası Greedy kullanılarak çözülemez. Açgözlü algoritma, n hedef sayısı olmak üzere, O(n log n) karmaşıklığına sahip ve çok hızlı çözüm üreten bir tekniktir.
İşletim Sistemlerinde Açgözlü Algoritmalar
- First Fit algorithm in Memory Management
- Best Fit algorithm in Memory Management
- Worst Fit algorithm in Memory Management
- Shortest Job First Scheduling
1) First Fit Algorithm
S = {4,8,5,7,6,1,1,4,2,2} C=10
2) Best Fit Algorithm
S = {11,2,15,5,6,17,7} C=20
3) Worst Fit Algorithm
S = {4,8,5,1,7,6,1,4,2,2} C=10
Greedy Yaklaşım ile Çözülebilen NP Complete Problemler
- Gezgin – Satıcı Problemi
- Küme Örtüleme (Set cover problem)
- Kutulama Problemi (Bin Packing Problem)
- Graf Renklendirme (Graph Coloring)
- K-centers problemi
NP-Complete: Her adımdaki çözümleme zamanı kendinden önceki adımdaki çözümleme zamanlarından daha fazla olduğu için bu problem tiplerinin çokterimli zamanda (polynomial time) çözülmesi mümkün değildir. NP-Complete bir problem Belirsiz(Non-Deterministic) Turing Makinesi tarafından belirli zamanda çözülebilmektedir.
Bir yanıt yazın