Teknik Pencarian / Penelusuran Kecerdasan Buatan

Pada umumnya manusia mempertimbangkan sejumlah alternatif strategi dalam menyelesaikan suatu problema. Dalam permainan catur misalnya, seorang pemain mempertimbangkan sejumlah kemungkinan tentang langkah-langkah berikutnya, memilih yang terbaik menurut kriteria tertentu seperti kemungkinan respon lawannya. Aspek tingkahlaku cerdas yang mendasari teknik penyelesaian problema seperti dalam permainan catur tersebut dinamakan proses pencarian ruang keadaan (space state search). 

Exhaustive search  –  adalah proses pencarian terhadap seluruh ruang keadaan serangakaian langkah yang paling dimungkinkan untuk menghasilkan kemenangan. Walaupun metode ini dapat diterapkan pada setiap ruang keadaan, namum ukuran ruang keadaan yang sangat besar membuat pendekatan ini secara praktis tidak dimungkinkan (dalam permainan catur terdapat 10120keadaan ) Bila kasus ini diimplementasikan ke dalam sistem komputer, maka akan membutuhkan memori yang sangat besar, dan waktu pencarian yang sangat lama. Dengan kata lain metode exhaustive search ini tidak efisien dan tidak efektif, sehingga tidak praktis untuk diimplementasikan. 

Untuk mengatasi kendala tersebut diatas, ada beberapa cara yang dapat dilakukan, diantaranya: pertama teknik pencarian parsial (Blind Search) dan yang kedua teknik pencarian heuristic (Heuristik Search). 

Pencarian Parsial (Blind Search)

PENCARIAN MELEBAR PERTAMA (Breadth-First Search)

Pada metode 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 ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya, demikian pula dari kiri ke kanan hingga ditemukannya solusi (lihat gambar di bawah ini ).

Keuntungan : 

• Tidak akan menemui jalan buntu 
• Jika ada satu solusi, maka breadth-first search akan menemukannya. Dan, jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan. 

Kelemahan : 

• Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon 
• Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1). 

PENCARIAN KEDALAM PERTAMA (Depth-First Search) 

Pada Depth-First Search, proses pencarian akan dilakukanpada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya solusi (lihat gambar di  bawah). 

Keuntungan : 

• Membutuhkan memori yang relative keci l, 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. 

Kelemahan : 

• Memungkinkan tidak ditemukannya tujuan yang diharapakan 
• Hanya akan menemukan 1 solusi pada setiap pencarian

Pencarian Heuristik (Heuristic Search)

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: 

1. Generate and Test. 
2. HillClimbing. 
3. Best First Search. 
4. Alpha  Beta  Prunning,Means-End-Anlysis,Constraint Satisfaction, Simulated Anealing, dll

lebih lengkap tentang Pencarian Heuristik (Heuristic Search)