Senin, 08 Juni 2015

Algoritma Greedy


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 untuk memecahkan persoalan.

#Contoh persoalan optimasi:
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 banyak koin 1, 5, 10, 25
Uang  senilai 32 dapat ditukar dengan banyak cara berikut:
32 = 1 + 1 + … + 1                     (32 koin)
32 = 5 + 5 + 5 + 5 + 10 + 1 + 1   (7 koin)
32 = 10 + 10 + 10 + 1 + 1           (5 koin)
… dst          
Minimum: 32 = 25 + 5 + 1 + 1    (4 koin)

#Algoritma Greedy contoh kasus 2
Anggota koin = 12,7,5,1 dapat ditukar dengan uang senilai 30 (target goal)
Maka
[1]. Urutkan tiap anggota mulai besar – terkecil
12;10;5;1
[2] Jumlah tiap anggota dengan tiap anggota
Pastikan jumlah kumulatif tiap anggota tidak lebih dari target








Pada anggota ke 2, mengapa anggota 2 yaitu 10 bernilai 0?
Anggota 1 = [12+12] = 24
Anggota 2 =  24 + [10] = 34 (TIDAK BISA karena 34 > 30) sehingga
Anggota 2 = TIDAK BISA diikutkan
Anggota 3 = 24 + [5+5] =  34 (tidak bisa karena seperti diatas!) sehingga
Anggota 3 = 24 + [5] = 29
Anggota 4 = 29 + [1]
Jadi
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
PADAHAL KITA BISA lebih ringkas yaitu 3 koin untuk 10, apa yang terjadi?? Lihat dibawah ini
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. 
Contoh 3: tinjau masalah penukaran uang.
Koin: 5, 4, 3, dan 1. Berapa uang yang ditukar 7 ?
Solusi greedy:  7 = 5 + 1 + 1       ( 3 koin) ? tidak optimal
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
Tapi penulis mempunyai pendapat lain! Bahwa 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!
Anggota koin = 5;4;3;1 dengan target 7

 


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
#Kasus4
Koin: 10, 7, 1
Uang yang ditukar: 15
Solusi greedy:  15 = 10 + 1 + 1 + 1 + 1 + 1     (6 koin)
Solusi optimal: 15 = 7 + 7 + 1                       (hanya 3 koin)
 



#kasus5

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




Ternyata Algoritma Greedy AKAN TETAP OPTIMAL dengan teknik diatas! Sehingga GREEDY akan tetap LAYAK menjadi penghuni “dunia” TEKNIK OPTIMASI



Berikut adalah kasus 2 yang diatas, ternyata greedy bisa dioptimasikan lagi dengan teknik iterasi per anggota

 

Download
https://www.dropbox.com/s/wv1wjqlyztqcu37/release%20aplikasi%20greedy%20-%20minimisasi%20dengan%20java.rar?dl=0

Posting Komentar