RINGKASAN MATERI
1. Pencarian dalam Ruang Keadaan (State Space Search)
State Space Search adalah pendekatan AI untuk menyelesaikan masalah dengan menelusuri berbagai kemungkinan keadaan (state) hingga menemukan solusi.
2. Konsep Dasar
State: kondisi sistem pada suatu waktu
Initial State: keadaan awal
Goal State: keadaan tujuan yang ingin dicapai
Operator / Action: tindakan yang mengubah state
Path: urutan state dari awal ke tujuan
Search Space: semua kemungkinan state yang dapat dicapai
3. Hubungan State, Operator, dan Goal
Proses pencarian bergerak dari initial state → state antara → goal state dengan menerapkan operator secara bertahap.
4. Goal Test
Digunakan untuk mengecek apakah state saat ini sudah memenuhi kondisi tujuan (true/false).
5. Representasi Ruang Keadaan
Ruang keadaan dapat direpresentasikan sebagai:
Graf (graph) atau
Pohon (tree)
Node mewakili state, edge mewakili operator.
6. Contoh Kasus
Puzzle 8: setiap konfigurasi ubin adalah state
Rute kota: state = posisi kota, operator = berpindah kota
Kehidupan nyata: menyalakan lampu, menyusun jadwal, memasak resep
7. Elemen Pencarian Formal
Initial state
Action
Transition model
Goal test
Path cost
Solution (jalur terbaik ke goal)
JAWABAN SOAL
1. Ruang keadaan (state space)
Ruang keadaan adalah kumpulan semua kondisi (state) yang mungkin dari suatu masalah. Konsep ini digunakan dengan menelusuri perpindahan dari state awal ke state tujuan melalui serangkaian aksi untuk menemukan solusi.
2. Tiga elemen utama pencarian AI
State: kondisi sistem (contoh: posisi pion pada puzzle)
Operator: aksi yang mengubah state (contoh: geser ubin)
Goal: kondisi akhir yang diinginkan (contoh: puzzle tersusun rapi)
3. Puzzle 8
State awal: konfigurasi awal ubin
Operator: geser ubin ke atas, bawah, kiri, kanan
Goal: konfigurasi ubin sesuai target
4. Pentingnya representasi pohon/graf
Karena memudahkan visualisasi, penelusuran, dan penerapan algoritma pencarian secara sistematis.
5. Perbedaan operator dan path
Operator: satu aksi perpindahan state
Path (jalur): rangkaian operator dari state awal ke goal
B. Analisis Strategi Pencarian
6. Breadth-First Search (BFS)
Menelusuri node per level
Menggunakan Queue (FIFO)
Menjamin solusi terpendek
7. Depth-First Search (DFS)
Menelusuri sedalam mungkin
Menggunakan Stack (LIFO)
Lebih hemat memori dibanding BFS
8. Urutan kunjungan node (goal = F)
Struktur:
A
├─ B → D, E
└─ C → F
BFS: A → B → C → D → E → F
DFS: A → B → D → E → C → F
9. Mengapa DFS lebih hemat memori
Karena DFS hanya menyimpan satu jalur aktif, sedangkan BFS menyimpan semua node pada satu level sekaligus.
10. Contoh BFS lebih tepat daripada DFS
Pencarian rute terpendek (misalnya GPS, maze)
Karena BFS menjamin solusi paling pendek, sedangkan DFS bisa menemukan solusi lebih panjang terlebih dulu.
