A. Pemahaman Konsep Dasar
-
Ruang keadaan adalah semua kemungkinan keadaan yang dapat dibentuk dari keadaan awal melalui operator. Digunakan untuk menelusuri jalur hingga menemukan goal.
-
Elemen pencarian:
-
State: kondisi saat ini (contoh: berada di Kota A).
-
Operator: tindakan yang mengubah state (contoh: pergi ke Kota B).
-
Goal: kondisi akhir yang dicapai (contoh: tiba di Kota D).
-
Puzzle 8:
(a) State awal: susunan ubin pertama.
(b) Operator: geser ubin kosong.
(c) Goal: susunan terurut 1–8. -
Pohon/graf penting karena memudahkan melihat semua jalur pencarian dan menemukan solusi secara sistematis.
-
Operator adalah aksi pengubah state, sedangkan path adalah rangkaian state hasil penerapan operator.
B. Analisis Strategi Pencarian
-
BFS: menelusuri level demi level menggunakan queue. Keluarkan node, periksa, lalu tambahkan semua anaknya.
-
DFS: menelusuri sedalam mungkin menggunakan stack. Ambil node paling atas dan telusuri cabang sampai mentok. Berbeda dari BFS yang melebar.
-
Urutan kunjungan:
a. BFS: A → B → C → D → E → F
b. DFS: A → B → D → E → C → F -
DFS lebih hemat memori karena hanya menyimpan jalur aktif, sedangkan BFS menyimpan semua node di satu level.
-
BFS lebih tepat digunakan jika membutuhkan solusi terpendek, misalnya mencari rute perjalanan paling singkat.
