PENGERTIAN
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 variabel X1,X2,X3,…..,Xn,
Variabel adalah elemen atau entity yang ingin dicari nilainya sehingga pemberian nilai pada variabel dapat menjadi solusi dari CSP.
CSP dapat direpresentasikan sebagai berikut :
1. Kumpulan variabel.
X --> kumpulan dari n variabel 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 nilainilai yang mungkin untuk variabel tertentu yang bertujuan untuk menyelesaikan persoalan.
3. Constraint C --> kumpulan dari constraintconstraint 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 nilainilai variabel tersebut merupakan solusi untuk persoalan.
Cryptarithmetic merupakan pengetahuan dan seni untuk menciptakan dan menyelesaikan mathematic puzzle, dimana digit-digit ditukar dengan hurufhuruf 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 (couple + couple = quartet) yaitu:
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.
3. Constraint C --> kumpulan dari constraintconstraint 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 nilainilai variabel tersebut merupakan solusi untuk persoalan.
Cryptarithmetic merupakan pengetahuan dan seni untuk menciptakan dan menyelesaikan mathematic puzzle, dimana digit-digit ditukar dengan hurufhuruf 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 (couple + couple = quartet) yaitu:
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.
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.
Referensi :
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2005-2006/Makalah2006/MakalahStmik2006-47.pdf
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.
Referensi :
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2005-2006/Makalah2006/MakalahStmik2006-47.pdf
0 Komentar