Ringkasan Materi Pertemuan 4
Pencarian dalam Ruang Keadaan (State Space Search) adalah teknik dalam kecerdasan buatan untuk menemukan solusi dengan menelusuri berbagai kemungkinan keadaan (state) dari keadaan awal menuju keadaan tujuan (goal) melalui serangkaian tindakan atau operator. Ruang keadaan biasanya direpresentasikan dalam bentuk graf atau pohon, di mana node menunjukkan state dan edge menunjukkan operator. Strategi pencarian dibagi menjadi uninformed search, yaitu pencarian tanpa informasi tambahan tentang posisi goal, seperti Breadth-First Search (BFS) dan Depth-First Search (DFS). BFS menelusuri state secara melebar per level dan menjamin solusi terpendek, tetapi membutuhkan memori besar. Sebaliknya, DFS menelusuri state secara mendalam, lebih hemat memori, namun tidak selalu optimal dan dapat terjebak pada jalur yang panjang. Efisiensi algoritma pencarian dianalisis melalui kompleksitas waktu dan ruang untuk menentukan strategi yang paling sesuai dengan permasalahan.
Jawaban Pertanyaan Materi Pertemuan 4
A. Pemahaman Konsep Dasar
1. Apa yang dimaksud dengan ruang keadaan (state space) dalam AI?
Ruang keadaan adalah kumpulan seluruh kemungkinan kondisi (state) yang dapat terjadi dalam suatu masalah, dimulai dari keadaan awal hingga mencapai keadaan tujuan. Konsep ini digunakan untuk menelusuri solusi melalui penerapan operator secara sistematis.
2. Jelaskan elemen utama dalam model pencarian AI (state, operator, goal)!
- State: kondisi sistem pada suatu waktu (contoh: posisi puzzle).
- Operator: aksi yang mengubah satu state ke state lain (contoh: menggeser ubin).
- Goal: kondisi akhir yang ingin dicapai (contoh: puzzle tersusun rapi).
3. Representasi pada Puzzle 8:
- State awal: susunan awal angka pada papan.
- Operator: menggeser ubin ke kiri, kanan, atas, atau bawah.
- Goal: susunan angka yang benar sesuai tujuan.
4. Mengapa representasi graf atau pohon penting?
Karena membantu memvisualisasikan hubungan antar state dan memudahkan algoritma pencarian dalam menelusuri solusi.
5. Perbedaan operator dan path (jalur)?
Operator adalah satu aksi perpindahan state, sedangkan path adalah rangkaian state dari awal hingga goal.
B. Analisis Strategi Pencarian
6. Jelaskan langkah-langkah BFS dan struktur data yang digunakan!
BFS dimulai dari state awal, lalu menelusuri semua node pada level yang sama sebelum ke level berikutnya menggunakan queue (antrian) dengan prinsip FIFO.
7. Jelaskan langkah-langkah DFS dan perbedaannya dengan BFS!
DFS menelusuri satu cabang sedalam mungkin sebelum berpindah ke cabang lain menggunakan stack (tumpukan) dengan prinsip LIFO. Berbeda dengan BFS yang melebar, DFS bersifat mendalam.
8. Urutan node yang dikunjungi jika goal = F:
A
/ \
B C
/ \ \
D E F
- BFS: A → B → C → D → E → F
- DFS: A → B → D → E → C → F
9. Mengapa DFS lebih hemat memori dibanding BFS?
Karena DFS hanya menyimpan jalur aktif yang sedang ditelusuri, sedangkan BFS harus menyimpan semua node pada satu level sekaligus di dalam antrian.
10. Contoh situasi BFS lebih tepat digunakan dibanding DFS:
BFS lebih tepat digunakan ketika mencari jalur terpendek, seperti mencari rute tercepat pada peta atau pencarian level dalam game, karena BFS menjamin solusi optimal jika semua biaya sama.
