Pelacakan (searching)

Pelacakan (searching) adalah suatu strategi untuk melakukan pencarian dalam ruang problema secara selektif, yang memandu proses pencarian di sepanjang jalur yang memiliki kemungkinan sukses paling besar. Teknik ini dipakai pada situasi dimana hasil yang dieksak akan terlalu mahal atau tidak mungkin dilakukan, sehingga pemecahan yang diperoleh lebih bersifat cukup (sufficient).

1. Depth first Search

Pelacakan depth first search bermula dari node akar dan bergerak ke bawah untuk memeriksa dahulu semua anak atau turunan dari suatu cabang sebelum beralih ke cabang lain.

pelacakan dimulai dari 1, diteruskan ke 2, 3, 4, gagal. Pelacakan kembali ke atas ke node 3, tidak ada jalan alternative sehingga terpaksa dilakukan runut balik ke node 2, diteruskan ke 5, 6 gagal, runut balik ke 5, 7 gagal. Runut balik terus-menerus sampai tujuan tercapai.

2. Breadth First Search

Pelacakan Breadth First Search dilakukan terhadap semua cabang, baru diteruskan ke level yang lebih dalam.

Pelacakan Breadth First dilakukan menurut urutan 1, 2, 3, 4, 5, 6, 7. Pelacakan berhenti pada node 7 karena node 7 merupakan tujuan. pelacakan ini tidak memerlukan backtracking (runut balik).