· Runut-balik (backtracking)
adalah algoritma yang berbasis pada DFS untuk mencari solusi persoalan secara
lebih mangkus.
· Runut-balik, yang merupakan perbaikan dari algoritma brute-force, secara sistematis mencari
solusi persoalan di antara semua kemungkinan solusi yang ada.
· Dengan metode runut-balik, kita tidak perlu memeriksa
semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja
yang selalu dipertimbangkan. Akibatnya, waktu pencarian dapat dihemat.
· Runut-balik merupakan bentuk tipikal dari algoritma rekursif.
· Saat ini algoritma runut-balik banyak diterapkan untuk
program games (seperti permainan tic-tac-toe, menemukan jalan keluar
dalam sebuah labirin, catur, dll) dan masalah-masalah pada bidang kecerdasan buatan (artificial intelligence).
Properti Umum Metode Runut-balik
1. Solusi persoalan.
Solusi dinyatakan sebagai vektor dengan n-tuple:
X = (x1,
x2, …, xn), xi
Î himpunan berhingga Si .
Mungkin saja S1
= S2 = … = Sn.
Contoh: Si
= {0, 1},
xi
= 0 atau 1
2. Fungsi pembangkit nilai xk
Dinyatakan sebagai:
T(k)
T(k)
membangkitkan nilai untuk xk,
yang merupakan komponen vektor solusi.
3. Fungsi pembatas (pada beberapa persoalan fungsi ini
dinamakan fungsi kriteria)
Dinyatakan sebagai
B(x1, x2, …, xk)
Fungsi pembatas menentukan apakah (x1, x2, …, xk) mengarah ke solusi. Jika ya, maka
pembangkitan nilai untuk xk+1
dilanjutkan, tetapi jika tidak, maka (x1,
x2, …, xk) dibuang dan tidak
dipertimbangkan lagi dalam pencarian solusi.
Pengorganisasian Solusi
· Semua kemungkinan solusi dari persoalan disebut ruang solusi (solution space).
· Jika xi
Î Si, maka S1 ´ S2
´ … ´ Sn
disebut ruang solusi.
· Jumlah anggota di dalam ruang solusi adalah | S1| × | S2|
× … × | Sn
|.
· Tinjau persoalan Knapsack
0/1 untuk n = 3. Solusi persoalan
dinyatakan sebagai vektor (x1,
x2, x3) dengan xi
Î {0,1}. Ruang solusinya adalah
{0,1} ´ {0,1} ´ {0,1} = {(0, 0, 0), (0, 1, 0),
(0, 0, 1),
(1,
0, 0), (1, 1, 0), (1, 0, 1),
(0, 1, 1), (1, 1, 1)}.
· Pada persoalan Knapsack
0/1 dengan n = 3 terdapat 2n = 23 = 8
kemungkinan solusi, yaitu:
(0,
0, 0), (0, 1, 0), (0, 0, 1),
(1, 0, 0), (1, 1, 0), (1, 0, 1),
(0, 1, 1), dan (1, 1, 1).
· Penyelesaian secara exhaustive search adalah dengan menguji setiap kemungkinan solusi.
· Ruang solusi diorganisasikan ke dalam struktur pohon.
· Tiap simpul pohon menyatakan status (state) persoalan, sedangkan sisi
(cabang) dilabeli dengan nilai-nilai xi.
· Lintasan dari akar ke daun menyatakan solusi yang
mungkin.
· Seluruh lintasan dari akar ke daun membentuk ruang
solusi. Pengorganisasian pohon ruang solusi diacu sebagai pohon ruang status (state space tree).
· Tinjau kembali persoalan Knapsack 1/0 untuk n = 3.
Ruang solusinya
Gambar 7.1 Ruang solusi
untuk persoalan Knapsack 0/1 dengan n = 3
Prinsip
Pencarian Solusi dengan Metode Runut-balik
1. Solusi dicari dengan membentuk lintasan dari akar ke
daun. Aturan pembentukan yang dipakai adalah mengikuti aturan pencarian
mendalam (DFS). Simpul-simpul yang sudah dilahirkan dinamakan simpul hidup (live node). Simpul hidup yang sedang
diperluas dinamakan simpul-E (Expand-node).
2. Tiap kali simpul-E diperluas, lintasan yang dibangun
olehnya bertambah panjang. Jika lintasan yang sedang dibentuk tidak mengarah ke
solusi, maka simpul-E tersebut “dibunuh” sehingga menjadi simpul mati (dead node).
Fungsi yang digunakan untuk membunuh simpul-E adalah dengan menerapkan fungsi pembatas (bounding function). Simpul yang sudah mati tidak akan pernah
diperluas lagi.
3. Jika pembentukan lintasan berakhir dengan simpul mati,
maka proses pencarian diteruskan dengan
membangkitkan simpul anak yang lainnya. Bila tidak ada lagi simpul anak yang
dapat dibangkitkan, maka pencarian solusi dilanjutkan dengan melakukan
runut-balik ke simpul hidup terdekat (simpul orangtua). Selanjutnya simpul ini
menjadi simpul-E yang baru.
4. Pencarian dihentikan bila kita telah menemukan solusi
atau tidak ada lagi simpul hidup untuk runut-balik.
Tinjau
persoalan Knapsack 0/1 dengan
instansiasi:
n = 3
(w1,
w2, w3) = (35, 32, 25)
(p1,
p2, p3) = (40, 25, 50)
M
= 30
Solusi
dinyatakan sebagai X = (x1, x2, x3),
xi Î {0, 1}.
Fungsi
pembatas:
(a)
|
(b)
|
Gambar 7.2 (a) Pohon dinamis yang dibentuk selama pencarian
untuk persoalan Knapsack 0/1 dengan n = 3,
w = (35, 32, 25) dan p = (40, 25, 50)
(b) Penomoran ulang simpul-simpul sesuai urutan
pembangkitannya
Solusi optimumnya adalah X = (0, 0, 1) dan F = 50.
Skema Umum Algoritma Runut-Balik
(a) Versi rekursif
|
procedure
RunutBalikR(input k:integer)
{Mencari semua solusi persoalan dengan metode runut-balik;
skema rekursif
Masukan: k, yaitu
indeks komponen vektor solusi, x[k]
Keluaran: solusi x
= (x[1], x[2], …, x[n])
}
Algoritma:
for tiap x[k] yang belum dicoba
sedemikian sehingga
( x[k]¬T(k))
and B(x[1], x[2], ... ,x[k])= true do
if
(x[1], x[2], ... ,x[k]) adalah lintasan dari akar ke daun
then
CetakSolusi(x)
endif
RunutBalikR(k+1) {
tentukan nilai untuk x[k+1]}
endfor
|
Pemanggilan
prosedur pertama kali: RunutBalikR(1)
(b) Versi iteratif
|
procedure
RunutBalikI(input n:integer)
{Mencari semua solusi persoalan dengan metode runut-balik;
skema iteratif.
Masukan: n, yaitu
panjang vektor solusi
Keluaran: solusi x
= (x[1], x[2], …, x[n])
}
Delarasi:
k : integer
Algoritma:
k¬1
while k > 0 do
if (x[k] belum dicoba sedemikian
sehingga x[k]¬T(k))
and
(B(x[1], x[2], ... ,x[k])= true)
then
if (x[1],x[2],...,x[k])
adalah lintasan dari akar ke daun
then
CetakSolusi(x)
endif
k¬k+1 {indeks
anggota tupple berikutnya}
else {x[1], x[2], …, x[k] tidak
mengarah ke simpul solusi }
k¬k-1
{runut-balik
ke anggota tupple sebelumnya}
endif
endwhile
{ k =
0 }
|
Pemanggilan
prosedur pertama kali: RunutBalikI(n)
· Setiap simpul dalam pohon ruang status berasosiasi
dengan sebuah pemanggilan rekursif.
· Jika jumlah simpul dalam pohon ruang status adalah 2n atau n!, maka untuk kasus terburuk, algoritma runut-balik membutuhkan
waktu dalam O(p(n)2n) atau O(q(n)n!), dengan p(n) dan q(n)
adalah polinom derajat n yang
menyatakan waktu komputasi setiap simpul.
2 komentar:
kita juga punya nih jurnal mengenai Algoritma Backtracking silahkan dikunjungi dan dibaca , berikut linknya
http://repository.gunadarma.ac.id/bitstream/123456789/2747/1/21-PENYELESAIAN%20MASALAH%20N-QUEEN%20DENGAN%20TEKNIK%20BACKTRACKING.pdf
terimakasih atas responnya...nanti akan saya kunjungi dan saya minta izin untuk saya share di blog ini/
Posting Komentar