Constraint Satisfaction Problem

Disini saya akan menjelaskan sedikit tentang CSP (Constraint Satisfaction Problem). Untuk lebih jelas nya terdapat di modul yang berjudul seperti dibawah.

1.      Pendahuluan

CSP merupakan teknik yang dapat digunakan untuk penyelesaian persoalan dalam dunia nyata, yang terkadang memberikan batasan tertentu yang tidak boleh dilanggar pada saat mencari solusinya. Pada saat melakukan pencarian solusi atau pemilihan urutan aksi, teknik penyelesaian ini akan selalu menyesuaikan dengan constraint-constraint yang sudah ditentukan sebelumnya, sedemikian sehingga semua constraint akan terpenuhi.

CSP dapat direpresentasikan sebagai berikut :

1.      Kumpulan variabel. X      Æ       kumpulan      dari      n      variable X1,X2,X3,…..,Xn, Variabel adalah elemen atau entity yang ingin dicari nilainya sehingga pemberian nilai pada variabel dapat menjadi solusi dari CSP.

2.      Domain D Æ  Masing-masing variabel didefinisikan oleh suatu domain yang finite D1,D2,………,Dn, yang berisi kumpulan nilai- nilai yang mungkin untuk variabel tertentu yang bertujuan untuk menyelesaikan persoalan.

3.      Constraint C Æ kumpulan dari constraint- constraint C1,C2,……,Cm. Ci merupakan constraint-constraint yang berisi batasan nilai untuk setiap variabel dan tidak boleh dilanggar. Constraint-constraint ini akan membatasi domain dari suatu variabel sehingga menjadi lebih sempit

4.      Assignment Æ pemberian nilai pada suatu variabel.

5.      Solusi Æ pemberian nilai-nilai pada setiap variabel yang memenuhi semua constraint yang telah ditetapkan untuk persoalan, sehingga nilai- nilai variabel tersebut merupakan solusi untuk persoalan.

2.      Deskrispsi Masalah Cryptarithmetic

Cryptarithmetic merupakan   pengetahuan dan seni untuk menciptakan dan menyelesaikan mathematic puzzle, dimana digit-digit ditukar dengan huruf- huruf alfabet atau symbol lain.

Cryptarithmetic merupakan salah satu contoh persoalan yang dapat diselesaikan dengan   CSP, dengan constraint yang melibatkan 3 atau lebih variabel.  Cryptarithmetic merupakan  contoh  yang sangat cocok untuk CSP, karena selain menyediakan deskripsi, masalah cryptarithmetic dapat dijelaskan lebih baik dengan constraint-constraint.

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.

Batasan-batasan di atas memunculkan beberapa batasan baru dalam persoalan, yaitu apabila basis dari angka adalah 10, maka pasti akan ada paling banyak 10 simbol atau huruf yang unik dalam persoalan.  Jika  tidak,  maka  tidak  akan  mungkin untuk memberikan digit yang unik ke setiap huruf atau simbol yang unik juga dalam persoalan. Dan supaya memiliki makna yang  berarti secara semantik, angka tidak boleh dimulai dengan 0, jadi huruf-huruf yang muncul untuk setiap variabel pertama sekali seharusnya tidak boleh mengandung 0.

     Spesifikasi  persoalan  cryptarithmetic  (TIGA + TIGA = ENAM ) yaitu:

1.   Pemberian digit atau nilai harus berbeda untuk setiap variabel {T, I, G, A, E, N, M} yaitu digit {0,…..9} sehingga persamaan TIGA + TIGA = ENAM 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 TIGA + TIGA = ENAM harus sesuai.

3. Variabel-variabel     untuk     persoalan cryptaritmetic ini  ada  7  variabel,  antara lain : T, I, G, A, E, N, dan M

4. Persoalan   cryptaritmetic   ini   akan menggunakan bit carry, yaitu variabel X1, X2, dan X3.

  

  Penyelesaian cryptarithmetic

Pertama tama kita lihat apa saja yang bisa kita lakukan untuk mengurangi kemungkinan kemungkinan yang terjadi. Seperti yang dijelaskan diatas variabel pertama tidaklah mungkin menjadi 0 maka jadi lah A != 0. Dan untuk variable terakhir tidaklah lebih dari 5 karena jika variable akhir lebih dari 5 hasil nya akan tidak kompatible maka T<5.

Selanjutnya kita mulai menyelesaikan persamaan tersebut. Kita misalkan A = 2 ; G = 3 ; I = 8; T =4. Maka persamaan nya akan menjadi

Ini bukan lah hasil yang sesuai karena tidak memenuhi constran constran tersebut

Selanjutnya kita lakukan permisalan yang lain seperti :  A = 4 ; G = 2 ; I = 5; T =3;

Maka persamaan nya akan menjadi

Dan hasil ini sesuai dengan constraint-constraint yang telah ditetapkan
 

Dengan cara seperti ini banyak hasil yang bisa didapatkan, untuk contoh lain dan cara penyelesaian dapat dilihat pada modul yang berjudul “Persoalan Cryptarithmetic dengan Algoritma Backtracking”

Source :

-          Modul “Persoalan Cryptarithmetic dengan Algoritma Backtracking”