Pengertian Algoritma Greedy
Pengertian Algoritma Greedy adalah jenis algoritma yang membentuk solusi langkah per langkah 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.
Prinsip Utama Algoritma Greedy
Prinsip utama algoritma greedy adalah “take what you can get now!”. Maksud dari prinsip tersebut adalah sebagai berikut: Pada setiap langkah dalam algoritma greedy, kita ambil keputusan yang paling optimal untuk langkah tersebut tanpa memperhatikan konsekuensi pada langkah selanjutnya. Sebagai contoh, jika kita manggunakan algoritma Greedy untuk menempatkan komponen diatas papan sirkuit, sekali komponen telah diletakkan dan dipasang maka tidak dapat dipindahkan lagi. Kita namakan solusi tersebut dengan optimum lokal. Kemudian saat pengambilan nilai optimum lokal pada setiap langkah, diharapkan tercapai optimum global, yaitu tercapainya solusi optimum yang melibatkan keseluruhan langkah dari awal sampai akhir.
Skema umum Algoritma Greedy
Algoritma greedy disusun oleh elemen, dan elemen-elemen yang digunakan dalam penerapan algoritma greedy antara lain :
- Himpunan Kandidat
Himpunan yang berisi elemen pembentuk solusi.
- Himpunan Solusi
Himpunan yang terpilih sebagai solusi persoalan.
- Fungsi Seleksi
Fungsi yang memilih kandidat yang paling mungkin untuk mencapai solusi optimal.
- Fungsi Kelayakan
Fungsi yang memeriksa apakah suatu kandidat yang dipilih dapat memberikan solusi yang layak. Maksudnya yaitu apakah kandidat tersebut bersama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala yang ada.
- Fungsi Solusi
Fungsi yang mengembalikan nilai boolean. True jika himpunan solusi yang sudah tebentuk merupakan solusi yang lengkap; False jika himpunan solusi belum lengkap.
- Fungsi Objektif
Fungsi yang mengoptimalkan solusi.
Di dalam mencari sebuah solusi (optimasi) algoritma greedy hanya memakai 2 buah macam persoalan Optimasi,yaitu:
- Maksimasi (maxizimation)
- Minimasi (minimization)
