Algoritma Greedy

Hallo !!! kembali lagi dengan kami pada postingan sebelumnya kita telah mengetahui bagaimana menganalisis matematis algoritma rekursif. Pada kesempatan kali ini kita akan membahas salah satu algoritma greedy . Jika belum belum tahu apa itu algoritma greedy . Anda sangat beruntung sekali masuk ke blog kami dan akan membahas detail satu persatu sehingga kalian bisa dengan mudah memahami Algoritma Greedy ini .

1. Definisi Algoritma Greedy

          Algoritma Greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum (local maximum) sementara pada setiap langkahnya . Algoritma nini merupakan metode yang paling populer untuk memecahkan suatu persoalan optimasi .  

Sebagai contoh masalah sehari – hari yang menggunakan prinsip algoritma greedy salah satunya adalah mencari jalu tercepat/tersingkat dari UNIKOM menuju Trans Studio Mall . 

Algoritma greedy disini membuat solusi langkah per langkah , banyak sekali pilihan yang perlu di eksplorasi pada setiap langkahnya . Oleh karena itu , setiap langkah harus dibuat keputusan yang tepat untuk menentukan pilihannya . Suatu keputusan yang sudah diambil tidak boleh diubah lagi pada langkah selanjutnya .

Perhatikan gambar dibawah ini :

Misalnya kita ingin bergerak dari UNIKOM menuju ke Trans Studio Bandung dan kita telah menemukan beberapa jalur dari peta . Suatu sistem peta (Google Maps) pada gambar secara otomatis mencari jalur tercepat menuju lokasi degan waktu kira-kira 37 menit perjalanan tanpa macet . Pada gambar diatas pada dasarnya menunjukan titik – titik yang saling berhubungan , dengan jarak tertentu dan waktu tertentu pada masing-masing titik tersebut . Misalkan peta diatas kita dipresentasikan dengan titik-titik penghubung seperti berikut :

Dari gambar di atas, kita dapat melihat bagaimana sebuah jalur perjalanan dapat dipresentasikan dengan menggunakan graph misal A = UNIIKOM dan B = TSM (Trans Studio Mall). Maka dari itu, untuk menyelesaikan suatu masalah jarak terpendek kita menggunakan struktur data graph untuk merepresentasikan peta. Berikut graph yang digunakan :

k   Untuk mencari jarak terpendek dari B ke A, langkah – langkah algoritma greedy adalah sebagai berikut:

1. Kunjungi satu titik pada graph , dan ambil seluruh titik yang dapat dikunjungi dari titik sekarang
      2.Cari local maximum ke titik selanjutnya.
      3. Tandai graph sekarang sebagai graph yang telah dikunjungi, dan pindah ke local maximum yang telah ditentukan .
      4. Kembali ke langkah 1 sampai titik tujuan didapatkan.

Jika pada graph B ke A kita akan mendapatkan pergerakan seperti berikut :
- Mulai dari titik awal (B). Ambil seluruh titik yang dapat dikunjungi.

- Local Maximum adalah C, karena jarak ke C adalah yang paling dekat .
- Tandai A sebagai titik yang telah dikunjungi, dan pindah ke C
- Ambil seluruh titik yang dapat dikunjungi dari C

- Local Maximum adalah ke G, karena yang paling dekat.
- Tandai C sebagai titik yang telah dikunjungi , dan pindah ke G
- Ambil seluruh titik yang dapat dikunjungi dari G

- Local Maximum adalah ke I, karena yang paling dekat.
- Tandai G sebagai titik yang telah dikunjungi , dan pindah ke I
- Ambil seluruh titik yang dapat dikunjungi dari I

- Local Maximum adalah ke A, karena yang paling dekat.
- Tandai I sebagai titik yang telah dikunjungi , dan pindah ke A
- Tandai semua titik yang sudah dikunjungi

Dengan menggunakan algoritma greedy pada graph diatas , maka hasil akhir yang kita dapat sebagai jarak terpendek adalah B-C-G-I-A. Hasil jarak terpendek yang didapatkan ini tidak tepat dengan jarak terpendek yang sebenarnya (B-C-F-A). Algoritma greedy memang tidak selamanya memberikan solusi yang optimal dan akurat , dikarenakan pencarian local maximum pada setiap langkahnya tidak memperhatikan solusi secara keseluruhan .

Contoh kasus dari algoritma greedy :

1. Penukaran Koin

Diberikan uang senilai A. Tukar A = 73 dengan koin-koin yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut.

Tersedia koin 1, 5, 10, 25. Uang A = 73 akan ditukarkan. Berapa koin yang ditukarkan?

Cara 1 : 73 = 1 + 1 + 1 + .... + 1 (73 koin)

Cara 2 : 73 = 5 + 5 + 5 + .... + 1 + 1 + 1 (17 koin)

Cara 3 : 73 = 10 + 10 + 10 + .... + 1 + 1 + 1 (10 koin)

dst...

Cara n : 73 = 25 + 25 + 10 + 10 + 1 + 1 + 1 (7 koin) = solusi optimal

2. Minimasi waktu di dalam sistem penjadwalan

Sebuah server mempunyai n pelanggan yang harus dilayani. Waktu pelayanan untuk setiap pelanggan i adalah ti. Minimumkan total waktu di dalam sistem.

Tiga Pelanggan dengan t1 = 5, t2 = 8, t3 = 2

Enam urutan pelayanan yang mungkin :

-----------------------------------------------------------------

Urutan                                   T

-----------------------------------------------------------------

1, 2, 3:            5 + (5 + 8) + (5 + 8 + 2) = 33

1, 3, 2:            5 + (5 + 2) + (5 + 2 + 8) = 27

2, 1, 3:            8 + (8 + 5) + (8 + 5 + 2) = 36

2, 3, 1:            8 + (8 + 2) + (8 + 2 + 5) = 33

3, 1, 2:            2 + (2 + 5) + (2 + 5 + 8) = 24 (optimal)

3, 2, 1:            2 + (2 + 8) + (2 + 8 + 5) = 27

-----------------------------------------------------------------

Kesimpulan

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