Algoritma Greedy

Dalam tutorial ini, Anda akan mempelajari apa itu Algoritma Greedy. Juga, Anda akan menemukan contoh pendekatan serakah.

Algoritme rakus adalah pendekatan untuk memecahkan masalah dengan memilih opsi terbaik yang tersedia saat ini, tanpa mengkhawatirkan hasil yang akan diperoleh di masa mendatang. Dengan kata lain, pilihan terbaik lokal bertujuan untuk menghasilkan hasil terbaik secara global.

Algoritme ini mungkin bukan pilihan terbaik untuk semua masalah. Mungkin menghasilkan hasil yang salah dalam beberapa kasus.

Algoritma ini tidak pernah kembali untuk membalikkan keputusan yang dibuat. Algoritma ini bekerja dengan pendekatan top-down.

Keuntungan utama dari algoritma ini adalah:

  1. Algoritme lebih mudah dijelaskan .
  2. Algoritme ini dapat bekerja lebih baik daripada algoritme lain (tetapi, tidak di semua kasus).

Solusi yang Layak

Solusi yang layak adalah yang memberikan solusi optimal untuk masalah tersebut.

Algoritma Greedy

  1. Untuk memulainya, set solusi (berisi jawaban) kosong.
  2. Di setiap langkah, item ditambahkan ke set solusi.
  3. Jika set solusi layak, item saat ini disimpan.
  4. Jika tidak, item tersebut ditolak dan tidak pernah dipertimbangkan lagi.

Contoh - Pendekatan Serakah

 Masalah: Anda harus membuat perubahan jumlah menggunakan jumlah koin sekecil mungkin. Jumlah: $ 28 Koin yang tersedia: $ 5 koin $ 2 koin $ 1 koin

Larutan:

  1. Buat solusi-set = () kosong.
  2. koin = (5, 2, 1)
  3. jumlah = 0
  4. Sementara jumlah ≠ 28, lakukan hal berikut.
  5. Pilih koin C dari koin sehingga jumlah + C <28.
  6. Jika C + jumlah> 28, tidak ada solusi yang dikembalikan.
  7. Lain, jumlah = jumlah + C.
  8. Tambahkan C ke kumpulan solusi.

Hingga 5 iterasi pertama, set solusi berisi 5 koin $ 5. Setelah itu, kita mendapatkan 1 koin $ 2 dan terakhir, 1 koin $ 1.

Aplikasi Algoritma Greedy

  • Sortir Pilihan
  • Masalah Knapsack
  • Pohon Rentang Minimum
  • Masalah Jalur Terpendek Sumber Tunggal
  • Masalah Penjadwalan Pekerjaan
  • Algoritma Pohon Rentang Minimal Prim
  • Algoritma Pohon Rentang Minimal Kruskal
  • Algoritma Pohon Rentang Minimal Dijkstra
  • Huffman Coding
  • Algoritma Ford-Fulkerson

Artikel yang menarik...