Matakuliah : T0034 / Perancangan & Analisis Algoritma

Tahun : 2008

Pertemuan 22

BACKTRACKING

Bina Nusantara

SEARCH TREE

• Untuk beberapa kasus algoritma, dalam setiap langkah terdapat beberapa pilihan dan algoritma harus memutuskan untuk memilih salah satunya.

• Keputusan yang dibuat akan mempengaruhi pilihan berikutnya, di mana algoritma harus membuat keputusan lagi, demikian seterusnya hingga solusi akhir dicapai.

• Teknik pencarian solusi seperti ini dapat digambarkan sebagai sebuah Search Tree– Hubungan antara sebuah parent node dengan anak-anaknya

adalah pilihan yang harus diputuskan dalam menyelesaikan sebuah masalah.

– Solusi yang benar ada di salah satu node tree, tapi kita belum tahu yang mana. Algoritma yang dibuat bertujuan untuk mencari node yang merupakan solusi tersebut.

[buku utama, bab 9.1]

Bina Nusantara

N-QUEEN PROBLEM

• Misalkan kita memiliki sebuah papan catur berukuran N x N. Papan catur ini harus diisi dengan N buah Queen sedemikian rupa sehingga keempat Queen tersebut tidak saling mengancam.

1 2 3 4 5 6 7 8

1

2

3

4

5 Q1

6

7

8

Bina Nusantara

MODELING N-QUEEN PROBLEM

• Bagaimana penyelesaian N-Queen Problem dapat digambarkan dengan sebuah Search Tree?– N buah Queen harus diletakkan, berarti terdapat N

keputusan– Setiap baris papan catur hanya mungkin diisi oleh 1

Queen– Berarti setiap keputusan akan meletakkan sebuah

Queen di baris ke-N– Yang harus diputuskan adalah : di kolom ke berapa

Queen harus diletakkan

Bina Nusantara

N-QUEEN SEARCH TREE

[buku utama, ilustrasi 9.4]

Bina Nusantara

COMPLETE vs PARTIAL SEARCH TREE

• Complete Search Tree bisa berukuran sangat besar– Kompleksitas algoritma tinggi– Diperlukan waktu cukup lama– Memerlukan memori penyimpanan yang besar

• Sering kali dalam sebuah Search Tree, tidak semua node perlu ditelusuri– Node-node yang jelas tidak memenuhi syarat dapat langsung

diabaikan– Node-node yang memiliki kemungkinan lebih tinggi menuju solusi

dapat dibuka terlebih dahulu– Kendala (constraint) sebuah problem dijadikan patokan untuk

meneusuri sebuah node atau tidak

Bina Nusantara

BACKTRACKING

• Backtracking adalah teknik untuk mencari solusi dengan Partial Search Tree– Search Tree tidak sekaligus dibentuk secara utuh melainkan satu per satu.– Pada setiap keputusan, algoritma akan menghitung apakah ”jalur tertentu”

dalam tree memungkinkan terjadinya sebuah solusi atau tidak.• Jika memungkinkan, proses akan diteruskan.• Jika tidak memungkinkan, algoritma akan membatalkan jalur keputusan yang

sudah dibuat, maka lakukan langkah mundur (backtrack) dan mencari jalur yang lain.

• Contoh populer penerapan teknik dasar algoritma Backtracking adalah N-Queen Problem– Sebagai contoh, akan digunakan nilai N=4 (4-Queen Problem)

[buku utama, bab 9.3]

Bina Nusantara

LANGKAH BACKTRACKING

1. Bangun node awal sebagai active node (E-node)

2. Dengan E-node, jalani node berikut dengan metode Depth First Search

3. Periksa constraint, jika constraint dipenuhi maka nyatakan node tersebut sebagai active node (E-node)

4. Jika contraint tidak dipenuhi, nyatakan node tersebut sebagai dead node (D-node)

5. Jika yang didapat D-node, backtrack ke E-node di atasnya, kemudian jalani cabang lain

6. dan seterusnya hingga didapat solusi yang diinginkan

Bina Nusantara

SEARCH TREE WITH BACKTRACKING

[buku utama, ilustrasi 9.17]

Bina Nusantara

HASIL 4-QUEEN PROBLEM

Q1

Q2

Q3

Q4

• Akhirnya didapat node P sebagai solusi. Node P ini mewakili pilihan Q1 (1,2), Q2 (2,4), Q3 (3,1) dan Q4 (4,3).

[buku utama, ilustrasi 9.17]

Bina Nusantara

LATIHAN

• Lakukan pencarian solusi 5-Queen Problem dengan menggunakan teknik Bactracking !

Bina Nusantara

REVIEW

• Apa yang sudah dipahami?• Apa yang akan dibahas selanjutnya?