Breadth-First Search (BFS)
Pencarian
dilakukan pada semua node dalam setiap level secara berurutan dari kiri ke
kanan.
Jika pada satu level belum ditemukan solusi, maka pencarian dilanjutkan pada
level
berikutnya. Demikian seterusnya sampai ditemukan solusi. Dengan strategi ini,
maka
dapat dijamin bahwa solusi yang ditemukan adalah yang paling baik (Optimal).
Tetapi
BFS harus menyimpan semua node yang pernah dibangkitkan. Hal ini harus
dilakukan
untuk penelusuran balik jika solusi sudah ditemukan. Gambar 2.4
mengilustrasikan
pembangkitan pohon BFS untuk masalah Water
Jug. Pembangkitan
suksesor
dari suatu node bergantung pada urutan dari Aturan Produksi yang dibuat
(lihat
gambar 2.2). Jika urutan dari aturan 4 ditukar dengan aturan 5, maka pohon
BFS
yang dibangkitkan juga akan berubah.
Pohon Breadth
First Search untuk Water
Jug Problem.
Depth-Limited Search (DLS)
Pencarian menggunakan DFS akan
berlanjut terus sampai kedalaman paling terakhir dari tree. Permasalahan yang
muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state
space. Hal ini bisa diatasi dengan menginisiasikan batas depth pada level
tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan
diperlakukan seolah-olah mereka tidak memiliki successor.
Mengatasi
kelemahan DFS (tidak complete) dengan membatasi kedalaman
maksimum
dari suatu jalur solusi. Tetapi harus diketahui atau ada batasan dari sistem
tentang level
maksimum. Jika batasan kedalaman terlalu kecil, DLS tidak complete.
•
depth-first search with depth limit L
•
nodes at depth L have no successors
