Bab 4 : Metode Pencarian dan Pelacakan 1

4.1 Metode Pencarian Buta ( Blind Search )

Yaitu tidak terdapatnya informasi awal yang digunakan dalam proses pencarian

4.1.1 Breadth First Search ( Pencarian Melebar Pertama )

Pada Breadth – First Search semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level 1 dari kiri ke kanan, kemudian berpindah ke level berikutnya dari kiri ke kanan hingga solusi ditemukan. Keuntungannya :

1. Tidak akan menemui jalan buntu, menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti solusi yang paling baik.

2. Jika ada 1 solusi, maka breadth – first search akan menemukannya

3. Jika ada lebih dari 1 solusi, maka solusi minimum akan ditemukan

Kerugiannya :

1. Membutuhkan memori yang banyak, karena harus menyimpan semua simpul yang pernah dibangkitkan dan hal ini harus dilakukan agar BFS dapat melakukan penelusuran simpul-simpul sampai di level bawah

2. Membutuhkan waktu yang cukup lama

Kesimpulan :

Teknik pencarian Breadth – First Search  ini :

1. Completeness : dimana teknik yang digunakan adanya solusi

2. Optimality : dimana teknik yang digunakan menemukan solusi yang terbaik saat adanya beberapa solusi berbeda Time complexity : waktu yang dibutuhkan cukup lama Space complexity : memori yang dibutuhkan juga banyak.

4.1.2 Depth First Search ( Pencarian Mendalam Pertama )

 Pada Breadth – First Search semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level 1 dari kiri ke kanan, kemudian berpindah ke level berikutnya dari kiri ke kanan hingga solusi ditemukan. Keuntungannya :

1. Tidak akan menemui jalan buntu, menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti solusi yang paling baik

2. Jika ada 1 solusi, maka breadth – first search akan menemukannya

3. Jika ada lebih dari 1 solusi, maka solusi minimum akan ditemukan

Kerugiannya :

1. Membutuhkan memori yang banyak, karena harus menyimpan semua simpul yang pernah dibangkitkan dan hal ini harus dilakukan agar BFS dapat melakukan penelusuran simpul-simpul sampai di level bawah

2. Membutuhkan waktu yang cukup lama

Kesimpulan :

Teknik pencarian Breadth – First Search  ini :

1. Completeness : dimana teknik yang digunakan adanya solusi

2. Optimality : dimana teknik yang digunakan menemukan solusi yang terbaik saat adanya beberapa solusi berbeda Time complexity : waktu yang dibutuhkan cukup lama Space complexity : memori yang dibutuhkan juga banyak.

4.2 Metode Pencarian Heuristik

Hampir sama dengan teknik Generate and Test dimana roses pengujian dilakukan dengan menggunakan fungsiheuristic. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baik nilai terkaan yang diambil terhadap kesalahan-kesalahan lainnya yang mungkin

4.2.1 Generate and Test

Pada Breadth – First Search semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level 1 dari kiri ke kanan, kemudian berpindah ke level berikutnya dari kiri ke kanan hingga solusi ditemukan. Keuntungannya :

1. Tidak akan menemui jalan buntu, menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti solusi yang paling baik

2. Jika ada 1 solusi, maka breadth – first search akan menemukanny

3. Jika ada lebih dari 1 solusi, maka solusi minimum akan ditemukan

Kerugiannya :

1. Membutuhkan memori yang banyak, karena harus menyimpan semua simpul yang pernah dibangkitkan dan hal ini harus dilakukan agar BFS dapat melakukan penelusuran simpul-simpul sampai di level bawah

2. Membutuhkan waktu yang cukup lama

Kesimpulan :

Teknik pencarian Breadth – First Search  ini :

1. Completeness : dimana teknik yang digunakan adanya solusi

2. Optimality : dimana teknik yang digunakan menemukan solusi yang terbaik saat adanya beberapa solusi berbeda Time complexity : waktu yang dibutuhkan cukup lama Space complexity : memori yang dibutuhkan juga banyak.

4.2.2 Hill Climbing

Hampir sama dengan teknik Generate and Test dimana roses pengujian dilakukan dengan menggunakan fungsiheuristic. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baik nilai terkaan yang diambil terhadap kesalahan-kesalahan lainnya yang mungkin. Teknik-teknik pada Hill Climbing :

1. Teknik simple hill climbing

Algoritma akan berhenti kalau mencapai nilai optimum lokal. Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi. Tidak diijinkan untuk melihat satupun langkah selanjutnya.

2.     2. Teknik steepest – ascent hill climbing

Hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari paling kiri. Gerakan selanjutnya dicari berdasarkan nilaiheuristic terbaik.

 Sumber :

http://yoosinhay.blogspot.co.id/2011/03/teknik-pencarian-perancangan.html