1. Ruang keadaan adalah kumpulan semua kemungkinan kondisi sistem yang terbentuk dari keadaan awal melalui penerapan operator. Digunakan untuk menemukan urutan tindakan yang membawa dari awal ke tujuan dengan mengeksplorasi kemungkinan tersebut.
2. Tiga elemen utama:
- State: Kondisi sistem pada waktu tertentu (contoh: posisi saat ini di Kota A).
- Operator: Tindakan yang mengubah state (contoh: berpindah dari Kota A ke B).
- Goal: Kondisi akhir yang ingin dicapai (contoh: mencapai Kota D).
3. Puzzle 8:
- (a) State awal: Konfigurasi ubin sembarang (misal [1 2 3; 4 _ 5; 7 8 6]).
- (b) Operator: Geser ubin ke atas, bawah, kiri, kanan (jika memungkinkan).
- (c) State tujuan: Konfigurasi ubin terurut ([1 2 3; 4 5 6; 7 8 _]).
4. Representasi pohon/graf penting karena memvisualisasikan hubungan antar state, di mana node = state dan edge = operator. Memudahkan pelacakan jalur dan eksplorasi sistematis ke tujuan.
5. Perbedaan: Operator adalah satu langkah yang mengubah state; Path adalah urutan berturut-turut dari operator/state yang menghubungkan awal ke tujuan.
6. Langkah BFS:
7. Mulai dari node awal, masukkan ke antrian.
8. Selama antrian tidak kosong: keluarkan node, cek apakah goal. Jika tidak, masukkan semua anaknya ke antrian.
Struktur data: Queue (FIFO).
9. Langkah DFS:
10. Mulai dari node awal, masukkan ke tumpukan.
11. Selama tumpukan tidak kosong: ambil node paling atas, cek apakah goal. Jika tidak, masukkan semua anaknya ke tumpukan.
Perbedaan dengan BFS: BFS jelajahi level demi level; DFS jelajahi cabang sedalam mungkin terlebih dahulu. Struktur data: Stack (LIFO).
12. Urutan kunjungan (goal = F):
- a. BFS: A → B → C → D → E → F.
- b. DFS: A → B → D → E → C → F (atau urutan lain tergantung urutan memasukkan anak, misal A→C→F jika C dimasukkan lebih dulu).
9. DFS lebih hemat memori karena menggunakan stack yang hanya menyimpan jalur aktif saat ini dan sebagian kecil node lain. Sedangkan BFS menggunakan queue yang harus menyimpan semua node pada level saat ini, sehingga membutuhkan lebih banyak ruang.
10. Contoh situasi BFS lebih tepat: Mencari rute terpendek dari rumah ke sekolah. Alasan: BFS menjamin menemukan solusi terpendek (level demi level), sedangkan DFS bisa menemukan jalur yang lebih panjang terlebih dahulu.
