Algoritma Greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi. Persoalan optimasi (optimization problems) yaitu persoalan yang menuntut pencarian solusi optimum. Persoalan optimasi hanya ada dua macam: Maksimasi (maximization) dan Minimasi (minimization)
Algoritma Greedy adalah sebuah metode algoritma yang mengambil keputusan berdasarkan pada informasi yang tersedia saat ini tanpa mempertimbangkan dampak keputusan tersebut pada langkah-langkah selanjutnya. Pada setiap langkah, algoritma greedy akan memilih langkah terbaik yang tersedia pada saat itu, dengan harapan bahwa dengan memilih langkah terbaik secara lokal pada setiap langkah akan menghasilkan solusi optimal secara keseluruhan.
Karakteristik utama dari algoritma greedy adalah keputusan yang diambil pada setiap langkah hanya didasarkan pada informasi yang tersedia pada saat itu, tanpa mempertimbangkan gambaran keseluruhan masalah. Ini membuat algoritma ini relatif sederhana dan cepat, tetapi tidak selalu menghasilkan solusi optimal untuk semua masalah. Oleh karena itu, algoritma greedy cocok untuk masalah yang memenuhi kriteria greedy-choice property, yaitu bahwa pemilihan langkah terbaik pada setiap langkah akan mengarah ke solusi optimal secara keseluruhan.
Contoh algoritma greedy
Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin. Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimalkan fungsi optimasi disebut solusi optimum.
Greedy = rakus, tamak, loba
Algoritma Greedy adalah algoritma yang memecahkan masalah langkah per langkah pada setiap langkah:
mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)
berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global
Contoh persoalan optimasi: ( Masalah Penukaran Uang): Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut? Contoh 1: tersedia banyak koin 1, 5, 10, 25 Uang senilai A = 32 dapat ditukar dengan banyak cara berikut: 32 = 1 + 1 + … + 1 (32 koin) 32 = 5 + 5 + 5 + 5 + 10 + 1 + 1 (7 koin) 32 = 10 + 10 + 10 + 1 + 1 (5 koin) … dst Minimum: 32 = 25 + 5 + 1 + 1 (4 koin)
Skema Umum Algoritma Greedy
Algoritma greedy disusun oleh elemen-elemen berikut: • Himpunan kandidat. Berisi elemen-elemen pembentuk solusi. • Himpunan solusi Berisi kandidat-kandidat yang terpilih sebagai solusi persoalan. • Fungsi seleksi (selection function) Memilih kandidat yang paling memungkinkan mencapai solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.
• Fungsi kelayakan (feasible) Memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala (constraints) yang ada. Kandidat yang layak dimasukkan ke dalam himpunan solusi, sedangkan kandidat yang tidak layak dibuang dan tidak pernah dipertimbangkan lagi.
• Fungsi obyektif, yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain).
Pada masalah penukaran uang: • Himpunan kandidat: himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai. • Himpunan solusi: total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang yang ditukarkan. • Fungsi seleksi: pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa. • Fungsi layak: memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar. • Fungsi obyektif: jumlah koin yang digunakan minimum
Contoh kasus algoritma greedy : Misalkan tersedia koin : 1, 3, 5. Uang senilai X=8 dapat di tukar dengan cara : 1+1+1+1+1+1+1+1 = 8 (8 koin) 1+1+1+1+1+3=8 (6 koin) 1+1+1+5=8 (4 koin) 1+1+3+3=8 (4 koin) 3+5=8 (2 koin) solusi optimal. Maka solusi optimal dari kasus penukaran koin di atas adalah 2 koin.
Knapsack Problem Knapsack problem adalah suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang di mana setiap barang tersebut mempunyai berat dan profit masing masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum. Contoh kasus knapsack w1 = 10; p1 = 2 w2 = 5; p2 = 3 w3 = 15; p3 = 5 w4 = 7; p4 = 7 w5 = 6; p5 = 1 w6 = 18; p6 = 4 w7 = 3; p7 = 1 M = 15
Perhitungan kompleksitas waktu
Kompleksitas waktu algoritma = O(n). T(n) = O(n) Disebut algoritma linear, dimana waktu eksekusinya sebanding dengan jumlah data, dan merupakan kondisi optimal dalam membuat algoritma. Contoh Program Pascal : Begin For I := 1 to n do Begin A:=A+1; End; End. Maka T(n) = O(n) karena program dieksekusi sejumlah n kali. Jadi Pengaruh jumlah data pada lama operasi Karena Kompleksitas waktu algoritma = O(n). Jadi jumlah data yang dimasukan akan mempengaruhi lama operasi program tesebut. Karena O(n) berarti program dieksekusi sejumlah n kali.
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 seperti sistem real-time atau game.
