1.
Blind
Search
Blind
Searching adalah model pencarian
buta atau pencarian yang tidak memiliki informasi awal, model pencarian ini
memiliki tiga ciri – ciri utama yaitu:
-
Membangkitkan simpul
berdasarkan urutan
-
Kalau ada solusi maka
solusi akan ditemukan
-
Hanya memiliki
informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).
A. Pencarian
Melebar pertama (Breadth-First Search)
Semua node
pada level n akan dikunjungi terlebih dahulu sebelum level n+1. BFS (Breadth First Search) juga
merupakan salah satu algoritma penelusuran struktur graf / pohon seperti DFS,
namun bedanya BFS melakukan pencarian secara melebar atau per level pohon.
Simpul ditelusuri dari root kemudian menelusuri semua simpul pada
setiap level di bawahnya ( misalnya prioritas penelusuran dari kiri ke kanan ),
maka penelusuran dilakukan terus dari simpul paling kiri ke simpul anak – anak
tetangganya yang selevel. Jadi, untuk pohon biner :
Maka, urutan penelusurannya adalah : A – B – C – D – E
– F – G – H – I – J – K – L
Salah satu cara implementasi BFS
adalah dengan bantuan struktur data queue. Sama seperti stack pada DFS, queue
yang digunakan adalah queue yang isi elemennya adalah simpul pohon / tree.
Berikut ini adalah urutan algoritmanya :
- Masukkan simpul root ke dalam antrian
- Periksa antrian terdepan apakah memiliki anak simpul
- Jika ya, masukan semua anak simpul ke dalam antrian
- Hapus antrian terdepan
- Jika antrian kosong berhenti, tapi jika tidak kembali ke langkah dua
Untuk gambar pohon biner di atas, urutan langkah dan
kondisi queue pada setiap iterasinya adalah sebagai berikut :
Contoh diatas menggunakan prioritas
untuk memasukkan anak simpul dari sebelah kiri terlebih dahulu ke dalam queue.
Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak simpulnya yaitu
B dulu, baru C ke dalam stack. Untuk penelusurannya yang dilihat adalah bagian
yang berwarna biru, yaitu antrian terdepan yang setiap iterasinya memiliki
urutan A – B – C – D – E – F – G – H – I – J – K – L. Sama seperti DFS lagi
pada iterasi ke 13 itu kondisi antrian sudah kosong.
B. Pencarian
mendalam pertama (Depth-First Search)
Proses pencarian dilakukan pada semua anaknya
sebelum dilakukan pencarian ke node-node yang selevel. Pencarian ini dilakukan
pada suatu simpul dalam setiap level dari yang paling kiri. Jika pada level
yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada
simpul sebelah kanan dan simpul yang kiri dapat dihapus dari memori. Jika pada
level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada
level sebelumnya. Demikian seterusnya sampai ditemukan solusi.
Dalam implementasinya DFS dapat
diselesaikan dengan cara rekursif atau dengan bantuan struktur data stack. Kita
akan membahas dengan cara yang menggunakan stack. Stack yang digunakan adalah
stack yang isi elemennya adalah simpul pohon / tree. Bagaimana cara kerjanya ?
Berikut ini adalah urutan algoritmanya :
- Masukkan simpul root ke dalam tumpukan dengan push
- Ambil dan simpan isi elemen (berupa simpul pohon) dari tumpukan teratas
- Hapus isi stack teratas dengan prosedur pop
- Periksa apakah simpul pohon yang disimpan tadi memiliki anak simpul
- Jika ya, push semua anak simpul yang dibangkitkan ke dalam stack
- Jika tumpukan kosong berhenti, tapi jika tidak kembali ke langkah dua
Jadi, untuk gambar pohon biner di
atas urutan langkah dan kondisi stack-nya setiap iterasi adalah :
Maka, urutan
penelusurannya adalah : A – B – D – H – E – I – C – F – G – J – K – L
Contoh
diatas menggunakan prioritas untuk memasukkan anak simpul dari sebelah kanan
terlebih dahulu ke dalam stack. Sehingga, pada iterasi 2 elemen A dihapus lalu
memasukkan anak simpulnya yaitu C dulu, baru B ke dalam stack. Selain itu bisa
dilihat stack teratas (yang diwarna biru) pada tiap iterasi memiliki urutan A –
B – D – H – E – I – C – F – G – J – K – L. Oiya, pada iterasi ke 13 itu kondisi
stack sudah kosong karena ketika simpul J dibangkitkan tidak ada anak simpul
yang dimasukkan ke stack.
Sumber :
No comments:
Post a Comment