Download - Algoritma Back Tracking
-
7/27/2019 Algoritma Back Tracking
1/22
-
7/27/2019 Algoritma Back Tracking
2/22
Intro
Brute-force seringkali menjadi satu-satunya
solusi yang dapat diharapkan untuk berbagaimasalah
pada masalah kombinatorial, backtracking
(runut-balik) membantu menentukan ruangpencarian secara sistematis
ruang pencarian disusun berupa tree, danumumnya ditelusuri menggunakan DFS
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
2
-
7/27/2019 Algoritma Back Tracking
3/22
Prinsip kerja
solusi dinyatakan dalam bentuk n-tuple
tentukan constraint/pembatas ruang solusi fungsi pembangkit pohon solusi, menambah
satu elemen setiap saatnya
evaluasi solusi secara sistematis
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
3
-
7/27/2019 Algoritma Back Tracking
4/22
Prinsip kerja
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
4
-
7/27/2019 Algoritma Back Tracking
5/22
algoritma iterasi
Backtrack
hitung S1 = kandidat solusi untuk elemen 1
k = 1
while(k>0) do
while( Sk ) do
ak = elemen Sk
Sk = Sk ak
if( A = (a1, a2, ...ak) adalah solusi, lapor
elsek = k+1
hitung Sk = kandidat solusi untuk elemen k
k = k 1 //backtrack
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
5
-
7/27/2019 Algoritma Back Tracking
6/22
algoritma rekursi
Backtrack(k)
if( A = (a1, a2, ...ak) adalah solusi, lapor
elsek = k+1
hitung Sk = kandidat solusi untuk elemen k
while( Sk
) do
ak = elemen Sk
Sk = Sk ak
Backtrack(k)
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
6
-
7/27/2019 Algoritma Back Tracking
7/22
Contoh kasus
N-Queen
0/1 knapsack Hamiltonian Circuit
Subset-Sum
m-coloring
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
7
-
7/27/2019 Algoritma Back Tracking
8/22
N-Queen
bagaimana meletakkan N buah queen pada
papan catur sehingga tidak ada queen yangdalam posisi saling menyerang
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
8
-
7/27/2019 Algoritma Back Tracking
9/22
N-Queen
Solusi:
dengan brute force: mencoba seluruh kombinasi yangada: memilih NxN kemungkinan posisi untuk N queen= C(NxN, N) = C(64, 8) = 4.426.165.368
dengan brute force: mencoba kombinasi posisi 1queen pada setiap barisnya = NN kemungkinan = 88 =16.777.216
dengan brute force: mencoba kombinasi posisi 1queen pada setiap barisnya yang tidak berada padakolom yang sama: N! = 40.320
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
9
-
7/27/2019 Algoritma Back Tracking
10/22
N-Queen
Solusi backtracking:
menggunakan permutasi sebagai dasarpembangkitan pohon solusi
mulai dari baris pertama, evaluasi kemungkinan
posisi queen, maju ke baris berikutnya untuk setiapkonfigurasi yang mungkin
jika tidak ada konfigurasi lain yang mungkin dan tidak
ada solusi, backtrack ke baris sebelumnya
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
10
-
7/27/2019 Algoritma Back Tracking
11/22
N-Queen
NQueen(k)
if k == N
// solusi ditemukanelse
while(ada pos Queen pada brs k yang belum dievaluasi)
pilih posisi baru Queen pada baris k
NQueen(k+1)
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
11
-
7/27/2019 Algoritma Back Tracking
12/22
N-Queen
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
12
{ }
{1 } {2 }
{1, 3}
{1, 4}
{1, 4, 2 }
{2, 4}
{2, 4, 1 }
{2, 4, 1, 3}
-
7/27/2019 Algoritma Back Tracking
13/22
0/1 Knapsack
N buah barang memiliki bobot yang berbeda-
beda (w1, w2, ... wn), dan nilai (v1, v2,...vn)dimasukkan ke dalam karung dengan kapasitasmaksimum W.
tentukan barang mana saja yang dimasukkanagar mencapai nilai maksimum
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
13
-
7/27/2019 Algoritma Back Tracking
14/22
0/1 knapsack
ruang solusi: ( x1, x2, ... xn ), xi {0, 1 }
batasan: temukan solusi yang mungkin
pilih solusi dengan nilai terbesar
=
k
iii Wxw
1
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
14
-
7/27/2019 Algoritma Back Tracking
15/22
0/1 Knapsack
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
15
{ }
{0 } {1 }
{0, 0}
{0, 1}
{0, 1, 0 }
{1, 1}
{1, 1, 0 }
{1, 1, 0, 1}
-
7/27/2019 Algoritma Back Tracking
16/22
hamiltonian circuit
diberikan sebuah graf dengan N simpul.
tentukan hamiltonian circuit pada graf tersebut
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
16
a
d
b
e
c f
-
7/27/2019 Algoritma Back Tracking
17/22
hamiltonian circuit
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
17
a
b
c
d
e
f
e
d f
f
e
c
d
a
-
7/27/2019 Algoritma Back Tracking
18/22
subset sum
diberikan sekumpulan bilangan S = {s1, s2, ...
sn}, tentukan subset dari S yang memiliki jumlahd
ruang solusi: ( x1, x2, ... xn ), xi {0, 1 }
batasan:
pilih solusi yang memiliki hasil d=
k
i
ii dxs1
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
18
-
7/27/2019 Algoritma Back Tracking
19/22
m-coloring
diberikan sebuah graf dengan N simpul. Berilah
warna pada setiap simpul dengan warna yangdiambil dari m buah warna, dengan syarat tidakada simpul yang bersebelahan memiliki warna
yang sama
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
19
a
d
b
e
c f
-
7/27/2019 Algoritma Back Tracking
20/22
m-coloring
ruang solusi: ( x1, x2, ... xn ), xi {c1, c2,...cm }
batasan: mulai dari simpul 1, evaluasi kemungkinan warna
simpul, maju ke simpul berikutnya untuk setiap
konfigurasi yang mungkin jika tidak ada konfigurasi lain yang mungkin dan tidak
ada solusi, backtrack ke simpul sebelumnya
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
20
( ) ji xxjiedgeji ),(,
-
7/27/2019 Algoritma Back Tracking
21/22
Penutup
secara umum, algoritma backtracking sesuai
untuk masalah yang mencari solusi yangdinyatakan berupa n-tuple
penelusuran tree dilakukan secara DFS
worse-case scenario: algoritma harusmenelusuri seluruh elemen tree tanpabacktracking
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
21
-
7/27/2019 Algoritma Back Tracking
22/22
Latihan
bangkitkan permutasi bilangan (1,2,...N)
sedemikian rupa sehingga tidak ada bilanganyang berada pada urutan yg sama denganbilangan tersebut
3-J un-07 IF-ITB/AI/Apr 07TOKI II Backtracking
22