My first Magazine pemrograman-kompetitif-dasar | Page 49

4.3 Optimisasi Teknik Brute Force
Sebagai contoh, kita kembali ke permasalahan Subset Sum . Untuk setiap elemen, terdapat
dua kemungkinan, yaitu memilih bilangan tersebut untuk dimasukkan ke subhimpunan atau tidak.
Selanjutnya, kita akan menelusuri semua kemungkinan pilihan yang ada. Jika terdapat pemilihan
yang jumlahan elemen-elemennya sama dengan K, maka terdapat solusi. Hal ini dapat dengan
mudah diimplementasikan secara rekursif.
Selanjutnya, mari kita analisis performa strategi brute force untuk permasalahan Subset
Sum . Untuk setiap elemen, terdapat 2 pilihan, yaitu dipilih atau tidak. Karena terdapat N elemen,
maka terdapat 2 N kemungkinan. Maka, kompleksitas solusi brute force adalah O(2 N ). Untuk
nilai N terbesar, 2 N = 2 15 = 32.768, yang masih cukup dalam operasi komputer per detik pada
umumnya (100 juta).
Algoritma untuk menyelesaikan permasalahan Subset Sum dapat ditemukan pada Algoritma
16 serta Algoritma 17.
Algoritma 16 Solusi permasalahan Subset Sum .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
function SOLVE (i, sum)
if i > N then
if sum = K then
return true
else
return f alse
end if
end if
option1 ← SOLVE (i + 1, sum + a i )
option2 ← SOLVE (i + 1, sum)
return option1 ∨ option2
end function
. Pilih elemen a i
. Tidak pilih elemen a i
Algoritma 17 Fungsi pemanggil solusi.
function SOLVE S UBSET S UM ()
return SOLVE (1, 0)
3: end function
1:
2:
4.3
Optimisasi Teknik Brute Force
Bisakah solusi pada Algoritma 16 dibuat menjadi lebih cepat? Perhatikan kasus ketika sum
telah melebihi K. Karena semua a i bernilai positif, maka sum tidak akan mengecil. Karena itu, bila
sum sudah melebihi K, dipastikan tidak akan tercapai sebuah solusi.
Dari sini, kita bisa mengoptimisasi fungsi SOLVE menjadi fungsi OPTIMIZED S OLVE yang
akan menghentikan suatu penelusuran kemungkinan apabila jumlahan elemen yang dipilih sudah
melebihi K. Algoritma penyelesaian Subset Sum dengan optimasi tersebut dapat dilihat di
Algoritma 18.
39