METODE
PENCARIAN DAN PELACAKAN
Pelacakan
adalah teknik untuk pencarian. Didalam pencarian ada dua kemungkinan hasil yang
didapat yaitu menemukan dan tidak menemukan. Sehingga pencarian merupakan
teknik yang penting dalam AI. Hal penting dalam menentukan keberhasilan sistem
berdasarkan kecerdasan adalah kesuksesan dalam pencarian dan pencocokan.
Pencarian adalah suatu proses mencari solusi dari suatu permasalahan melalui
sekumpulan kemungkinan ruang keadaan (state place). Ruang keadaan merupakan
suatu ruang yang berisi semua keadaan yang mungkin.
Untuk
mengukur performansi metode pencarian, terdapat empat kriteria yang dapat
digunakan :
- Completeness (Kelengkapan) : apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada ?
- Time compexity (Kekompleksan waktu) : berapa lama waktu yang diperlukan ?
- Space complexity (Kekompleksan ruang) : berapa banyak memori yang di perlukan ?
- Optimality (Optimal) : apakah metode tersebut menjamin menemukan solusi yang terbaik jika beberapa solusi berbeda ?
Ada beberapa teknik pelacakan :
- Pencarian Buta (Blind Search)
- Pencarian Melebar Pertama (Breadth-First Search)
BREADTH-FIRST SEARCH (BFS) sebuah algoritma
pencarian graf yang dimulai dari node pangkal dan menjelajahi semua node yang
berdekatan.dan untuk setiap node yang berdekatan, bfs menjelajahi node-node
yang tidak terlihat sebelumnya (unexplored) dan seterusnya
BFS adalah sebuah metode pencarian yang bertujuan untuk memperluas dan memeriksa semua node dari sebuah graf atau kombinasi dari urutan dengan menggunakan semua solusi secara sistematis. dengan kata lain, bfs mencari ke seluruh graf atau urutan secara mendalam tanpa mempertimbangkan tujuannya (goal) sampai tujuan itu tercapai. bfs tidak menggunakan algoritma heuristis.
BFS adalah sebuah metode pencarian yang bertujuan untuk memperluas dan memeriksa semua node dari sebuah graf atau kombinasi dari urutan dengan menggunakan semua solusi secara sistematis. dengan kata lain, bfs mencari ke seluruh graf atau urutan secara mendalam tanpa mempertimbangkan tujuannya (goal) sampai tujuan itu tercapai. bfs tidak menggunakan algoritma heuristis.
Kelebihan
BFS
- 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
- 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
Kekurangan
BFS
Dan kekurangan dari metode BFS ini yaitu:
- Membutuhkan memori yang cukup banyak.
- Membutuhkan waktu yang cukup lama.
Dan kekurangan dari metode BFS ini yaitu:
- Membutuhkan memori yang cukup banyak.
- Membutuhkan waktu yang cukup lama.
- Pencarian Mendalam Pertama (Depth-First Search)
Pencarian mendalam pertama merupakan teknik penelusuran data
pada node-node secara vertikal dan sudah terdefinisikan secara mendalam.
Proses pemeriksaan akan bergerak turun jika node
yang diperiksa saat ini tidak sesuai dengan tujuan. Node tidak akan dikembangkan ke samping walaupun node masih mempunyai beberapa node anak yang dapat dikembangkan. Node anak baru dikembangkan lagi setelah
selesainya pencarian mendalam terhadap node
anak yang sebelumnya telah dikembangkan. Proses ini diulangi terus hingga
didapatkan solusi. Perhatikan gambar 2.8 sebagai prosedur pencarian mendalam
pertama.
Keuntungan dari metode ini adalah
membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan
yang aktif saja yang disimpan. Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih
banyak lagi dalam ruang keadaan.
Sedangkan kelemahan dari metode ini adalah memungkinkan
tidak ditemukannya tujuan yang diharapkan dan hanya akan mendapatkan 1 solusi
pada setiap pencarian.
- Pencarian Terbimbing/Heuristik (Heuristic Search)
- Pembangkitan dan Pengujian (Generate And Test)
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.
- Pendakian Bukit (Hill Climbing)
Metode
ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses
pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan
berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa
fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang
diambil terhadap keadaan-keadaan lainnya yang mungkin.
Referensi
:
Mata Kuliah : Pengantar Teknologi Sistem Cerdas