IF Notes

Backtracking Search untuk CSP

4 min read

Back to IF3170 Inteligensi Artifisial

Topic

Questions/Cues

  • Apa itu Backtracking Search?

  • Bagaimana cara kerjanya?

  • Apa saja pertanyaan kunci untuk efisiensi?

  • Apa itu Variable Ordering?

  • Apa itu heuristik MRV?

  • Apa itu Degree Heuristic?

  • Apa itu Value Ordering?

  • Apa itu heuristik LCV?

Reference Points

  • IF3170_Materi04_AI-CSP.pdf (Slide 13-20)

Backtracking Search adalah algoritma dasar uninformed untuk menyelesaikan CSP. Algoritma ini pada dasarnya adalah Depth-First Search (DFS) yang dimodifikasi untuk CSP.

Beberapa properti pentingnya:

  • Satu Variabel per Langkah: Di setiap level pohon pencarian, kita hanya mempertimbangkan assignment untuk satu variabel tunggal.

  • Komutatif: Urutan pemberian nilai tidak penting untuk hasil akhir (misal, WA=merah, NT=hijau sama saja dengan NT=hijau, WA=merah). Ini memungkinkan kita hanya mempertimbangkan satu variabel pada satu waktu.

  • Solusi di Kedalaman n: Untuk CSP dengan n variabel, solusi ditemukan pada kedalaman n di pohon pencarian.

Cara kerjanya adalah dengan mencoba memberikan nilai pada satu variabel, lalu secara rekursif melanjutkan ke variabel berikutnya. Jika ditemukan sebuah nilai yang melanggar constraint, maka algoritma akan “mundur” (backtrack) ke langkah sebelumnya dan mencoba nilai lain.

Meningkatkan Efisiensi Backtracking

Algoritma backtracking standar bisa sangat lambat. Efisiensinya dapat ditingkatkan secara drastis dengan menjawab tiga pertanyaan kunci (tanpa memerlukan pengetahuan spesifik domain):

  1. Variabel mana yang harus dipilih selanjutnya? (Variable Ordering)

  2. Dalam urutan apa nilai-nilainya harus dicoba? (Value Ordering)

  3. Bisakah kita mendeteksi kegagalan lebih awal? (Inference, akan dibahas di catatan berikutnya).

1. Variable Ordering: Gagal Lebih Cepat

Tujuannya adalah memilih variabel yang paling mungkin menyebabkan kegagalan, sehingga kita bisa memangkas cabang pencarian sedini mungkin.

  • Minimum Remaining Values (MRV) Heuristic:

    • Pilih variabel yang memiliki jumlah nilai legal (valid) paling sedikit di domainnya. Heuristik ini juga dikenal sebagai “most constrained variable”.

    • Contoh: Setelah WA=merah dan NT=hijau, domain untuk SA tinggal {biru} (1 nilai) sementara domain Q adalah {merah, biru} (2 nilai). Maka, kita harus memilih SA selanjutnya.

  • Degree Heuristic:

    • Digunakan sebagai pemecah seri (tie-breaker) jika ada beberapa variabel dengan MRV yang sama. Pilih variabel yang memiliki jumlah constraint paling banyak dengan variabel lain yang belum diberi nilai.

    • Heuristik ini mencoba mengurangi domain variabel lain secepat mungkin.

    • Contoh: Pada awal pewarnaan peta, SA adalah pilihan terbaik karena berbatasan dengan 5 wilayah lain.

2. Value Ordering: Sukses Lebih Cepat

Berbeda dengan variable ordering, tujuan di sini adalah memilih nilai yang paling mungkin membawa kita ke solusi.

  • Least Constraining Value (LCV) Heuristic:

    Pilih nilai yang paling sedikit menghilangkan pilihan untuk variabel-variabel tetangga yang belum diberi nilai.

    • Contoh: Setelah WA=merah dan NT=hijau, kita perlu memilih warna untuk Q.

      • Jika Q=biru, maka domain SA menjadi {} (kosong). Ini sangat membatasi.

      • Jika Q=merah, maka domain SA menjadi {biru}. Ini menyisakan satu pilihan.

    • Maka, kita harus memilih Q=merah terlebih dahulu.

Summary

Backtracking Search adalah algoritma fundamental berbasis DFS untuk menyelesaikan CSP dengan mencoba nilai secara rekursif dan mundur saat terjadi konflik. Performanya yang naif dapat ditingkatkan secara dramatis menggunakan heuristik cerdas. Heuristik Variable Ordering (MRV, Degree) bertujuan untuk “gagal lebih cepat” dengan memilih variabel yang paling terbatas, sementara heuristik Value Ordering (LCV) bertujuan untuk “sukses lebih cepat” dengan memilih nilai yang paling tidak membatasi sisa masalah.

Graph View

Backlinks