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

Knapsack Problem Metode Greddy (Soal Bonus)

Knapsack Problem

Knapsack adalah tas atau karung. Karung digunakan untuk memuat sesuatu. Dan tentunya tidak semua objek dapat ditampung di dalam karung tersebut. Karung tersebut hanya dapat menyimpan beberapa objek dengan total ukurannya (weight) lebih kecil atau sama dengan ukuran kapasitas karung. 

Penggunaan Metode Greddy salah satunya adalah untuk menyelesaikan permasalahan Knapsack, Knapsack problem bisa di gambarkan, misalnya kita mempunyai kantong dengan kapasitas tertentu sedangkan dihadapan kita terdapat begitu banyak pilihan barang, maka kita harus memilih barang mana saja yang kira-kira akan kita angkut sesuai dengan kapasitas kantong yang kita miliki supaya bisa mendapatkan keuntungan yang maksimal.

Algoritma Greedy
Teknik  pemrograman  dengan  menggunakan  Greedy  sering  digunakan  untuk permasalahan  optimasi.  Secara  umum  teknik  ini  menggunakan  heuristic  untuk mencari solusi suboptimum sehingga diharapkan solusi optimum.
Pada Greedy  Algorithm ada  beberapa  strategi yang  digunakan untuk  memilih objek yang akan dimasukkan ke dalam knapsack.
  

Jenis-Jenis Knapsack Problem
Terdapat beberapa variasi Knapsack problem:

• 0/1 Knapsack problem : Setiap barang hanya tersedia 1 unit, take it or leave it.

• Fractional Knapsack problem : Barang boleh dibawa sebagian saja (unit dalam pecahan). Versi problem ini menjadi masuk akal apabila barang yang tersedia dapat dibagi-bagi misalnya gula, tepung, dan sebagainya.

• Bounded Knapsack problem : Setiap barang tersedia sebanyak N unit (jumlahnya terbatas).

• Unbounded Knapsack problem : Setiap barang tersedia lebih dari 1 unit, jumlahnya tidak terbatas

Dalam menghadapi masalah di atas, metode greddy memiliki 3 pilihan strategi pengangkutan, yaitu :

1. Greedy by Profit
   Strategi ini mengharapkan keuntungan maksimal dengan cara memasukan barang dengan nilai keuntungan terbesar terlebih dahulu ke dalam Knapsack. Strategi ini hanya mempertimbangkan jumlah keuntungan dari sekumpulan barang, dengan catatan berat barang yang akan dibawa tidak melebihi kapasitas kantong yang kita miliki.
2. Greedy by weight 
   Strategi ini, kita berusaha memasukan barang semaksimalnya kedalam kantong  barang yang dimasukan terlebih dahulu adalah bobot paling ringan terlebih dahulu, dengan banyaknya barang yang terangkut kita bisa mendapatkan keuntungan semaksimal mungkin.
3. Greedy by density
   Strategi ini mengharapkan keuntungan semaksimal mungkin dengan memasukan barang  yang memiliki keuntungan per unit terbesar (Pi/Wi) terlebih dahulu kedalam kantong. 

Tata cara penggunaan Metode Greddy dalam persoalan Knapsack adalah

• Masukkan objek satu per satu ke dalam knapsack. Sekali objek dimasukkan ke dalam knapsack, objek tersebut tidak bisa dikeluarkan lagi. 

Namun karena Metode Greddy hanya mempertimbangkan keuntungan local dengan harapan mendapat keuntungan global, maka metode ini juga tidak menjamin akan memberikan solusi optimal.

 Contoh masalah Knapsack :

Permasalahan knapsack atau yang biasa kita kenal dengan sebutan 0/1 knapsack merupakan salah satu dari persoalan klasik yang banyak ditemukan pada literatur-literatur lama dan hingga kini permasalahan ini masih banyak ditemukan dalam kehidupan sehari-hari. Contoh kongkret permasalahan ini dalam dunia nyata adalah penjualan beberapa jenis keperluan rumah tangga oleh pedagang keliling dengan menggunakan gerobak ataupun alat pengangkut lainnya yang hanya memiliki kapasitas angkut maksimum sebesar w kg keperluan rumah tangga yang akan dijual hanya berjumlah satu untuk tiap jenisnya dan tiap jenis barang memiliki berat w1,w2,w3,w4, ..wn dengan keuntungan yang diperoleh untuk tiap jenisnya adalah p1,p2,p3,p4, .pn. tidak semua jenis keperluan rumah tangga yang akan dijual oleh pedagang keliling tersebut dapat dimasukan kedalam alat pengangkut. Maka akan dipilih jenis-jenis keperluan rumah tangga yang akan dijual untuk setiap harinya oleh pedagang keliling tersebut agar diperoleh keuntungan yang maksimal dari penjualan barang-barang keperluan rumah tangga tersebut.

Contoh Soal Knapsack dan Fractional Knapsack :

1.    w₁ = 10;  p₁ = 2

w₂ = 5;     p₂ = 3

w₃ = 15;   p₃ = 5

w₄ = 7;     p₄ = 7

w₅ = 6;     p₅ = 1

w₆ = 18;   p₆ = 4

w₇ = 3;     p₇ = 1

M = 15

Jawaban : 

• 1/0 Knapsack M= 15 

Properti objek				Greedy by			Solusi Optimal
i	wi	pi	pi /wi	profit	weight	density
1	2	10	5	1	1	1	1
2	3	5	1,7	1	1	0	1
3	5	15	3	1	0	1	1
4	7	7	1	0	0	0	0
5	1	6	6	1	1	1	1
6	4	18	4,5	1	1	1	1
7	1	3	3	0	1	1	0
Total bobot :				15	11	13	15
Total keuntungan :				54	42	52	54

• Kesimpulan : Pada soal ini, algoritma greedy dengan strategi pemilihan objek berdasarkan profit memberikan solusi optimal, sedangkan pemilihan objek berdasarkan weight dan density tidak memberikan solusi optimal. 

•       Fractional Knapscak M=15

Properti objek				Greedy by
i	wi	pi	pi /wi	profit	weight	density
1	2	10	5	1	1	1
2	3	5	1,7	0	1	2/3
3	5	15	3	1	4/5	1
4	7	7	1	4/7	0	0
5	1	6	6	0	1	1
6	4	18	4,5	1	1	1
7	1	3	3	0	1	1
Total bobot :				15	15	15
Total keuntungan :				47	48	55

·         Solusi optimal X = (1,2/3,1,0,1,1,1)

·         Yang memberikan keuntungan maksimum 55

 Referensi : 

• http://nurmaghany.blogspot.co.id/2012/01/knapsack-algoritma.html
• http://itsmepowel.blogspot.co.id/2012/01/tugas-uas-knapsack.html
• http://sitiekachotimah.blogspot.co.id/2012/04/contoh-soal-knapsack-dan-fractional.html