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.
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.
Untuk mempermudah pemahaman
terhadap suatu CSP, maka umumnya persoalan ini digambarkan dalam bentuk graf,
dan disebut constraint graph. Constraint graph terdiri dari simpul – simpul
yang merepresentasikan variabel pada CSP yang akan dicari nilainya, dan busur
pada graf menggambarkan constraint di antara variabel yang dihubungkannya. Jika
dua variabel tidak terhubung dengan suatu busur, maka di antara dua variabel
tersebut tidak memiliki hubungan constraint, jadi tidak perlu diperiksa
kekonsistenannya pada saat pemberian nilai.
Tujuan utama dari penyelesaian
CSP yaitu untuk memberikan nilai pada semua komponen persoalan, dengan tidak
melanggar constraint yang telah ditetapkan untuk persoalan tersebut.
Deskripsi Umum Algoritma Backtracking Runut-balik (backtracking)
adalah algoritma yang berbasis pada DFS untuk mencari solusi persoalan secara
lebih mangkus. Runut-balik merupakan perbaikan dari algoritma exhaustive-search
yang secara sistematis akan melakukan pencarian solusi permasalahan di antara
semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja
yang akan dipertimbangkan. Akibatnya, waktu pencarian dapat dihemat.
Runut-balik lebih alami dinyatakan dalam algoritma rekursif. Untuk
memfasilitasi pencarian ini, maka ruang solusi diorganisasikan ke dalam
struktur pohon. Tiap simpul pohon menyatakan status (state) persoalan,
sedangkan sisi (cabang) dilabeli dengan nilai – nilai x. Lintasan dari akar ke
daun menyatakan solusi yang mungkin. Seluruh lintasan dari dari akar ke daun
membentuk ruang solusi.
 |
| Stage Awal |
 |
| Goal Stage |
Deskripsi Umum Game Sudoku. Sudoku merupakan salah satu permainan
yang sangat populer. Pada permainan ini akan terdapat kotak besar yang disusun
oleh kotak-kotak kecil. Kota kecil akan tersusun oleh n2 space sebagai tempat
untuk memposisikan angka. Kemudian kotak – kotak kecil terebut akan menyusun
kotak besar sehingga ukuran kotak besar adalah n2 x n2 .
Objektif dari permainan ini
adalah bagaimana kita bisa mengatur susunan angka – angka yang telah ditentukan
kedalam suatu space pada kotak, dengan syarat bahwa angka pada kolom dan baris
kotak besar tidak boleh sama demikian juga angka pada satu kotak kecil tidak
boleh sama. Cara penyelesaian permainan ini dirancang dengan menggunakan
algoritma backtracking dalam menemukan susunan angka yang sesuai untuk mengisi
space – space yang ada sesuai dengan batasan yang telah dijelaskan sebelumnya,
yaitu angka pada satu baris, satu kolom dan satu kotak kecil tidak boleh sama.
Dalam implementasinya , proses
pencarian pada algoritma backtracking sebenarnya identik dengan penggunaan algoritma
exhaustive-search namun dengan proses yang lebih sistematis. Secara garis besar
langkah – langkah yang dilakukan oleh program dalam pencarian solusi adalah
sebagai berikut :
1. Menguji sembarang nilai (0
< nilai < n+1) dengan fungsi pembatas yang ada.
2. a. Jika nilai tersebut
memenuhi fungsi pembatas maka kotak akan terisi dengan nilai uji tersebut
kemudian proses akan berpindah ke kotak berikutnya.
b. Jika nilai tersebut tidak
memenuhi fungsi pembatas, maka program akan mengambil nilai yang belum dipakai.
3. Jika semua opsi nilai pada
domain nilai telah dicoba dan tidak ada satupun yang memenuhi fungsi pembatas,
maka terjadi backtracking ke kotak sebelumnya. MAKALAH IF2251 STRATEGI
ALGORITMIK TAHUN 2007
4. Pada kotak hasil backtracking
ini, program akan menguji fungsi pembatas dengan nilai baru.
5. a. Jika nilai baru tersebut
dapat memenuhi fungsi pembatas, maka nilai tersebut akan diisikan ke dalam
kotak. Kemudian proses pengisian akan berpindah ke kotak berikutnya. b. Jika
semua opsi nilai baru yang ada pada domain tidak dapat memenuhi fungsi pembatas
maka akan terjadi lagi backtracking ke kotak sebelumnya.
6. Program akan melakukan proses di atas
secara rekursif sampai ditemukan penyelesaian atau tidak terdapat penyelesaian.
a. Terdapat penyelesaian :
program berhasil mengisi semua kotak kosong yang tersedia dengan nilai yang
memenuhi fungsi pembatas.
b. Tidak terdapat penyelesaian :
setelah beberapa saat mencari solusi, ternyata program melakukan backtracking
hingga kembali ke kotak pertama dan saat nilai indeks baris = -1 menandakan
bahwa program tidak berhasil menemukan solusi.
Implementsi domain solusi permasalahan
Himpunan ruang solusi terdiri :
{nilai| 0 < nilai < n+1;
nilai є integer} dengan n adalah ukuran kotak kecil.
Implementsi fungsi –fungsi pembatas
Sebagaimana telah saya sampaikan di atas game sudoku mempunyai fungsi pembatas
yang cukup menarik dan unik, yaitu :
a. angka pada
satu baris tidak boleh sama,
b. angka pada
satu kolom tidak boleh sama, dan
c. angka pada
satu kotak kecil tidak boleh sama.
Berikut
saya tampilkan source code dari ketiga fungsi pembatas tersebut, sengaja
dituliskan dalam bahasa java untuk memudahkan pembaca bila ingin mencoba
menjalankan ketiga fungsi tersebut tanpa perlu menerjemahkannya terlebih dahulu
ke suatu bahasa pemrograman. Semoga dapat membantu dalam memahami fungsi
batasan yang dimiliki permainan ini.
a.
A. Cek Kolom. Spesifikasi : Pada suatu kolom tidak
boleh ditemukan 2 (dua ) nilai yang sama.
Tidak ada komentar:
Posting Komentar