Algoritma Greedy

Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan
optimasi (persoalan untuk mencari solusi optimum) .

Hanya ada dua macam persoalan optimasi :

1. Maksimasi (maximization)

2. Minimasi (minimization)

Prinsip greedy: “take what you can get now!”.
Algoritma greedy membentuk solusi langkah per langkah (step by step). Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.  Pada kebanyakan kasus, algoritma greedy tidak akan menghasilkan solusi paling optimal, begitupun algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.

Pseucode untuk algoritma greedy

set Greedy (Set Candidate){

   solution= new Set( );

   while (Candidate.isNotEmpty()) {

     next = Candidate.select(); //use selection criteria,

                 //remove from Candidate and return value

     if (solution.isFeasible( next)) //constraints satisfied

   solution.union( next);

       if (solution.solves()) return solution

    }

   //No more candidates and no solution

   return null

}

Algoritma greedy merupakan algoritma yang besifat heuristik, mencari nilai maksimal sementara dengan harapan akan mendapatkan solusi yang cukup baik. Meskipun tidak selalu mendapatkan solusi terbaik (optimum), algoritma greedy umumnya memiliki kompleksitas waktu yang cukup baik, sehingga algoritma ini sering digunakan untuk kasus yang memerlukan solusi cepat meskipun tidak optimal seperti sistem real-time atau game.

Algoritma greedy memiliki beberapa fungsionalitas dasar, yaitu:

1. Fungsi untuk melakukan penelusuran masalah.
2. Fungsi untuk memilih local maximum dari pilihan-pilihan yang ada tiap langkahnya.
3. Fungsi untuk mengisikan nilai local maximum ke solusi keseluruhan.
4. Fungsi yang menentukan apakah solusi telah didapatkan.