Solusi Constraint Satisfaction Problems

Solusi Constraint Satisfaction Problems

a. Generate And Test

Melalui cara ini kita haru membangkitkan satu persatu alokasi variable sehingga memenuhi semua constrainnya. Struktur program untuk cara ini sangat sederhana, hanya berupa konstruksi loop, satu untuk setiap variable, dan setiap constraint. Metode ini tidak efektif karna memiliki kompleksitas waktu yang tinggi.

Metode ini merupakanpenggabunganantaradepth-first search dengan pelacakan mundur(backtracking), yaitu bergerak kebelakang menuju pada suatu keadaan awal.

Algoritma:

1.Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).

2.Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.

3.Jikas solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.

b. Backtracking

Dalam metode ini dibutuhkan penyusunan ulang dalam urutan variable. Cara yang paling efektif adalah dengan mencari solusi untuk variable dengan constraint terbanyak atau dengan domain yang paling sedikit. Urutan akan menentukan cepat atau lambatnya solusi yang ditemukan. Algoritma dimulai dengan mengisikan variable dalam constraint-nya, kemudian melakukan evaluasi terhadap constraint , apakah terpenuhi atau tidak. Lakukan hal yang sama sampai semua variable terisi. Jika variable tidak dapat diisikan, maka harus dilakukan penelaahan ulang (backtracking), ke node di atas atau variable sebelumnya.