Constraint Satisfaction Problem (CSP)

Constraint Satisfaction Problem (CSP)

Constraint Satisfaction Problem adalah permasalahan  yang tujuannya adalah mendapatkan suatu kombinasi variabel-variabel tertentu yang memenuhi aturan-aturan (constraints) tertentu.
CSP adalah suatu permasalahan seseorang yang harus mencari nilai untuk set variabel (finite) yang memenuhi set constraint (finite).

Komponen - komponen yang tedapat pada CSP :

• Variabel      : merupakan penampung yang dapat diisi dengan nilai tertentu.
• Constraint : sesuatu aturan ditentukan untuk mengatur nilai boleh diisikan pada variabel
• Domain      : kumpulan nilaiyang legal dapat diisi ke variabel

Cryptarithmatic merupakan penyelesaian mathematic puzzle, dimana digit diganti dengan huruf alfabet atau simbol lain sesuai yang diinginkan.

Backtracking adalah algoritma berbasis DFS (Depth First Search) untuk mencari solusi tepat. Dalam metode ini tidak perlu memeriksa semua kemungkinan atau solusi yang ada, hanya pencarian yang mendekati solusi sajayang diperiksa.

Contoh permasalah CSP dengan menggunakan Backtracking :

   

Variabel : {M, O, S, E, N, R, D, Y, X1, X2, X3}

Domain : Di = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Constaint :D + E = Y + 10*X1

                    X1 + N + R = E + 10*X2

                    X2 + E + O = N + 10*X3

                    X3 + S + M = O + 10*M

Initial State : Setiap variabel masih berbentik huruf atau simbol

Succesor : Pemberian nilai pada setiap variabel, tetapi setiap nilai harus berbeda untuk setiap variabelnya.

Path Cost : Jumlah pencarian solusi permasalahan agar mencapai goal statenya

Goal State : Setiap menilai sudah memiliki nilai yang sesuai dengan constraint yang harus dipenuhi.

Hasil yang didapat :

M : 1                  D : 7

O : 2                   Y : 2

S : 9                   X1 : 1

E : 5                   X2 : 1

N : 6                  X3 : 0

R : 8 

 

Atau

Constraint-constraint yang mendefinisikan sebuah cryptarithmetic problem antara lain :

1. Masing-masing huruf atau symbol  merepresentasikan digit yang hanya satu dan unik dalam persoalan tersebut. 
2. Ketika digit-digit menggantikan huruf atau simbol, maka hasil dari operasi aritmatika harus benar.   

• variablenya : (C,O,U,P,L,E,A,Q,R,T) 
• Domain       : (0,1,2,3,4,5,6,7,8,9)

1. Pemberian digit atau nilai harus berbeda untuk setiap variabel {C, O, U, P, L, E, Q, A, R, T} yaitu digit {0,…..9} sehingga persamaan COUPLE + COUPLE = QUARTET terpenuhi.
2. Apabila masing-masing variabel sudah diberikan nilai, maka pemberian nilai harus memenuhi constraint yang ada, sehingga pada saat operasi aritmatika dilakukan untuk nilai setiap variabel, maka hasil dari operasi penjumlahan COUPLE + COUPLE = QUARTET harus sesuai.
3. Variabel-variabel untuk persoalan cryptaritmetic ini ada 10 variabel, antara lain : C, O, U, P, L, E, Q, A, R, dan T. 
4. Persoalan cryptaritmetic ini akan menggunakan bit carry, yaitu variabel X1, X2, X3, X4, dan X5.  

Persoalan cryptarithmetic: Diberikan sebuah bentuk cryptarithmetic dengan n buah variabel dan disediakan m buah angka. Berikan angka yang sesuai untuk setiap variabel, dan hasil aritmatika setelah setiap variabel diberi angka, harus sama dengan bentuk awal dan tidak ada variabel yang diberi angka yang sama.

Untuk persoalan ini, karena jumlah variabel ada 10, maka pastilah kesepuluh angka harus dipakai.  

       X5  X4 X3 X2 X1       
         C  O  U  P  L  E       
         C  O  U  P  L  E
       ---------------------- +    
     Q U  A  R  T  E  T 


Bit carry X1 = {0,1}, X2 = {0,1}, X3 = {0,1}, X4 = {0,1}, X5 = {0,1}.
         

• Constraint-contraint yang ditentukan untuk persoalan cryptarithmetic yaitu:

 • E + E = T + 10 * X1
 • X1 + L + L = E + 10 * X2
 • X2 + P + P = T + 10 * X3
 • X3 + U + U = R + 10 * X4
 • X4 + O + O = A + 10 * X5
 • X5 + C + C = U + 10 * Q

Solusi dinyatakan sebagai vektor X dengan n-tuple:

X = (x1, x2, ……., xn), xi Є {0,1,2,…..,9}
 
Angka variabel ke-k, xk, ditentukan dengan algoritma berikut: 

1. Bangkitkan angka i 
2. Periksa pemberian angka berdasarkan constraint yang ada 
3. Jika angka i yang dibangkitkan tidak melanggar constraint untuk variabel tersebut, maka variabel k diberi angka i, kalau tidak bangkitkan angka berikutnya, dan ulangi langkah 2 di atas. 
4. Jika tidak ada lagi angka yang dapat dibangkitkan (angka habis), maka persoalan cryptarithmetic dengan n variabel dan m warna tidak dapat diselesaikan.

Karena penamaan simpul adalah angka, bukan variabel, sehingga untuk setiap variabel akan diberi urutan nomor dimulai dari variabel paling kanan dari cryptarithmetic yaitu E sampai ke paling kiri yaitu Q, sebab operasi yang dilakukan adalah penjumlahan sehingga harus dimulai dari sebelah kiri, yaitu:

E = 1  R = 6
T = 2  O = 7
L = 3  A = 8
P = 4  C = 9
U = 5  Q = 10

Perlu diingat : pemberian nomor untuk variabel bukanlah solusi, tetapi hanya untuk mempermudah proses iterasi.

• Initial state

         C  O  U  P  L  E       
         C  O  U  P  L  E
       ---------------------- +    
     Q U  A  R  T  E  T 

• Operator Succesor : (0,1,2,3,4,5,6,7,8,9)

• Path cost

 • E + E = T + 10 * X1
 • X1 + L + L = E + 10 * X2
 • X2 + P + P = T + 10 * X3
 • X3 + U + U = R + 10 * X4
 • X4 + O + O = A + 10 * X5
 • X5 + C + C = U + 10 * Q

• Goal state 

E = 1  R = 6 T = 2  O = 7
L = 3  A = 8
P = 4  C = 9
U = 5  Q = 10

  

Referensi :

• http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2005-2006/Makalah2006/MakalahStmik2006-47.pdf  
• http://slideplayer.info/slide/2819535/
• http://maisarohmae23.blogspot.co.id/2016/10/csp-constraint-satisfaction-problem.html
• http://clear-shade.blogspot.co.id/2016/10/cryptarithmetic-solve-with-algorithm.html