DAA - Metode Serakah
Di antara semua pendekatan algoritmik, pendekatan yang paling sederhana dan langsung adalah metode Greedy. Dalam pendekatan ini, keputusan diambil atas dasar informasi yang tersedia saat ini tanpa mengkhawatirkan pengaruh keputusan saat ini di masa depan.
Algoritma serakah membangun solusi bagian demi bagian, memilih bagian selanjutnya sedemikian rupa, sehingga memberikan manfaat langsung. Pendekatan ini tidak pernah mempertimbangkan kembali pilihan yang diambil sebelumnya. Pendekatan ini terutama digunakan untuk memecahkan masalah pengoptimalan. Metode serakah mudah diterapkan dan cukup efisien dalam banyak kasus. Oleh karena itu, dapat dikatakan bahwa algoritma Greedy merupakan paradigma algoritmik berbasis heuristik yang mengikuti pilihan optimal lokal pada setiap langkah dengan harapan menemukan solusi optimal global.
Dalam banyak masalah, hal tersebut tidak menghasilkan solusi yang optimal meskipun memberikan solusi yang mendekati (mendekati optimal) dalam waktu yang wajar.
Komponen Algoritma Greedy
Algoritme serakah memiliki lima komponen berikut -
A candidate set - Solusi dibuat dari set ini.
A selection function - Digunakan untuk memilih kandidat terbaik untuk ditambahkan ke solusi.
A feasibility function - Digunakan untuk menentukan apakah seorang kandidat dapat digunakan untuk berkontribusi pada solusi.
An objective function - Digunakan untuk memberikan nilai pada solusi atau solusi parsial.
A solution function - Digunakan untuk menunjukkan apakah solusi lengkap telah tercapai.
Area Aplikasi
Pendekatan serakah digunakan untuk menyelesaikan banyak masalah, seperti
Menemukan jalur terpendek antara dua simpul menggunakan algoritma Dijkstra.
Menemukan pohon rentang minimal dalam grafik menggunakan algoritme Prim / Kruskal, dll.
Dimana Pendekatan Serakah Gagal
Dalam banyak masalah, algoritma Greedy gagal menemukan solusi yang optimal, apalagi menghasilkan solusi yang paling buruk. Masalah seperti Travelling Salesman dan Knapsack tidak dapat diselesaikan dengan menggunakan pendekatan ini.