Kendala kepuasan atau Constraint Satisfaction

Dalam kecerdasan buatan dan riset operasi , kepuasan kendala adalah proses menemukan solusi untuk satu set kendala yang memaksakan kondisi bahwa variabel harus memuaskan . Solusi Oleh karena itu vektor dari variabel yang memenuhi semua kendala.

Teknik yang digunakan dalam kepuasan kendala tergantung pada jenis kendala yang dipertimbangkan. Sering digunakan adalah kendala pada domain yang terbatas, ke titik yang kendala masalah kepuasan biasanya diidentifikasi dengan masalah berdasarkan kendala pada domain yang terbatas. Masalah seperti ini biasanya dipecahkan melalui pencarian , khususnya bentuk kemunduran ataupencarian lokal . propagasi Kendala metode lain digunakan pada masalah tersebut, kebanyakan dari mereka tidak lengkap pada umumnya, yaitu, mereka dapat memecahkan masalah atau membuktikannya unsatisfiable, namun tidak selalu. Kendala metode propagasi juga digunakan dalam hubungannya dengan pencarian untuk membuat soal yang diberikan sederhana untuk memecahkan. Jenis lain dianggap kendala berada pada bilangan real atau rasional; pemecahan masalah pada kendala-kendala dilakukan melalui eliminasi variabel atau algoritma simpleks .

Kendala kepuasan berasal dari bidang kecerdasan buatan pada tahun 1970 (lihat misalnya ( Laurière 1978 )). Selama 1980-an dan 1990-an, embedding kendala menjadi bahasa pemrograman yang dikembangkan. Bahasa sering digunakan untuk pemrograman kendala adalah Prolog dan C + + .

Sebagai awalnya didefinisikan dalam kecerdasan buatan, kendala menghitung nilai yang mungkin satu set variabel dapat mengambil. Informal, domain terbatas adalah himpunan berhingga elemen sewenang-wenang. Sebuah kepuasan kendala masalah pada domain seperti berisi satu set variabel yang nilainya hanya dapat diambil dari domain, dan satu set kendala, kendala masing-masing menetapkan nilai diperbolehkan untuk sekelompok variabel. Sebuah solusi untuk masalah ini adalah evaluasi dari variabel-variabel yang memenuhi semua kendala. Dengan kata lain, solusi adalah cara untuk menetapkan nilai untuk setiap variabel sedemikian rupa sehingga semua kendala dipenuhi oleh nilai-nilai ini.

Dalam praktek, kendala yang sering diekspresikan dalam bentuk yang kompak, daripada enumerasi semua nilai dari variabel yang akan memuaskan kendala. Salah satu kendala yang paling sering digunakan adalah salah satu menetapkan bahwa nilai-nilai dari variabel-variabel yang terkena harus semua berbeda.

Masalah yang dapat dinyatakan sebagai masalah kepuasan kendala adalah teka-teki ratu Delapan , yang Sudoku pemecahan masalah, yang masalah satisfiability Boolean , penjadwalan masalah dan berbagai masalah pada grafik seperti grafik mewarnai masalah.

Meskipun biasanya tidak termasuk dalam definisi di atas dari masalah kepuasan kendala, aritmatika persamaan dan ketidaksetaraan terikat nilai-nilai dari variabel yang dikandungnya dan karenanya dapat dianggap sebagai bentuk kendala. Domain mereka adalah himpunan nomor (baik bilangan bulat, rasional, atau nyata), yang tak terbatas: oleh karena itu, hubungan ini kendala mungkin tak terbatas serta, misalnya, X = Y + 1 memiliki jumlah tak terbatas pasang memuaskan nilai-nilai. Aritmatika persamaan dan ketidaksamaan sering tidak dianggap dalam definisi "masalah kepuasan kendala", yang terbatas pada domain yang terbatas. Namun mereka sering digunakan dalam pemrograman kendala .

Masalah kepuasan kendala pada domain yang terbatas biasanya dipecahkan dengan menggunakan bentuk pencarian . Teknik yang paling digunakan adalah varian dari kemunduran , propagasi kendala , dan pencarian lokal . Teknik ini digunakan pada masalah dengan nonlinier kendala.

Variabel eliminasi dan algoritma simpleks digunakan untuk memecahkan linier dan polinomial persamaan dan kesenjangan, dan masalah yang mengandung variabel dengan domain yang tak terbatas.Ini biasanya dipecahkan sebagai optimasi masalah di mana fungsi dioptimalkan adalah jumlah kendala dilanggar.

