Masalah Pemenuhan Batasan (Constraint Satisfaction Problems)

Masalah pemenuhan batasan menanyakan penugasan nilai ke sekumpulan variabel yang secara simultan memenuhi semua batasan di antara variabel-variabel tersebut, menyediakan representasi seragam untuk banyak masalah kombinatorial.

Definition

Masalah pemenuhan batasan terdiri dari sekumpulan variabel, domain nilai yang mungkin untuk setiap variabel, dan sekumpulan batasan yang menentukan kombinasi nilai yang diizinkan; solusi adalah penugasan lengkap yang tidak melanggar batasan apa pun.

Scope

Topik ini mencakup formalisme masalah pemenuhan batasan (CSP) (variabel, domain, batasan) dan algoritma yang menyelesaikannya: pencarian backtracking dengan heuristik pengurutan variabel dan nilai, propagasi batasan dan teknik konsistensi (konsistensi node, arc, dan path, seperti algoritma AC-3), serta eksploitasi struktur masalah (CSP berstruktur pohon, cutset conditioning). Ini terhubung dengan pencarian lokal untuk CSP dan praktik pemrograman batasan yang lebih luas. Formulasi pengoptimalan berkelanjutan dan berbasis pembelajaran dari masalah serupa berada di luar cakupan di sini.

Core questions

• Bagaimana beragam masalah (penjadwalan, pewarnaan peta, teka-teki) secara seragam diubah menjadi variabel, domain, dan batasan?
• Bagaimana propagasi batasan memangkas nilai sebelum dan selama pencarian untuk mengurangi backtracking?
• Heuristik pengurutan variabel dan nilai mana yang membuat pencarian backtracking efisien?
• Bagaimana struktur grafik batasan (misalnya, berbentuk pohon) dapat dieksploitasi untuk penyelesaian yang efisien?

Key concepts

• variabel, domain, batasan
• grafik batasan
• pencarian backtracking
• pemeriksaan ke depan (forward checking)
• konsistensi arc dan AC-3
• heuristik nilai sisa minimum (minimum-remaining-values heuristic)
• propagasi batasan
• CSP berstruktur pohon dan cutset conditioning

Key theories

Konsistensi arc dan propagasi batasan

CSP dikatakan konsisten arc ketika setiap nilai dari setiap variabel memiliki pasangan yang konsisten di setiap variabel tetangga; algoritma seperti AC-3 memberlakukan ini dengan berulang kali menghapus nilai yang tidak didukung, seringkali secara drastis memperkecil domain sebelum atau selama pencarian.

Pencarian backtracking dengan heuristik

CSP diselesaikan dengan penugasan depth-first dengan backtracking, yang menjadi praktis dengan heuristik seperti memilih variabel yang paling dibatasi (nilai sisa minimum), nilai yang paling tidak membatasi, dan dengan menyelingi pemeriksaan ke depan atau propagasi untuk mendeteksi jalan buntu lebih awal.

Eksploitasi struktur

Ketika grafik batasan adalah pohon, CSP dapat diselesaikan dalam waktu linier terhadap jumlah variabel, dan struktur yang mendekati pohon dapat direduksi ke kasus ini melalui cutset conditioning atau dekomposisi pohon.

Clinical relevance

Teknik CSP adalah mesin di balik penjadwalan dan penyusunan jadwal, alokasi sumber daya, konfigurasi produk, verifikasi perangkat keras dan perangkat lunak, serta pemecah teka-teki seperti Sudoku; bahasa pemrograman batasan dan pemecah masalah yang dibangun berdasarkan ide-ide ini banyak digunakan dalam perencanaan industri dan riset operasi.

History

Jaringan batasan muncul pada tahun 1970-an dari pekerjaan pelabelan adegan dan konsistensi relasional, dengan makalah Mackworth tahun 1977 yang memformalkan konsistensi node, arc, dan path. Sepanjang tahun 1980-an hingga 1990-an, bidang ini berkembang menjadi pemrograman batasan, dikonsolidasikan dalam Handbook of Constraint Programming tahun 2006, dan tetap menjadi topik AI standar.

Key figures

• Alan K. Mackworth
• Rina Dechter
• Eugene C. Freuder
• Ugo Montanari

Seminal works

• mackworth1977
• dechter2003
• rossi2006

Frequently asked questions

Bagaimana masalah pemenuhan batasan berbeda dari masalah pencarian umum?

Masalah pencarian umum memperlakukan keadaan sebagai kotak hitam, tetapi CSP mengekspos struktur internal suatu keadaan sebagai penugasan ke variabel yang tunduk pada batasan. Struktur ini memungkinkan pemecah CSP menggunakan propagasi batasan dan heuristik pengurutan yang tidak dapat dieksploitasi oleh pencarian generik.

Apa yang dilakukan konsistensi arc?

Konsistensi arc menghapus nilai dari domain variabel yang tidak memiliki nilai yang kompatibel di variabel tetangga, mengingat batasan di antara keduanya. Menerapkannya sebelum dan selama pencarian memangkas ruang pencarian dan terkadang dapat menyelesaikan masalah secara langsung tanpa backtracking.