Tugas Kecerdasan Buatan

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