Algoritma Greedy

ALGORITMA GREEDY

Algoritma adalah langkah dalam mencari solusi atas sebuah masalah. banyak sekali algoritma yang dapat kita gunakan dalam membangun sebuah program , salah satunya adalah algoritma greedy.

Algoritma greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada setiap langkahnya. Nilai maksimum sementara ini dikenal dengan istilah local maximum. 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. Greedy sendiri diambil dari bahasa inggris yang artinya rakus, tamak atau serakah .Prinsip algoritma greedy adalah: “take what you can get now!”.

Algoritma greedy membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.

Persoalan optimasi (optimization problems): persoalan yang menuntut pencarian solusi optimum. Persoalan optimasi ada dua macam: Maksimasi (maximization) dan Minimasi (minimization)

Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.

Elemen persoalan optimasi: kendala (constraints) dan fungsi objektif (atau fungsi optiamsi).

Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi optimum.

Studi kasus Algoritma Greedy

Mari kita lihat sebuah masalah klasik yang sering dijumpai dalam kehidupan sehari-hari: mencari jarak terpendek dari peta. Misalkan kita ingin bergerak dari titik A ke titik B, dan kita telah menemukan beberapa jalur dari peta:

Jalur dari Titik A ke B

Dari peta yang ditampilkan di atas, dapat dilihat bahwa terdapat beberapa jalur dari titik A ke titik B. Sistem peta pada gambar secara otomatis telah memilih jalur terpendek (berwarna biru). Kita akan mencoba mencari jalur terpendek juga, dengan menggunakan algoritma greedy.

Langkah pertama yang harus kita lakukan tentunya adalah memilih struktur data yang tepat untuk digunakan dalam merepresentasikan peta. Jika dilihat kembali, sebuah peta seperti pada gambar di atas pada dasarnya hanya menunjukkan titik-titik yang saling berhubungan, dengan jarak tertentu pada masing-masing titik tersebut. Misalnya, peta di atas dapat direpresentasikan dengan titik-titik penghubung seperti berikut:

Graph Sederhana dari Titik A ke B

Dari gambar di atas, kita dapat melihat bagaimana sebuah peta jalur perjalanan dapat direpresentasikan dengan menggunakan graph, spesifiknya Directed Graph (graph berarah). Maka dari itu, untuk menyelesaikan permasalahan jarak terpendek ini kita akan menggunakan struktur data graph untuk merepresentasikan peta. Berikut adalah graph yang akan digunakan:

Graph Berarah dari Titik A ke B

Untuk mencari jarak terpendek dari A ke B, sebuah algoritma greedy akan menjalankan langkah-langkah seperti 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 mengapliikasikan langkah-langkah di atas pada graph A ke B sebelumnya maka kita akan mendapatkan pergerakan seperti berikut:

1. Mulai dari titik awal (A). Ambil seluruh titik yang dapat dikunjungi.

Langkah Pertama Greedy

           2.      Local maximum adalah ke C, karena jarak ke C adalah yang paling dekat.

           3.      Tandai A sebagai titik yang telah dikunjungi, dan pindah ke C.

     4.       Ambil seluruh titik yang dapat dikunjungi dari C.

Langkah Kedua Greedy

         5.      Local maximum adaah ke D, dengan jarak 6.

         6.      Tandai C sebagai titik yang telah dikunjungi, dan pindah ke D.

Langkah Ketiga Greedy

     

    7.   (Langkah selanjutnya diserahkan kepada pembaca sebagai latihan).

 Dengan menggunakan algoritma greedy pada graph di atas, hasil akhir yang akan didapatkan sebagai jarak terpendek adalah A-C-D-E-F-B. Hasi jarak terpendek yang didapatkan ini tidak tepat dengan jarak terpendek yang sebenarnya (A-G-E-F-B). Algoritma greedy memang tidak selamanya memberikan solusi yang optimal, dikarenakan pencarian local maximum pada setiap langkahnya, tanpa memperhatikan solusi secara keseluruhan.

Contoh Algoritma Pseudocode Greedy
Berikut adalah salah satu contoh dari algoritma greedy : 

Sumber Referensi :

https://www.it-jurnal.com/pengertian-algoritma-greedy/

https://bertzzie.com/knowledge/analisis-algoritma/Greedy.html
http://kurniadi-addi.blogspot.co.id/2015/07/materi-analisis-algortima-algoritma.html