constraint satisfaction problems merupakan sebuah pendekatan untuk menyelesaikan suatu masalah...

8/4/2019 Constraint Satisfaction Problems Merupakan Sebuah Pendekatan Untuk Menyelesaikan Suatu Masalah Dengan Tuju

1/8

ASSIGNMENT ARTIFICIAL INTELLIGENT

CONSTRAINT SATISFACTION PROBLEM (CSP)

DISUSUN OLEH

SANDAG, GREEN A.

08520075

FAKULTAS ILMU KOMPUTER

UNIVERSITAS KLABAT

2010


2/8


3/8

Variables WA, NT, Q, NSW, V, SA, T DomainsDi = {red,green,blue} Constraints: 2 wilayah yang berbatasan harus berbeda warna:WA NT, NT SA, . . .(WA, NT) {(red, green), (red, blue), (green, red), (green,

blue),..}

Contoh sulusi CSP mewarnai peta:

Solusi adalah pemberian nilai setiap variabel yang memenuhi syarat, mis:

{WA = red, NT = green,Q = red,NSW = green, V = red, SA = blue, T = green}

Representasi CSP

CSP biasanya direpresentasikan dengan sebuah graf, tanpa arah, disebut sebagai Constraint

Graph, dengan node-nya adalah variable dan jalurnya adalah batasan yang dimiliki oleh node.Untuk batasan tunggal, dapat dilengkapi dengan mendefinisikan ulang domain yang ada

sehingga mengisi variable tersebut. Constraint dengan batasan yang lebih tinggi dapat dinyatakan

dalam arc(jalur berarah).

Sebuah constraint akan dapat mempengaruhi satu atau lebih variable(1n) dalam definisipermasalahan. Jika semua constraint dalam CSP adalah biner(ada minimal 2 variabel

kemungkinan untuk solusi berikut), maka semua bariabel dan constraint dapat derepresentasikandalam sebuah graf, dan algoritma CSP dapat diberlakukan untuk mengeksploitasi graf.

Constraint Graph

Binary CSP: sebuah constraint menyangkut hubungan maksimal 2 variable.

Constraint graph: representasi di mana node adalah variable, edge adalah constraint, misalkan:


4/8

CSP Dapat Dikelompokkan Menjadi

1. Berdasarkan nilai domain : Variabel diskrit

Domain berhingga (finite): dengan ukuran d, ada O(dn) kemungkinan assignment yang lengkap.Domain tak hingga(infinite), mis: integer, string, dll. Misalnya: penjadwalan (kuliah, bis,

pekerjaan, dll.). Perlu constraint language, mis: + 5 Integer CSP denganlinear constraint dapat diselesaikan

Variabel continuous: contohnya linear programming2. Berdasarkan banyaknya variabel dengan jenis constraint :

Unary constraint: menyatakan persyaratan sebuah variabel, mis: SA green Binary constraint: menyatakan persyaratan sepasang variabel, mis: SA WA n-ary constraint (higher-order): menyatakan persyaratan tiga atau lebih variabel,

misalnya: cryptarithmetic

Preference, atau soft constraint: syarat yang sebaiknya dipenuhi, tetapi tidak harus.Mis: r lebih baik dari g. Biasanya dinyatakan sebagai cost sebuah nilai variabel.3. Apakah constraint merupakan keharusan atau preference :

Absolute: violation which rules out a potential solution Preference: constraint yang dibuat sesuai dengan keinginan atau tidak mutlak ada.Keuntungan CSP:

Successor function dan goal test tidak problem specific Heuristic function, tidak ada problem atau domain specific Constraint graph dapat digunakan untuk menyederhanakan proses solusiMenyelesaikan CSP dengan search biasa:

Mari kita mulai dengan pendekatan sederhana dengan mengformulasikan masalah CSP sebagai

search

Initial state: assignment kosong: {}

Successor function: pilih nilai untuk sebuah variable yang belum di-assign yang sah: tidak

konflik dengan assignment. Jika tidak ada: gagal!

Goal test: apakah assignment sudah lengkap.

Solusi pasti di depth n untuk n variabel depth first search di sini Path tidak penting.

Backtracking search for CSPVariable assignment berlaku komutatif, dalam arti: [WA=red lalu NT=green] sama saja

[NT=green lalu WA=red]. Pada tiap level, hanya perlu meng-assign satu variable b = d, ada leaf... Depth first search pada CSP dengan assignment satu variabel tiap level disebut

backtracking search.

Dalam metode ini, diperlukan penyusunan ulang dalam urutan pengisian variable. Cara yangpaling efektif adalah dengan mencari solusi untuk variable dengan constraint terbanyak, atau


5/8

dengan domain yang paling sedikit. Urutan akan sangat menentukan cepat atau lambatnya solusi

ditemukan. Algoritma dimulai dengan mengisikan variable dalam contraintnya, kemudianmelakukan evaluasi terhadap constraint, apakah terpenuhi atau tidak. Lakukan hal yang sama,

sampai semua variable terisi. Jika variable tidak dapat diisikan, maka harus dilakukan

pengecekan ulang (backtracking), ke node di atasnya, atau variable sebelumnya.

Contoh backtracking

Performance CSPCSP dapat diselesaikan tanpa domain spesifik heuristic menggunakan General Purpose Methodyang dapat meningkatkan speed atau kecepatan dalam proses pencarian

Urutan pemilihan variable dan nilai mempengaruhi kinerja backtracking. Terdapat beberapa

strategi yang berlaku secara umum (general-purpose):

1 Variable mana yang perlu di-assign terlebih dulu?

