·
Pertama
kali diperkenalkan oleh DH Lehmer
(1950), dirumuskan dalam suatu algortima oleh RJ Walker (1960), aplikasinya dikembangkan oleh Golomb dan Baumert.
·
Dasar
dari teknik Backtracking adalah searching.
·
Backtracking
merupakan salah satu algotritma yang didasarkan pada pencarian ruang solusi.
·
Pencarian
ruang solusi dalam algoritma backtracking menggunakan teknik pencarian Depth First Search (DFS).
·
Masalah-masalah
yang dapat diselesaikan dengan menggunakan algoritma Backtracking adalah :
Ø The 8-Queen Problem
Ø The 4-Queen Problem
Ø Sum of Subsets
Ø Graph Coloring
Ø Hamilton Cycles
Ø Knapsack Problem
Ø The Travelling Salesman Problem
Penyelesaian Sum of Subsets dengan
Menggunakan Algoritma Backtracking
Masalah
utama dari SUM of SUBSETS adalah jika terdapat n bilangan real dan ingin dihitung
semua kombinasi yang mungkin dari himpunan bilangan tersebut. Kombinasi yang
didinginkan adalahkombinasi yang jumlah seluruh elemen-elemennya sama dengan M
(tertentu).
Algoritma Sum of Subset
procedure
sumofsub(s,k,r)
global
integer M,n
global real
w(1:n)
real
r,s
integer k,j
x(k) = 1
if s + w(k)
= M then
print(x(j),j ß 1 to k)
else
if s + w(k) + w(k+1) ≤ M
then
call
sumofsub(s+w(k), k+1, r-w(k))
endif
endif
if s +
r-w(k) ≥ M and s + w(k+1) ≤ M then
x(k) ß 0
call sumofsub(s, k+1, r-w(k))
endif
end
sumofsub
Permasalahan :
Suatu
himpunan terdiri dari 6 bilangan yaitu {5, 10, 12, 13, 15, 18} yang disusun
secara tidak turun. Akan ditentukan himpunan-himpunan bagiannya yang jumlah
seluruh elemennya adalah 30
Penyelesaian :
n=6
W(1:6) =
{5,10,12,13,15,18}
M = 30
Diasumsikan bahwa w(1) ≤ M dan ∑ w(i) ≥ M
Dalam hal
ini w(1)= 5 ≤ 30 dan ∑ w(i) = 73 ≥ 30,
|
|
|
|
Diperoleh himpunan
penyelesaian :
A = {1,1,0,0,1} =
5+10+15=30
B = {1,0,1,1} =
5+12+13 = 30
C = {0,0,1,0,0} =
12+18 = 30
1 komentar:
terimakasih atas responnya...nanti akan saya kunjungi dan saya minta izin untuk saya share di blog ini/
Posting Komentar