Interleaving Search dan Reference

Back to IF3170 Inteligensi Artifisial

Topic

Questions/Cues

• Apa itu Interleaving?

• Mengapa ini penting?

• Apa itu Forward Checking?

• Bagaimana cara kerjanya?

• Apa itu Maintaining Arc Consistency (MAC)?

• Apa perbedaan FC dan MAC?

Reference Points

• IF3170_Materi04_AI-CSP.pdf (Slide 21-24)

Konsep Dasar Interleaving Search and Inference

Daripada melakukan inference hanya sekali di awal, kita bisa menggabungkannya dengan proses pencarian backtracking. Setiap kali kita memberikan sebuah nilai ke sebuah variabel, kita langsung melakukan inference untuk melihat dampaknya pada variabel-variabel lain.

Tujuan Utama: Mendeteksi kegagalan (failure) sedini mungkin untuk memangkas cabang pencarian yang tidak akan pernah menuju solusi.

1. Forward Checking (FC)

Ini adalah salah satu cara paling sederhana untuk menggabungkan inference dengan pencarian.

Cara Kerja:

1. Ketika sebuah variabel X diberi nilai v, algoritma akan melihat setiap variabel Y yang belum diberi nilai dan terhubung dengan X oleh sebuah constraint.

2. Untuk setiap Y tersebut, semua nilai di domain Y yang tidak konsisten dengan X=v akan dihapus.

3. Jika proses ini menyebabkan domain salah satu variabel Y menjadi kosong, maka assignment X=v langsung dianggap gagal, dan algoritma akan backtrack saat itu juga, tanpa perlu mencoba variabel lain.

Contoh:

• WA diberi warna merah.

• Forward Checking akan menghapus merah dari domain tetangganya, yaitu NT dan SA.

• Proses ini terus berlanjut setiap kali sebuah variabel diberi nilai.

2. Maintaining Arc Consistency (MAC)

MAC adalah strategi yang lebih kuat dan lebih proaktif daripada Forward Checking.

Cara Kerja:

1. Sama seperti FC, ketika variabel X diberi nilai v, proses dimulai.

2. Namun, alih-alih hanya memeriksa tetangga X, algoritma MAC akan menjalankan algoritma arc consistency penuh (seperti AC-3) untuk seluruh CSP.

3. Ini berarti efek dari sebuah assignment akan dirambatkan (propagated) ke seluruh jaringan. Jika penghapusan nilai dari domain Y (tetangga X) menyebabkan nilai lain harus dihapus dari domain Z (tetangga Y), MAC akan mendeteksinya, bahkan jika Z bukan tetangga langsung dari X.

Contoh Ilustrasi:

• Dalam gambar di slide 23, setelah beberapa assignment, MAC bisa menyimpulkan bahwa NT dan SA tidak bisa sama-sama biru. Kesimpulan ini mungkin tidak bisa didapat oleh Forward Checking biasa pada tahap yang sama. Jika proses ini menyebabkan domain manapun kosong, algoritma langsung backtrack.

Summary

Interleaving search and inference adalah strategi untuk mendeteksi kegagalan lebih awal dengan menjalankan inference setiap kali sebuah nilai ditetapkan selama pencarian. Forward Checking (FC) melakukan ini dengan memeriksa dan menyaring domain dari tetangga langsung variabel yang baru ditetapkan. Sementara itu, Maintaining Arc Consistency (MAC) mengambil langkah lebih jauh dengan menjalankan algoritma arc consistency penuh untuk merambatkan (propagate) constraint ke seluruh masalah, membuatnya lebih kuat dalam mendeteksi ketidakkonsistenan.

Additional Information

FC vs. MAC: Mana yang Lebih Baik?

• Forward Checking: Lebih ringan secara komputasi pada setiap langkahnya. Ia hanya memeriksa “satu lapis” keluar dari variabel yang baru di-assign.

• Maintaining Arc Consistency: Jauh lebih mahal pada setiap langkah karena bisa jadi ia memeriksa banyak sekali arcs di seluruh graf.

Namun, biaya tambahan MAC seringkali terbayarkan. Dengan mendeteksi lebih banyak kegagalan lebih awal, MAC dapat memangkas cabang-cabang pohon pencarian yang jauh lebih besar. Untuk banyak masalah sulit, pengurangan drastis dalam jumlah backtrack membuat MAC secara keseluruhan lebih cepat daripada Forward Checking, meskipun setiap langkahnya lebih lambat.

Kapan Inference Diaktifkan?

Dalam implementasi pseudocode backtracking (dari catatan sebelumnya), langkah inference (baik FC maupun MAC) akan ditambahkan setelah sebuah nilai di-assign ke variabel, dan sebelum pemanggilan rekursif BACKTRACK. Jika inference mengembalikan kegagalan (misalnya, domain kosong), maka pemanggilan rekursif tersebut dilewati dan algoritma langsung mencoba nilai berikutnya.