Part 2

MASALAH, RUANG KEADAAN, PENCARIAN

Pembahasan kaping setunggal membahas suatu problem/Masalah
yaitu:
Dalam pembangunan sistem masalah yang perlu kita pertimbangkan ada 4 hal, yaitu:
* Penjabaran dan pendefinisian masalah dengan tepat:
• Spesifikasi yang tepat mengenai keadaan awal
• Solusi yang diharapkan
*Penganalisisan masalah dengan tepat
*teknik penyelesaian masalah yang sesuai
– Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah
– Memilih teknik penyelesaian masalah yang terbaik

Masalah Sebagai Ruang Keadaan
• Misalkan permasalahan yang dihadapi adalah Permainan Catur
• Maka harus ditentukan :
– Posisi awal pada papan catur
– Aturan-aturan untuk melakukan gerakan secara legal
– Tujuan (goal)

Posisi awal pada papan catur
• Posisi awal selalu sama

Aturan-aturan untuk melakukan gerakan secara legal
• Aturan-aturan sangat berguna untuk menentukan gerakan suatu bidak
• Untuk mempermudah
– huruf (a,b,c,d,e,f,g,h) horizontal
– angka (1,2,3,4,5,6,7,8) vertikal
• Contoh
– bidak (e,2) ke (e,4)
IF Bidak putih pada Kotak(e,2),
AND Kotak(e,3) Kosong,
AND Kotak(e,4) Kosong
Then Gerakkan bidak dari (e,2) ke (e,4)
Aturan-aturan untuk melakukan gerakan secara legal
• Aturan-aturan sangat berguna untuk menentukan gerakan suatu bidak
• Untuk mempermudah
– huruf (a,b,c,d,e,f,g,h) horizontal
– angka (1,2,3,4,5,6,7,8) vertikal
• Contoh
– bidak (e,2) ke (e,4)
IF Bidak putih pada Kotak(e,2),
AND Kotak(e,3) Kosong,
AND Kotak(e,4) Kosong
Then Gerakkan bidak dari (e,2) ke (e,4)

Aturan-aturan untuk melakukan gerakan secara legal

Tujuan (goal)
• Tujuan yang ingin dicapai adalah posisi pada papan catur yang menunjukkan kemenangan seseorang  terhadap lawannya
• Ditandai dengan posisi Raja yang sudah tidak dapat bergerak lagi
Tujuan (goal)
• Tujuan yang ingin dicapai adalah posisi pada papan catur yang menunjukkan kemenangan seseorang terhadap lawannya
• Ditandai dengan posisi Raja yang sudah tidak dapat bergerak lagi

Ruang Keadaan(State Space)
• Suatu ruang yang berisi semua keadaan yang mungkin
• Sehingga secara umum, untuk mendeskripsikan masalah dengan baik, harus:
– Mendefinisikan suatu ruang keadaan
– Menetapkan satu atau lebih keadaan awal
– Menetapkan satu atau lebih tujuan
– Menetapkan kupulan aturan
• Ada beberapa cara untuk merepresentasikan
Ruang Keadaan
Ruang Keadaan(State Space)
• Suatu ruang yang berisi semua keadaan yang mungkin
• Sehingga secara umum, untuk mendeskripsikan masalah dengan baik, harus:
– Mendefinisikan suatu ruang keadaan
– Menetapkan satu atau lebih keadaan awal
– Menetapkan satu atau lebih tujuan
– Menetapkan kupulan aturan
• Ada beberapa cara untuk merepresentasikan
Ruang Keadaan

Graph Keadaan
• Terdiri dari node-node yang menunjukkan keadaan yaitu keadaan awal dan keadaan
baru yang akan dicapai dengan menggunakan operator
• Node-node saling dihubungkan dengan menggunakan arc (busur) yang diberi panah
untuk menunjukkan arah
Graph Keadaan
• Terdiri dari node-node yang menunjukkan keadaan yaitu keadaan awal dan keadaan
baru yang akan dicapai dengan menggunakan operator
• Node-node saling dihubungkan dengan menggunakan arc (busur) yang diberi panah
untuk menunjukkan arah

Penyelesaian masalah secara umum
• Mendefinisikan suatu ruang keadaan;
• Menetapkan satu atau lebih keadaan awal;
• Menetapkan satu atau lebih tujuan;
• Menetapkan kumpulan aturan.

Penyelesaian
• Identifikasi ruang keadaan
– Permasalahan ini dapat dilambangkan dengan
(JumlahKambing, JumlahSerigala, JumlahSayuran,
JumlahBoat).
– Sebagai contoh: Daerah asal (0,1,1,1) berarti pada daerah
asal tidak ada kambing, ada serigala, ada sayuran, dan ada
boat.
• Keadaan Awal
– Daerah asal: (1,1,1,1)
– Daerah seberang: (0,0,0,0)
– Tujuan
– Daerah asal: (0,0,0,0)
– Daerah seberang: (1,1,1,1)
Penyelesaian
• Identifikasi ruang keadaan
– Permasalahan ini dapat dilambangkan dengan
(JumlahKambing, JumlahSerigala, JumlahSayuran,
JumlahBoat).
– Sebagai contoh: Daerah asal (0,1,1,1) berarti pada daerah
asal tidak ada kambing, ada serigala, ada sayuran, dan ada
boat.
• Keadaan Awal
– Daerah asal: (1,1,1,1)
– Daerah seberang: (0,0,0,0)
– Tujuan
– Daerah asal: (0,0,0,0)
– Daerah seberang: (1,1,1,1)