2 Nilai apakah yang perlu dicoba terlebih dulu?3 Apakah kita bisa mendeteksi kepastian failure lebih awal?

4 Apakah kita bisa memanfaatkan struktur masalah CSP? (Representasinya jelas!)

Most Constrained Variable

Variabel yang paling dibatasi adalah memilih variable yang memiliki kemungkinan nilai sah

paling sedikit

Most Constraining VariableVariable paling membatasi adalah memilih variable yang terlibat constraint dengan variable lain

(yang belum di-assign) yang paling banyak.Tie breaker : gunakan kalau ada 2 atau lebihvariable yang sama bagusnya berdasarkan Most Constrained Variable.


6/8

Least Constraining Value

Nilai paling membatasi adalah memilih nilai yang menimbulkan batasan kemungkinan nilaivariable lain (yang belum di-assign) yang paling sedikit.

Jika ketiga prinsip ini digunakan, masalah n-queens dengan n=1000 bisa diselesaikan!

Forward checking

Catat kemungkinan nilai sah untuk semua variabel yang belum di-assign. Jika ada sebuah

variable yang tidak ada kemungkinan nilai sah, langsung failure (backtrack). Teknik inimenggunakan constraint selama proses pencarian. Setiap kali variable X diassign nilai maka

harus mencek setiap unassign variable Y yang terhubung dengan X. Kemudian hapus setiap nilai

atau domain pada Y yang inconsistent dengan nilai yang dipilih untuk X.

Kelemahannya: tidak mendeteksi semua kegagalan di awal proses pencarian.

Constraint propagation

Forward checking mem-propagasi (meneruskan) informasi dari variable yang sudah di-assign keyang belum. Secara umum, ini disebut constraint propagation. Namun, tidak semua failure bisa

di-deteksi secara dini:


7/8

NT dan SA tetanggaan ! tidak boleh sama-sama biru!. Forward checking hanya

mempertimbangkan setiap constraint secara terpisah. Jika tidak konsisten maka akan dideletevariable tersebut. Sedangkan untuk proses constraint propagation itu mencek implikasi suatu

constraint pada sebuah variable terhadap vaiable yang lain. Menggunakan teknik ini adalah

merupakan tekni pencarian yang cepat. Jika untuk setiap nilai X yang ada pada variable A ada

beberapa nilai Y dari variable B yang consistent dengan X, maka variable A dan variable Bdikatakan consistent jika tidak consistent maka delete nilai pada variable B

Arc ConsistencyArc consistency adalah metode constraint propagation yang lebih canggih. Konsistensi antar

constraint dipertahankan. Arc X Y adalah edge satu arah dari variable X ke Y dalam

constraint graph.Prinsip Arc Consistency X Y dikatakan konsisten jika dan hanya jika untuk setiap nilai sah x

dari X ada nilai sah y dari Y.

Algoritma AC3Algoritma AC3 melakukan constraint propagation sbb:

Periksa semua arc dalam constraint graph, jika untuk X Y ada nilai sah x dari X sehingga

tidak ada nilai sah y dari Y, buang x. Jika ada nilai x yang dibuang, periksa ulang semua

tetangga X di dalam constraint graph. Algoritma AC3 ini bisa mendeteksi failure lebih cepatdaripada forward checking. AC3 dapat dijalankan sebagai pra-proses sebelum melakukan

backtracking, atau bisa dijalankan setelah setiap assignment.


8/8

Kelemahan dari Arc Consistency: tidak semua inconsistency dapat ditemukan oleh algoritma

AC3.Ketika algoritma AC3, mengunjungi kembali jalur pada kesempatan kedua, algoritma ini akan

melakukan evaluasi ulang terhadap nilai-nilai variable yang telah diketahui sebelumnya untuk

mencapai kekonsistenan atau ketidak-konsistenan, dan tidak dipangaruhi oleh reduksi domain .

karena adanya pengulangan evaluasi dan dinilai tidak efisien maka diperkenalkan algoritma AC-4 untuk menangani constraint pada jalur(edge). Algoritma ini bekerja dengan nilai individual

yang berpasangan.

Submasalah independen

Assignment T (Tasmania) adalah submasalah independen. Andaikan CSP dengan n variabel !

submasalah masing-masiang c variabel: Dari O() menjadi O(n/c ) misalkan boolean CSP

n = 80, d = 2, c = 20, bisa memproses 10 juta node/detik 4 miliar tahun jadi 4 x

Pendekatan local search untuk solusi CSPDalam praktek, local search cocok untuk CSP. State harus lengkap/complete (semua variable

harus ter-assign) tapi boleh melanggar constraint. Operator/action-nya: menukar nilai variabel

(reassign). Pemilihan variable: pilih secara acak variable yang melanggar sebuah constraint.

Pemilihan nilai: gunakan heuristic minimum conflict: pilih nilai yang melanggar constraintpaling sedikit. Lakukan local search (hillclimb, simulated annealing, genetic algorithm, dll.)

meminimalkan h(n) = jumlah pelanggaran constraint.Perhatian: secara teoritis pendekatan ini tidak dijamin complete.

Local search untuk CSPContoh masalah 4-queens:

State: 4 menteri dalam 4 kolom (44 = 256 state)

Operator/action: pindahkan menteri dalam kolomGoal test: tidak ada menteri saling makan

Evaluation/fitness function: h(n) = jumlah pasangan menteri saling makan

Metode inin bisa menyelesaikan 1000000-queens problem!

constraint satisfaction problems merupakan sebuah pendekatan untuk menyelesaikan suatu masalah...

Documents