Daftar Isi:
Definisi - Apa yang dimaksud dengan Greedy Algorithm?
Algoritma serakah adalah strategi algoritmik yang membuat pilihan optimal terbaik pada setiap tahap kecil dengan tujuan ini pada akhirnya mengarah ke solusi optimal global. Ini berarti bahwa algoritma memilih solusi terbaik saat ini tanpa memperhatikan konsekuensi. Ini memilih output langsung terbaik, tetapi tidak mempertimbangkan gambaran besar, karenanya dianggap serakah.
Techopedia menjelaskan Algoritma Greedy
Algoritma serakah bekerja dengan memilih jawaban terbaik di setiap langkah dan kemudian beralih ke langkah berikutnya hingga mencapai akhir, tanpa memperhatikan solusi keseluruhan. Ia hanya berharap bahwa jalan yang diambilnya adalah yang optimal secara global, tetapi seperti terbukti berkali-kali, metode ini tidak sering menghasilkan solusi yang optimal secara global. Bahkan, sangat mungkin bahwa solusi jangka pendek yang paling optimal mengarah pada hasil global yang paling buruk.
Anggap saja mengambil banyak jalan pintas dalam bisnis manufaktur: dalam jangka pendek jumlah besar dihemat dalam biaya produksi, tetapi ini pada akhirnya menyebabkan kejatuhan karena kualitas dikompromikan, menghasilkan pengembalian produk dan penjualan rendah ketika pelanggan berkenalan dengan pelanggan. Produk "murah". Tapi ini tidak selalu terjadi, ada banyak aplikasi di mana algoritma serakah bekerja paling baik untuk menemukan atau memperkirakan solusi optimal secara global seperti dalam membangun pohon Huffman atau pohon pembelajaran keputusan.
Misalnya: Ambil jalur dengan jumlah keseluruhan terbesar. Algoritma serakah akan mengambil jalur biru, sebagai hasil dari rabun jauh, bukan jalur oranye, yang menghasilkan jumlah terbesar.
Komponen:
- Satu set kandidat data yang membutuhkan solusi
- Fungsi pemilihan yang memilih kontributor terbaik untuk solusi akhir
- Fungsi kelayakan yang membantu fungsi seleksi dengan menentukan apakah seorang kandidat dapat menjadi kontributor untuk solusi
- Fungsi obyektif yang memberikan nilai pada solusi parsial
- Fungsi solusi yang menunjukkan bahwa solusi optimal telah ditemukan
