SSSS, Problem Solving
State Space Search Erick Pranata Edisi I
19/04/2013
Definisi Merupakan sebuah teknik dalam kecerdasan buatan yang dapat digunakan untuk mencari langkah-langkah yang perlu ditempuh untuk mencapai tujuan yang diharapkan secara otomatis. Beberapa hal yang harus diformulasikan terlebih dahulu agar teknik ini dapat diimplementasikan dengan mudah adalah: 1. State 2. Operator 3. Initial State 4. Goal State State merupakan representasi kondisi suatu problem saat ini. State dapat berubah. Suatu masalah dimulai dari Initial State dan berakhir pada Goal State. Operator merupakan pilihan-pilihan langkah yang boleh ditempuh untuk mengubah state. Dengan demikian, kombinasi operator yang tepat dapat mengubah Initial State menjadi Goal State. Teknik ini memiliki beberapa manifestasi dengan cara kerja yang bebeda, yaitu: 1. Depth-first Search 2. Breadth-first Search 3. Uniform-cost Search 4. Best-first Heuristic Search 5. A* Optimal Heuristic Search Sementara itu, beberapa kasus yang banyak dipakai sebagai contoh kasus untuk pemahaman setiap algoritma di atas adalah: 1. Missionaries and Cannibals 2. 8-Puzzle 3. Water Jug Problem Urutan operator yang digunakan untuk mengubah Initial State menjadi Goal State biasanya direpresentasikan dalam bentuk Search Tree dan Search Graph.
Erick Pranata - State Space Search - 19/04/2013
1
Depth-first Search Sebuah algoritma yang mencari solusi dengan menelusuri dengan mendalam terlebih dahulu. Input Output Output Samping Variabel Lokal Struktur X
: : : :
state START dan state GOAL adakah urutan Operator dari START ke GOAL? stack CLOSED stack OPEN, stack CLOSED, record X, daftar SUCCESSOR : parent state, current state
1. Siapkan OPEN yang berisi (-, START) 2. Siapkan CLOSED. 3. Jika OPEN kosong: hentikan pencarian dan nyatakan pencarian sebagai gagal. 4. Jika tidak: 4.1. X = pop(OPEN), push(CLOSED, X). 4.2. Jika X.current adalah GOAL: hentikan pencarian dan nyatakan pencarian sebagai sukses. (Solusi diperoleh dengan menelusuri CLOSED) 4.3. Jika tidak: 4.3.1. SUCCESSOR = expand(X.current) 4.3.2. Hapus seluruh isi SUCCESSOR yang sudah tercatat dalam CLOSED maupun OPEN 4.3.3. Push seluruh isi SUCCESSOR ke dalam OPEN dengan format yang sesuai dengan X. 4.3.4. Kembali ke step 3
Erick Pranata - State Space Search - 19/04/2013
2
Breadth-first Search Sebuah algoritma yang mencari solusi dengan menelusuri permukaan terlebih dahulu terlebih dahulu. Input Output Output Samping Variabel Lokal Struktur X
: : : :
state START dan state GOAL adakah urutan Operator dari START ke GOAL? CLOSED queue OPEN, stack CLOSED, record X, daftar SUCCESSOR : parent state, current state
1. Siapkan OPEN yang berisi (-, START) 2. Siapkan CLOSED 3. Jika OPEN kosong: hentikan pencarian dan nyatakan pencarian sebagai gagal. 4. Jika tidak: 4.1. X = delete(OPEN), push(CLOSED, X). 4.2. Jika X.current adalah GOAL: hentikan pencarian dan nyatakan pencarian sebagai sukses. (Solusi diperoleh dengan menelusuri CLOSED) 4.3. Jika tidak: 4.3.1. SUCCESSOR = expand(X.current) 4.3.2. Hapus seluruh isi SUCCESSOR yang sudah tercatat dalam CLOSED maupun OPEN 4.3.3. Insert seluruh isi SUCCESSOR ke dalam OPEN dengan format yang sesuai dengan X. 4.3.4. Kembali ke step 3
Erick Pranata - State Space Search - 19/04/2013
3
Uniform-cost Search Sebuah algoritma yang mencari solusi dengan memperhatikan cost yang dibutuhkan oleh operator yang dipilih. Input Output
: state START dan state GOAL : adakah urutan Operator dengan cost minimum dari START ke GOAL? Output Samping : CLOSED Variabel Lokal : priority queue OPEN, stack CLOSED, record X, daftar SUCCESSOR Struktur X : parent state, current state, cost (akumulasi dari START [g(x)]) 1. Siapkan OPEN yang berisi (-, START,0) 2. Siapkan CLOSED 3. Jika OPEN kosong: hentikan pencarian dan nyatakan pencarian sebagai gagal. 4. Jika tidak: 4.1. X = deleteMin(OPEN), push(CLOSED, X). 4.2. Jika X.current adalah GOAL: hentikan pencarian dan nyatakan pencarian sebagai sukses. (Solusi diperoleh dengan menelusuri CLOSED) 4.3. Jika tidak: 4.3.1. SUCCESSOR = expand(X.current). 4.3.2. Jika SUCCESSOR tidak kosong: 4.3.2.1. e = fetch(SUCCESSOR) 4.3.2.2. Jika e belum tercatat dalam CLOSED 4.3.2.2.1. Jika e tersebut belum tercatat dalam OPEN 4.3.2.2.1.1. Tambahkan 4.3.2.2.2. Jika tidak: 4.3.2.2.2.1. Pastikan bahwa yang tercatat dalam OPEN adalah e dengan cost terendah. 4.3.2.3. Kembali ke step 4.3.2. 4.3.3. Kembali ke step 3.
Erick Pranata - State Space Search - 19/04/2013
4
Best-first Heuristic Search Sebuah algoritma yang mencari solusi dengan memperhatikan cost dari state saat ini hingga state goal. Input Output
: state START dan state GOAL : adakah urutan Operator dengan cost minimum dari START ke GOAL? Output Samping : CLOSED Variabel Lokal : priority queue OPEN, stack CLOSED, record X, daftar SUCCESSOR Struktur X : parent state, current state, cost ke GOAL (Fungsi Evaluasi Heuristic [h(x)]) 1. Siapkan OPEN yang berisi (-, START,0) 2. Siapkan CLOSED 3. Jika OPEN kosong: hentikan pencarian dan nyatakan pencarian sebagai gagal. 4. Jika tidak: 4.1. X = deleteMin(OPEN), push(CLOSED, X). 4.2. Jika X.current adalah GOAL: hentikan pencarian dan nyatakan pencarian sebagai sukses. (Solusi diperoleh dengan menelusuri CLOSED) 4.3. Jika tidak: 4.3.1. SUCCESSOR = expand(X.current). 4.3.2. Jika SUCCESSOR tidak kosong: 4.3.2.1. e = fetch(SUCCESSOR) 4.3.2.2. Jika e belum tercatat dalam CLOSED 4.3.2.2.1. Jika e tersebut belum tercatat dalam OPEN 4.3.2.2.1.1. Tambahkan 4.3.2.2.2. Jika tidak: 4.3.2.2.2.1. Pastikan bahwa yang tercatat dalam OPEN adalah e dengan cost terendah. 4.3.2.3.
Kembali ke step 4.3.2
4.3.3. Kembali ke step 3.
Erick Pranata - State Space Search - 19/04/2013
5
A* Optimal Heuristic Search Sebuah algoritma yang mencari solusi dengan memperhatikan total cost dari state awal hingga state saat beserta cost dari state saat ini hingga state goal. Input Output
: state START dan state GOAL : adakah urutan Operator dengan cost minimum dari START ke GOAL dengan cost minimum? Output Samping : CLOSED Variabel Lokal : priority queue OPEN, stack CLOSED, record X, daftar SUCCESSOR Struktur X : parent state, current state, cost (akumulasi biaya dari START + Fungsi Evaluasi Heuristic [g(x)+h(x)]) 1. Siapkan OPEN yang berisi (-, START,0) 2. Siapkan CLOSED 3. Jika OPEN kosong: hentikan pencarian dan nyatakan pencarian sebagai gagal. 4. Jika tidak: 4.1. X = deleteMin(OPEN), push(CLOSED, X). 4.2. Jika X.current adalah GOAL: hentikan pencarian dan nyatakan pencarian sebagai sukses. (Solusi diperoleh dengan menelusuri CLOSED) 4.3. Jika tidak: 4.3.1. SUCCESSOR = expand(X.current). 4.3.2. Jika SUCCESSOR tidak kosong: 4.3.2.1. e = fetch(SUCCESSOR) 4.3.2.2. Jika e belum tercatat dalam CLOSED 4.3.2.2.1. Jika e tersebut belum tercatat dalam OPEN 4.3.2.2.1.1. Tambahkan 4.3.2.2.2. Jika tidak: 4.3.2.2.2.1. Pastikan bahwa yang tercatat dalam OPEN adalah e dengan cost terendah. 4.3.2.3.
Kembali ke step 4.3.2.
4.3.1. Kembali ke step 3.
Referensi Rich, Elaine, et.al., Artificial Intelligence 2nd Ed., International Ed., 1991.
Erick Pranata - State Space Search - 19/04/2013
6
