csp

CSP adalah suatu permasalahan seseorang harusmencari nilai untuk set variabel (finite) yang memenuhiset constraint (finite) [6, 7]. CSP terdiri dari komponenkomponenberikut:_ Variabel, yang merupakan penampung dapat diisi berbagainilai._ Constraint yang merupakan suatu aturan yang ditentukanuntuk mengatur nilai boleh diisikan ke variabel,atau kombinasi variabel._ Domain yang merupakan kumpulan nilai legal dapatdiisi ke variabel._ Solusi yang merupakan assignment nilai-nilai daridomain ke setiap variabel tidak ada constraint yangdilanggar.CSP dimulai dari solusi kosong dan diakhiri dengan sebuahsolusi yang memenuhi semua constraint (consistent).Pencarian solusi dilakukan dengan mencoba mengisi nilaidomain pada setiap variabel satu demi satu tanpa melanggarconstraint, sampai solusi ditemukan.

Backtracking :

Algoritma yang paling banyak dipakai untuk melakukanpencarian sistematik untuk menyelesaikan CSP adalah backtracking.Algoritma backtracking search (penelusuran kembali)adalah suatu bentuk algoritma depth-first-search. Backtrackingdapat dilihat sebagaimana searching dalam tree,karena setiap node mewakili state dan turunan dari setiapnode mewakili ekstensi dari state tersebut.Pada metode backtracking, variabel diisi secara sequentialselagi semua variabel relevan dengan constraint yangsudah diinisialisasi. Jika solusi partial melanggar constraint,backtracking melakukan langkah kembali ke solusi partialsebelumnya dan memilih nilai lain yang belum dicoba untukvariabel yang ingin diisikan. Langkah tersebut bergunauntuk menghindari eksplorasi lebih lanjut dari solusi partialyang salah. Keuntungan backtracking adalah pemeriksaanconsistency hanya perlu dilakukan terhadap assignmentyang terakhir dilakukan karena pemeriksaan terhadapassignment yang sebelumnya sudah dilakukan sebelumnya.Pada algoritma backtracking, teknik look ahead digunakanuntuk meramalkan efek pemilihan variabel branchinguntuk mengevaluasi nilai-nilai variabel tersebut. Forwardchecking adalah salah satu cara untuk melakukan lookahead. Forward checking mencegah terjadinya konflik denganmelarang nilai-nilai yang belum diisikan ke variabeluntuk dipakai. Ketika suatu nilai diisikan ke suatu variabel,nilai yang berada di domain dari variabel yang konflik denganassignment tersebut akan dihilangkan dari domain.Minimum Remaining Value (MRV) adalah suatu teknikyang dikembangkan untuk menangani masalah kemungkinanbesar gagal pada pencarian menggunakan CSP.MRV berkerja dengan memilih variabel yang memiliki domainlegal dan paling sedikit (memiliki kemungkinan untukmembuat suatu dead-end paling besar) untuk diisikan

terlebih dulu.

Penelusuran dengan Backtracking (BT).Algoritma backtracking menggunakan Constructivemethods, yang berarti mengembangkan solusi partialsedikit demi sedikit dengan tetap menjaga consistency,sehingga mencapai consistent complete assignment.2. Forward Checking (FC).Forward checking berkerja dengan membuat suatutabel yang menyatakan nilai domain yang masih tersediauntuk setiap variabel. Kemudian pada tabel inidihilangkan domain yang sudah tidak boleh diambillagi.3. Minimum Remaining Value (MRV).Minimum remaining value dapat bekerja bersamaandengan FC dengan memilihkan variabel yang diisikan.Variabel yang dipilih adalah variabel yang memilikidomain paling sedikit. Pertimbangan yang digunakanadalah variabel yang jumlah domain-nyapaling sedikit mempunyai kesempatan gagal lebihbesar. Hal ini dapat memotong percabangan treeyang tidak perlu dan mempercepat waktu pembuatanjadwal.