algoritma back tracking

7/27/2019 Algoritma Back Tracking

1/22


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


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


4/22

Prinsip kerja


4


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


5


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)


6


7/22

Contoh kasus

N-Queen

0/1 knapsack Hamiltonian Circuit

Subset-Sum

m-coloring


7


8/22

N-Queen

bagaimana meletakkan N buah queen pada

papan catur sehingga tidak ada queen yangdalam posisi saling menyerang


8


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


9


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


10


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)


11


12/22

N-Queen


12

{ }

{1 } {2 }

{1, 3}

{1, 4}

{1, 4, 2 }

{2, 4}

{2, 4, 1 }

{2, 4, 1, 3}


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


13


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


14


15/22

0/1 Knapsack


15

{ }

{0 } {1 }

{0, 0}

{0, 1}

{0, 1, 0 }

{1, 1}

{1, 1, 0 }

{1, 1, 0, 1}


16/22

hamiltonian circuit

diberikan sebuah graf dengan N simpul.

tentukan hamiltonian circuit pada graf tersebut


16

a

d

b

e

c f


17/22

hamiltonian circuit


17

a

b

c

d

e

f

e

d f

f

e

c

d

a


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


18


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


19

a

d

b

e

c f


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


20

( ) ji xxjiedgeji ),(,


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


21


22/22

Latihan

bangkitkan permutasi bilangan (1,2,...N)

sedemikian rupa sehingga tidak ada bilanganyang berada pada urutan yg sama denganbilangan tersebut


22

algoritma back tracking

Documents