METODE PENCARIAN DAN PELACAKAN

METODE PENCARIAN DAN PELACAKAN

( Annisa Imania Putri 11114374 , Ariefah Nur Aisyah 11114575 , Syarifa Isninawati 1A114607 )

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)

1. 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.

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

Kekurangan BFS

Dan kekurangan dari metode BFS ini yaitu:
- Membutuhkan memori yang cukup banyak.
- Membutuhkan waktu yang cukup lama.

2. 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)

1. 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.

2. 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 :

https://yanneevelynip.wordpress.com/2013/10/20/metode-pencarian-dan-pelacakan-kecerdasan-buatan/

http://muhamadmasruri.blogspot.co.id/2013/04/pencarian-melebar-pertama-breadth-first.html

http://duniainformatikaindonesia.blogspot.co.id/2013/03/pencarian-mendalam-pertama-depth-first.html

http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html

Mata Kuliah : Pengantar Teknologi Sistem Cerdas