Struktur Data - Algoritma Greedy

Algoritme dirancang untuk mencapai solusi optimal untuk masalah tertentu. Dalam pendekatan algoritma serakah, keputusan dibuat dari domain solusi yang diberikan. Karena tamak, solusi terdekat yang tampaknya memberikan solusi optimal dipilih.

Algoritme serakah mencoba menemukan solusi optimal yang dilokalkan, yang pada akhirnya dapat menghasilkan solusi yang dioptimalkan secara global. Namun, umumnya algoritme serakah tidak memberikan solusi yang dioptimalkan secara global.

Menghitung Koin

Masalah ini adalah menghitung ke nilai yang diinginkan dengan memilih koin sesedikit mungkin dan pendekatan serakah memaksa algoritme untuk memilih koin terbesar yang mungkin. Jika kita diberi koin sebesar ₹ 1, 2, 5 dan 10 dan kita diminta untuk menghitung ₹ 18 maka prosedur serakah adalah -

• 1 - Pilih satu koin ₹ 10, sisa hitungannya adalah 8

• 2 - Kemudian pilih satu koin ₹ 5, sisa hitungannya adalah 3

• 3 - Lalu pilih satu koin ₹ 2, sisa hitungannya 1

• 4 - Dan akhirnya, pemilihan satu koin ₹ 1 menyelesaikan masalah

Meskipun, tampaknya berfungsi dengan baik, untuk hitungan ini kita hanya perlu memilih 4 koin. Tetapi jika kita sedikit mengubah masalah maka pendekatan yang sama mungkin tidak dapat memberikan hasil optimal yang sama.

Untuk sistem mata uang, di mana kita memiliki koin dengan nilai 1, 7, 10, menghitung koin untuk nilai 18 akan benar-benar optimal tetapi untuk hitungan seperti 15, mungkin menggunakan lebih banyak koin daripada yang diperlukan. Misalnya, pendekatan serakah akan menggunakan 10 + 1 + 1 + 1 + 1 + 1, total 6 koin. Sedangkan masalah yang sama dapat diselesaikan dengan hanya menggunakan 3 koin (7 + 7 + 1)

Oleh karena itu, kami dapat menyimpulkan bahwa pendekatan serakah memilih solusi yang segera dioptimalkan dan mungkin gagal jika pengoptimalan global menjadi perhatian utama.

Contoh

Sebagian besar algoritme jaringan menggunakan pendekatan serakah. Berikut ini daftar beberapa di antaranya -

• Masalah Penjual Bepergian
• Algoritma Pohon Rentang Minimal Prim
• Algoritma Pohon Rentang Minimal Kruskal
• Algoritma Pohon Rentang Minimal Dijkstra
• Grafik - Mewarnai Peta
• Grafik - Penutup Vertex
• Masalah Knapsack
• Masalah Penjadwalan Pekerjaan

Ada banyak masalah serupa yang menggunakan pendekatan serakah untuk menemukan solusi optimal.