Metode pencarian Buta (Blind Search) dan metode pencarian Heuristik.
1.Metode Pencarian Buta(Blind Search).
merupakan pencarian asal.
Jika solusi sudah ditemukan, maka pencarian akan dihentikan. Jika dibuat skemanya, pencarian buta hanya mengenal 3 bagian yaitu [masalah]-[pencarian]-[solusi].
Blind search tidak mempunyai atribut atau informasi tambahan. Algoritma yang
termasuk Blind search yaitu:
A.Pencarian Melebar Pertama
(Breadth-First Search)
Pada metode pencarian
ini, 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 ke-1 dari kiri ke kanan, Kemudian ke level selanjutnya hingga
solusi ditemukan
contoh:
• Keuntungan
– Tidak akan
menemui jalan buntu
– Menjamin ditemukannya
solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti
yang paling baik
– Jika ada satu solusi maka
bread-first search akan menemukannya
• Kelemahannya
– Membutuhkan memori yang
cukup banyak
– Membutuhkan waktu yang
cukup lama
B.Pencarian mendalam
pertama (Depth-First Search)
Proses pencarian
dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang
selevel
contoh:
• Keuntungan
– Memori yang relatif kecil
– Secara kebetulan, akan
menemukan solusi tanpa harus menguji lebih banyak lagi
2.metode pencarian Heuristik.
Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaankeadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Jenis-jenis Heuristic Searching:
A.PEMBANGKITAN dan PENGUJIAN (Generate
and Test).
Pada metode pencarian
ini, 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 ke-1 dari kiri ke kanan, Kemudian ke level selanjutnya hingga
solusi ditemukan
contoh:
• Keuntungan
– Tidak akan
menemui jalan buntu
– Menjamin ditemukannya
solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti
yang paling baik
– Jika ada satu solusi maka
bread-first search akan menemukannya
• Kelemahannya
– Membutuhkan memori yang
cukup banyak
– Membutuhkan waktu yang
cukup lama
B.Pencarian mendalam
pertama (Depth-First Search)
Proses pencarian
dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang
selevel
contoh:
• Keuntungan
– Memori yang relatif kecil
– Secara kebetulan, akan
menemukan solusi tanpa harus menguji lebih banyak lagi
Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaankeadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Jenis-jenis Heuristic Searching:
Metode ini merupakan penggabungan antara depth-first search
dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada
suatu keadaan awal. Algoritma:
- Bangkitkan suatu kemungkinan solusi
(membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan
awal).
- Uji untuk melihat apakah node tersebut
benar-benar merupakan solusinya dengan cara membandingkan node terebut
atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan
yang diharapkan.
- Jika solusi ditemukan, keluar. Jika
tidak, ulangi kembali langkah pertama.
Contoh:
“Travelling Salesman Problem (TSP)” Seorang salesman ingin
mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin
mengetahui ruter terpendek dimana setaip kota hanya boleh dikkunjungi tepat
1 kal i. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti
gambar di bawah ini:
Penyelesaian dengan metode Generate and Test
Penyelesaian dengan metode Generate and Test






