Monday, February 10, 2020

Buku Belajar Machine Learning dengan Java - Penerapan Algoritma Greedy


Seiring dengan meningkatnya traffic dan kemudahan dalam mengelola content, kami mengucapkan banyak terima kasih kepada para pembaca setia pada blog www.softscients.web.id

Per 19 Maret 2020, kami sedang melakukan migrasi ke domain dan hosting yang lebih baik yaitu
Semoga dengan alamat domain dan hosting terbaru akan semakin memudahkan para pembaca dalam mencari materi/content. Migrasi dilakukan secara bertahap yang membutuhkan waktu yang cukup lama jadi jangan kuatir selama migrasi akan dilakukan secara hati-hati untuk memimalkan broken link




Sinopsis

Dunia teknik optimasi mempunyai banyak jurus ampuh untuk menangani masalah optimasi minimisasi / maksimisasi. Salah satu nya yaitu algoritma greedy (RAKUS) yang merupakan metode yang paling populer. Contoh persoalan optimasi yaitu Masalah Penukaran Uang: Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?


Contoh 1

Tersedia pecahan koin dengan nilai 1, 5, 10, 25; Maka uang senilai 32 dapat ditukar dengan banyak cara berikut:
jawab:
32 = 1 + 1 + … + 1 (32 koin)
32 = 5 + 5 + 5 + 5 + 10 + 1 + 1 (7 koin)
32 = 10 + 10 + 10 + 1 + 1 (5 koin)
Dari beberapa cara diatas didapakan Minimum: 32 = 25 + 5 + 1 + 1 (4 koin)

Contoh 2

Kita coba menggunakan algoritma Greedy untuk memecahkan persoalan minimum. Tersedia pecahan uang koin dengan nilai 12,10,5,1.  Berapa jumlah koin (minimal) yang dibutuhkan untuk  ditukar dengan uang senilai 30?
Jawab:
Algoritma Greedy melalui langkah-langkah berikut ini
[1]. Urutkan tiap anggota mulai besar – terkecil: 12;10;5;1
[2] Jumlah tiap anggota secara kumulatif, pastikan jumlah kumulatif tiap anggota tidak lebih dari target seperti berikut bila menggunakan tabel.





Pada anggota ke 2, mengapa anggota 2 yaitu 10 bernilai 0?
  1. Anggota 1 = [12+12] = 24
  2. Anggota 2 = 24 + [10] = 34 (TIDAK BISA karena 34 > 30) sehingga Anggota 2 = TIDAK BISA diikutkan
  3. Anggota 3 = 24 + [5+5] = 34 (TIDAK BISA karena 34 > 30) sehingga Anggota 3 = 24 + [5] = 29
  4. Anggota 4 = 29 + [1]

Sehingga bisa disimpulkan menjadi
Ada 2 koin untuk 12 = 24
Ada 1 koin untuk 5 =5
Ada 1 koin unuk 1=1
Total 24+5+1 = 30
Maka jumlah koin ada 4

Dengan kata lain: algoritma greedy melibatkan pencarian sebuah himpunan bagian, S, dari himpunan kandidat, C; yang dalam hal ini, S harus memenuhi beberapa kriteria yang ditentukan, yaitu menyatakan suatu solusi dan S dioptimisasi oleh fungsi obyektif.

Tapi ada catatan tersendiri lho untuk kasus diatas:  akan lebih ringkas menggunakan 3 koin bila digunakan pecahan 10 saja

Contoh 3

Tersedia pecahan koin  5, 4, 3, dan 1. Berapa jumlah koin yang dibutukan untuk ditukar dengan nilai 7 ?
jawab
  1. Solusi greedy: 7 = 5 + 1 + 1 ( 3 koin) ? tidak optimal
  2. Solusi optimal: 7 = 4 + 3 ( 2 koin)

Jika jawaban terbaik mutlak TIDAK diperlukan, maka algoritma greedy sering berguna untuk menghasilkan solusi hampiran (approximation), daripada menggunakan algoritma yang lebih rumit untuk menghasilkan solusi yang eksak. Bila algoritma greedy optimum, maka keoptimalannya itu dapat dibuktikan secara matematis.

Optimasi Algoritma Greedy

Algoritma Greedy sejatinya dapat dioptimalkan! Yaitu dengan cara mengurangi satu demi satu anggota koin, dan melakukan teknik Greedy, lihat kondisi berikut untuk setiap anggota koin yang di remove satu persatu!

Contoh soal: Tersedia  nilai koin 5;4;3;1 dengan target untuk ditukar nilai 7
Jawab
Perhatikan tabel dibawah ini, dengan cara membandingkan tiap ulangan, maka akan didapatkan solusi optimal.
 




Maka dapat dibandingkan antara tiap ulangan untuk mencari nilai terkecil. Penulis menggunakan java untuk mempermudah algoritma diatas karena terlalu banyak iterasi sehingga perlu dibuat dengan bahasa pemrograman daripada dihitung menggunakan excel 
 





Berikut adalah contoh kasus lainnya

Contoh 4

Nominal Koin yang tersedia: 10, 7, 1. Uang yang ditukar: 15
Jawab
  1. Solusi greedy: 15 = 10 + 1 + 1 + 1 + 1 + 1 (6 koin)
  2. Solusi optimal: 15 = 7 + 7 + 1 (hanya 3 koin)


 





Contoh 5

Nominal Koin yang tersedia: 15, 10, dan 1. Uang yang ditukar: 20
Jawab
  1. Solusi greedy: 20 = 15 + 1 + 1 + 1 + 1 + 1 (6 koin)
  2. Solusi optimal: 20 = 10 + 10 (2 koin) 






Ternyata Algoritma Greedy AKAN TETAP OPTIMAL dengan teknik diatas!  Berikut adalah Contoh 2 yang diatas, ternyata greedy bisa dioptimasikan lagi dengan teknik iterasi per anggota

 

Kalian bisa mendapatkan source code nya dengan cara subcribe dan follow blog ini

No comments:

Post a Comment