Aturan-aturan


Aturan
ke-
Aturan
1. Kambing menyeberang
2. Sayuran menyeberang
3. Serigala menyeberang
4. Kambing kembali
5. Sayuran kembali
6. Serigala kembali
7. Boat kembali

Penyelesaian


Daerah
Seberang
Daerah Asal
Aturan yang
dipakai
(1,1,1,1) (0,0,0,0) 1
(0,1,1,0) (1,0,0,1) 7
(0,1,1,1) (1,0,0,0) 3
(0,0,1,0) (1,1,0,1) 4
(1,0,1,1) (0,1,0,0) 2
(1,0,0,0) (0,1,1,1) 7
(1,0,0,1) (0,1,1,0) 1
(0,0,0,0) (1,1,1,1) solusi


Metode Pencarian dan
Pelacakan



• Hal penting dalam menentukan
keberhasilan sistem cerdas adalah
kesuksesan dalam pencarian.
• Pencarian = suatu proses mencari solusi
dari suatu permasalahan melalui
sekumpulan kemungkinan ruang keadaan
(state space).
• Ruang keadaan = merupakan suatu ruang
yang berisi semua keadaan yang mungkin.

Metode Pencarian dan
Pelacakan



•
Untuk mengukur perfomansi metode pencarian,
terdapat empat kriteria yang dapat digunakan :
– Completeness : apakah metode tersebut menjamin
penemuan solusi jika solusinya memang ada?
– Time complexity : berapa lama waktu yang
diperlukan?
– Space complexity : berapa banyak memori yang
diperlukan
– Optimality : apakah metode tersebut menjamin
menemukan solusi yang terbaik jika terdapat
beberapa solusi berbeda?

Metode Pencarian dan
Pelacakan



• Dua teknik pencarian dan pelacakan
– Pencarian buta (blind search)
• Pencarian melebar pertama (Breadth – First
Search)
• Pencarian mendalam pertama (Depth – First
Search)
– Pencarian terbimbing (heuristic search)
• Pendakian Bukit (Hill Climbing)
• Pencarian Terbaik Pertama (Best First Search)

Pencarian Melebar Pertama
(Breadth-First Search)
• Semua node pada level n akan dikunjungi
terlebih dahulu sebelum level n+1
• Mulai dari akar terus ke level 1 dari kiri ke
kanan
• Kemudian ke level selanjutnya hingga solusi
ditemukan
Pencarian Melebar Pertama
(Breadth-First Search)
• Semua node pada level n akan dikunjungi
terlebih dahulu sebelum level n+1
• Mulai dari akar terus ke level 1 dari kiri ke
kanan
• Kemudian ke level selanjutnya hingga solusi
ditemukan

Pencarian Melebar Pertama
(Breadth-First Search)
• Keuntungan
– Tidak akan menemui jalan buntu
– Menjamin ditemukannya solusi (jika solusinya
memang ada) dan solusi yang ditemukan pasti
yang paling baik
– Jika ada satu solusi maka bread-first search akan
menemukannya
• Kelemahannya
– Membutuhkan memori yang cukup banyak
– Membutuhkan waktu yang cukup lama
Pencarian Melebar Pertama
(Breadth-First Search)
• Keuntungan
– Tidak akan menemui jalan buntu
– Menjamin ditemukannya solusi (jika solusinya
memang ada) dan solusi yang ditemukan pasti
yang paling baik
– Jika ada satu solusi maka bread-first search akan
menemukannya
• Kelemahannya
– Membutuhkan memori yang cukup banyak
– Membutuhkan waktu yang cukup lama

Pencarian mendalam pertama
(Depth-First Search)
• Proses pencarian dilakukan pada semua
anaknya sebelum dilakukan pencarian ke
node-node yang selevel
• Keuntungan
– Memori yang relatif kecil
– Secara kebetulan, akan menemukan
solusi tanpa harus menguji lebih banyak
lagi
Pencarian mendalam pertama
(Depth-First Search)
• Proses pencarian dilakukan pada semua
anaknya sebelum dilakukan pencarian ke
node-node yang selevel
• Keuntungan
– Memori yang relatif kecil
– Secara kebetulan, akan menemukan
solusi tanpa harus menguji lebih banyak
lagi

Pencarian buta
(blind search)
• Kekurangan
– Memungkinkan tidak ditemukannya
tujuan yang diharapkan
– Hanya akan mendapatkan 1 solusi pada
setiap pencarian
Pencarian buta
(blind search)
• Kekurangan
– Memungkinkan tidak ditemukannya
tujuan yang diharapkan
– Hanya akan mendapatkan 1 solusi pada
setiap pencarian