Pertemuan 2

Masalah, Ruang Keadaan dan Pencarian

• Sistem AI

Dalam Sistem AI kita memiliki algoritma sebagai berikut

• Masalah

Untuk membangun sistem yang mampu menyelesaikan masalah, perlu di pertimbangkan 4 hal:

1.Mendefinisikan masalah dengan tepat

• Spesifikasi yang tepat

• Solusi yang diharapkan

2. Menganalisis masalah serta mencapai beberapa teknik penyelesaian masalah yang sesuai.
3. Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah.
4. Memilih teknik penyelesaian masalah yang terbaik.

• Masalah sebagai ruang keadaan

1. Misalkan permasalahan yang dihadapi adalah permainan catur.
2. Maka harus ditentukan

• Posisi awal pada papan catur
• Aturan-aturan untuk melakukan gerakan secara legal
• Tujuan(goal)

• Posisi awal pada papan catur

posisi awal pada papan catur selalu sama, yaitu seperti pada gambar berikut:

• Aturan-aturan untuk melakukan gerakan secara legal

1. Aturan-aturan sangat berguna untuk menetukan gerakan secara bidak
2. Untuk mempermudah

• Huruf (a,b,c,d,e,f,g) horizontal
• Angka (1,2,3,4,5,6,7,8) vertikal

3. contoh singkat coding dengan menggunakan bahasa pemrograman PASCAL

• Bidak (e,2) ke (e,4)

IF bidak putih pada kotak (e,2),
AND kotak (e,3) kosong,
AND kotak (e,4) kosong
Then gerakan bidak dari (e,2) ke (e,4)

• Contoh gambarnya sebagai berikut:

• Tujuan (goal)

1. Tujuan yang ingin dicapai adalah posisi pada papan catur yang menunjukan kemenangan
seseorang terhadap lawannya.
2. Ditandai dengan posisi raja yang sudah tidak dapat bergerak lagi.

• Ruang Keadaan (State Space)

1. Suatu ruang yang berisi semua keadaan yang mungkin
2. Sehingga secara umum, untuk menjelaskan masalah dengan baik, kita harus:

• Mendefinisikan suatu ruang keadaan
• Menetapkan satu atau lebih keadaan awal
• Menetapkan satu atau lebih tujuan
• Menetapkan kumpulan aturan

3. Ada beberapa cara untuk mempresentasikan ruang keadaan

1. 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

> Contoh gambarnya sebagai berikut:











• Contoh lintasan dari M ke T (lintasan yang sampai ke T )

– M-A-B-C-E-T, M-A-B-C-E-H-T, M-D-C-E-T, M-D-C-E-H-T

• Yang tidak sampai ke T
– M-A-B-C-E-F-G, M-A-B-C-E-I-J, M-D-C-E-F-G, M-D-C-E-I-J, M-D-I-J

2. Pohon Pelacakan

• Struktur pohon digunakan untuk menggambarkan keadaan secara hirarkis
• Terdiri dari beberapa node, level 0 disebut akar atau keadaan awal
• Node akar : menunjukkan keadaan awal & memiliki beberapa percabangan yang terdiri atas beberapa node yg disebut ’anak’.
• Node-node yg tidak memiliki anak disebut ’daun’ menunjukkan akhir dari suatu pencarian, dapat berupa tujuan yang diharapkan (goal) atau jalan buntu (dead end).

> Contoh Gambarnya sebagai beriku













> Contoh Permainan Online sebagai berikut:









> Keterangan yang ada pada gambar:

• Petani, Sayur, Kambing dan Serigala
• Seorang petani akan menyeberangkan seekor kambing, seekor serigala, dan sayur- sayuran dengan sebuah boat yang melalui sungai.
• Boat hanya bisa memuat petani dan satu penumpang yang lain (kambing, serigala atau
  sayur-sayuran).
• Jika ditinggalkan oleh petani tersebut, maka sayur-sayuran akan dimakan oleh kambing, dan kambing akan dimakan oleh serigala.

> Penyelesaian masalah secara umum

• Mendefinisikan suatu ruang keadaan.
• Menetapkan satu atau lebih keadaan awal.
• Menetapkan satu atau lebih tujuan.
• Menetapkan kumpulan aturan.

> Penyelesaian dalam permainan game online seperti gambar diatas:

1. Identifikasi ruang keadaan

• Permasalahan ini dapat dilambangkan dengan (JumlahKambing, JumlahSerigala, Jumlah Sayuran, JumlahBoat).
• Sebagai contoh: Daerah asal (0,1,1,1) berarti pada daerah asal tidak ada kambing, ada erigala, ada sayuran, dan ada boat.

2. 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)

3. Aturan-aturan dalam game online diatas













4. Cara menyelesaikannya sebagai berikut:

• Metode Pencarian dan Pelacakan

1. Hal penting dalam menentukan keberhasilan sistem cerdas adalah kesuksesan dalam
pencarian.
2. Pencarian = suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan
kemungkinan ruang keadaan (state space).
3. Ruang keadaan = merupakan suatu ruang yang berisi semua keadaan yang mungkin.
4. 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?

5. 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)

1. Semua node pada level n akan dikunjungi terlebih dahulu sebelum level n+1
2. Mulai dari akar terus ke level 1 dari kiri ke kanan
3. Kemudian ke level selanjutnya hingga solusi ditemukan

> Contoh gambarnya sebagai berikut:















> Keuntungan dan kelemahan dari Pencarian diatas adalah:

• Keuntungan
  

1. Tidak akan menemui jalan buntu
2. Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik.
3. Jika ada satu solusi maka bread-first search akan menemukannya

• Kelemahan

1. Membutuhkan memori yang cukup banyak.
2. Membutuhkan waktu yang cukup lama.

• Pencarian mendalam pertama (Depth-First Search)

1. Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke
node-node yang selevel
> Contoh gambarnya sebagai berikut














> Keuntungan dan Kelemahan dari Pencarian diatas adalah:

• Keuntungan

1. Memori yang relatif kecil
2. Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi

• Kelemahan
  

1. Memungkinkan tidak ditemukannya tujuan yang diharapkan
2. Hanya akan mendapatkan 1 solusi pada setiap pencarian

Lebih lengkap semua silakan download di bagian "Download Materi"