Memecahkan masalah kendala kepuasan pada domain terbatas adalah NP lengkap masalah. Penelitian telah menunjukkan sejumlah penurut sub kasus, beberapa membatasi hubungan kendala diperbolehkan, beberapa membutuhkan lingkup kendala untuk membentuk pohon, mungkin dalam versi dirumuskan dari masalah. Penelitian juga membentuk hubungan dari masalah kepuasan kendala dengan masalah di daerah lain seperti teori model terbatas .


Kendala pemrograman adalah penggunaan kendala sebagai bahasa pemrograman untuk mengkodekan dan memecahkan masalah. Hal ini sering dilakukan oleh embedding kendala menjadi bahasa pemrograman , yang disebut host language. Pemrograman kendala berasal dari formalisasi kesetaraan istilah dalam Prolog II , yang mengarah ke kerangka umum untuk embedding kendala menjadilogika pemrograman bahasa. Bahasa host yang paling umum adalah Prolog , C + + , dan Java , namun bahasa lainnya telah digunakan juga.

Sebuah program logika kendala adalah logika program yang berisi kendala dalam tubuh klausa. Sebagai contoh, klausa A(X):-X>0,B(X) adalah klausa yang mengandung kendala X>0 dalam tubuh.Kendala juga dapat hadir dalam tujuan. Kendala dalam tujuan dan dalam klausa digunakan untuk membuktikan tujuan diakumulasikan ke dalam satu set disebut toko kendala . Set ini berisi kendala penafsir telah diasumsikan satisfiable dalam rangka untuk melanjutkan dalam evaluasi tersebut. Akibatnya, jika set ini terdeteksi unsatisfiable, yang backtracks penerjemah. Persamaan istilah, seperti yang digunakan dalam pemrograman logika, yang dianggap sebagai bentuk khusus dari kendala yang dapat disederhanakan dengan menggunakan unifikasi . Akibatnya, toko kendala dapat dianggap sebagai perpanjangan dari konsep substitusi yang digunakan dalam pemrograman logika biasa. Jenis yang paling umum digunakan dalam pemrograman kendala kendala kendala logika lebih dari bilangan bulat / bilangan rasional / nyata dan kendala atas domain yang terbatas.

Kendala logika pemrograman konkuren bahasa juga telah dikembangkan. Mereka secara signifikan berbeda dari non-logika pemrograman konkuren kendala dalam bahwa mereka ditujukan untuk pemrograman proses konkuren yang tidak dapat mengakhiri. Kendala aturan penanganan dapat dilihat sebagai bentuk kendala logika pemrograman konkuren, tetapi juga kadang-kadang digunakan dalam kendala non-bersamaan logika bahasa pemrograman. Mereka memungkinkan untuk menulis ulang kendala atau untuk menyimpulkan yang baru berdasarkan kebenaran kondisi.

Kendala kepuasan toolkit perangkat lunak perpustakaan untuk bahasa pemrograman imperatif yang digunakan untuk mengkodekan dan memecahkan masalah kepuasan kendala.

• Pemecah kendala Kasuari adalah sebuah open source proyek untuk kepuasan kendala (dapat diakses dari C, Java, Python dan bahasa lainnya).
• Komet , sebuah bahasa pemrograman komersial dan toolkit
• Gecode , sebuah toolkit open source portabel yang ditulis dalam C + + dikembangkan sebagai pelaksanaan produksi berkualitas dan sangat efisien dari latar belakang teoritis lengkap.
• JaCoP (pemecah) open source Java kendala pemecah
• Koalog solver berbasis Java kendala komersial.
• logilab-kendala kendala open source pemecah ditulis dengan Python murni dengan algoritma propagasi kendala.
• Minion kendala open source solver ditulis dalam C + +, dengan bahasa kecil untuk tujuan menetapkan model / masalah.
• ZDC adalah sebuah program open source yang dikembangkan dalam Proyek Computer-Aided Kepuasan Kendala untuk pemodelan dan memecahkan masalah kendala kepuasan.

Kendala toolkit adalah cara untuk embedding kendala menjadi bahasa pemrograman imperatif . Namun, mereka hanya digunakan sebagai perpustakaan eksternal untuk encoding dan memecahkan masalah. Suatu pendekatan di mana kendala yang diintegrasikan ke dalam bahasa pemrograman imperatif diambil dalam bahasa pemrograman Kaleidoscope .

Kendala juga telah tertanam ke dalam bahasa pemrograman fungsional .