Metode Pencarian & Pelacakan (M4)

Blind Searching

Blind Searching merupakan pencarian buta, pencarian ini tidak memiliki informasi awal. Ciri-cirinya membangkitkan simpul berdasarkan urutan, kalau ada solusi, solusi akan ditemukan, hanya memilki informasi tentang node yang telah dibuka.

Ada beberapa teknik blind searching :

   - Breadth-first Search, yang sering disebut pencarian melebar. 

   Pencarian ini membuka note (titik) per levelnya. Sehingga penyelesaiannya menjadi seperti ini.

a    - Depth-First Search, yang sering disebut pencarian mendalam.

 Metode Pencarian Heuristik

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian (pencarian yang lebih simple). Namun kemungkinan juga dapat mengngorbankan kelengkapan (complateness).

Fungsi Heuristik

Heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

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:

1.Bangkitkan suatu kemungkinan solusi(membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).

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

3.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 lainnyayang mungkin.

Algoritma:

1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.

a) Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang : Cari operator yang belum digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.

b) Evaluasi keadaan baru tersebut :
– Jika keadaan baru merupakan tujuan, keluar
– Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang,

maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
– Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.

Sumber :

http://kuliahkusayang.blogspot.co.id/2010/04/teknik-searching.html

http://lily.staff.gunadarma.ac.id/Downloads/files/17559/Pertemuan2.pdf