Algoritma greedy merupakan metode yang paling populer untuk memecahkanpersoalan optimasi. Greedy sendiri diambil dari bahasa inggrisyang artinya rakus, tamak atau serakah .Prinsip algoritma greedy adalah: “take what you can get now!”.
Algoritma greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencarinilai maksimum sementara pada setiap langkahnya. Nilaimaksimum sementara ini dikenal dengan istilah local maximum.Pada kebanyakan kasus, algoritma greedy tidak akanmenghasilkan solusi paling optimal, begitupun algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.
Contoh masalah sehari-hari yang menggunakan prinsipgreedy:
– Memilih beberapa jenis investasi (penanaman modal)
– Mencari jalur tersingkat dari Bandung ke Surabaya
– Memilih jurusan di Perguruan Tinggi
– Bermain kartu remi
Algoritma greedy membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu dieksplorasi padasetiap langkah solusi. Oleh karena itu, pada setiap langkah harusdibuat keputusan yang terbaik dalam menentukan pilihan.Keputusan yang telah diambil pada suatu langkah tidak dapatdiubah lagi pada langkah selanjutnya.
Kesimpulan
Algoritma greedy merupakan algoritma yang besifat heuristik, mencari nilai maksimal sementara dengan harapan akanmendapatkan solusi yang cukup baik. Meskipun tidak selalumendapatkan 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 sistemreal-time atau game.
Dari impementasi yang kita lakukan, dapat dilihat bagaimanaalgoritma greedy memiliki beberapa fungsionalitas dasar, yaitu:
1. Fungsi untuk melakukan penelusuran masalah.
2. Fungsi untuk memilih local maximum dari pilihan-pilihanyang ada tiap langkahnya.
3. Fungsi untuk mengisikan nilai local maximum ke solusikeseluruhan.
4. Fungsi yang menentukan apakah solusi telah didapatkan.
Tentunya fungsi-fungsi di atas juga dapat digabungkan ataudipecah lebih lanjut lagi, menyesuaikan dengan strategi greedy yang dikembangkan.
Resource:
No comments:
Post a Comment