Greedy Algoritmalar

Giriş

Yarışmalarda sorulan 16 çeşit soru var. Bunlar şöyle. Bu liste genişletilebilir.

There are around 16 types of problems that the programmer face while programming, these problems include:

1. Ad-Hoc

2. BigNums

3. Knapsack

4. Greedy

5. Flood Fill

6. Shortest Path

7. Network Flow

8. Complete Search

9. Eulerian Path

10. Two-Dimensional

11. Dynamic Programming

12. Computational Geometry

13. Minimum Spanning Tree

14. Approximate Search

15. Recursive Search Techniques

16. Heuristic Search

4. Greedy Algoritmalar Nedir?

Greedy algoritmalar ilk buldukları çözümü döndürürler. Bu çözüm en optimal çözüm olmak zorunda değildir. Açıklaması şöyle

Sacrificing your time for the best solution is a noble cause, but there may come the times where the best solution is overkill and you don’t always the resources (time, money, etc.) to go after your ideals. In fact, you don’t always need the best solution either, just a fairly good one might suffice.

Hatta bazen çok kötü bir sonuç bile döndürebilirler. Bu gibi durumlarda ya algoritmayı iyileştirmek ya da Dynamic Algorithm kullanmak gerekir.

Örnek - Coin Change Problem

Elimizde çeşitli değerlerde bozuk paralar var. Örneğin {1,5,6,9} TL. Amacımız 11 TL elde etmek. Önce 11'e en yakın parayı seçeriz. Daha sonra kalan değere en yakın parayı seçeriz ve bu böyle devam eder. Kod olarak şöyle

std::vector<int> denominations = {1, 2, 5, 10, 20, 50, 100, 500};

void findMinCoins(int value)
{
  sort(denominations.begin(), denominations.end());

  std::vector<int> answer;

  for (int i = denominations.size() - 1; i >= 0; i--)
  {
    while (value >= denominations[i])
    {
      value = value - denominations[i];
      answer.push_back(denominations[i]);
    }
  }

  std::cout << "The value can be achieved in " << answer.size() << " coins" << std::endl;

  for (int i = 0; i < answer.size(); i++)
  {
    std::cout << answer[i] << " ";
  }
}

 
Örnek - Activity Selection Problem
Elimizde başlangıç ve bitiş zamanları belli faaliyetler olsun. Bunların bir kısmının zamanı çakışacaktır. En fazla faaliyeti seçmek isteyelim. Şu çözümlerden birisi tercih edebiliriz.
1 - En erken başlayan faaliyeti seç. Daha sonra bir sonraki en erken başlayan faaliyeti seç
2 - En erken biten faaliyeti seç. Daha sonra bir sonraki en erken biten faaliyeti seç
3 - En kısa faaliyeti seç. Daha sonra bir sonraki en kısa faaliyeti seç

Örnek - Fractional Knapsack Problem
Elimizde 10 birim alabilen bir kutu olsun. Bu kutuları greedy algoritma ile şöyle doldururuz.

Enter the number of objects: 6
Enter the weight of the objects: 7 5 2 3 5 8
Container 1 contains objects with weight [7.0, 2.0]
Container 2 contains objects with weight [5.0, 3.0]
Container 3 contains objects with weight [5.0]
Container 4 contains objects with weight [8.0]

12. Computational Geometry

Örnek - Curve Fitting Algoritması

Şeklen şöyledir. Elimizde noktalar varsa bu noktaları en iyi şekilde temsil edecek bir doğru bulunması istenir.