Softskill

METODE PENCARIAN DAN PELACAKAN HEURISTIK

(Anggi Yolanda Faradila 11114234, Inne Meilyanti 1D114056, Wahyuni 1C114167)

A.   Metode Pencarian Buta

Pada metode pencarian buta (blind search) ada 2 metode yang umum digunakan, antara lain :

1.    Pencarian Melebar Pertama (Breadth-First Search)

Prosedur pencarian pelebaran pertama (bread-first search) akan dilakukan dengan mencari semua lintasan yang panjangnya 1 (yang panjangnya berhingga), dan kemudian akan mengamati semua lintasan dengan panjang 2 (yang panjangnya juga berhingga). Proses ini terus dilanjutkan sampai semua lintasan dengan panjang N telah diamati, sehingga solusipun dapat diproleh. Akibatnya, prosedur ini akan menjamin ditemukannya solusi. Namun, terdapat tiga yang menjadi persoalan utama sehubungan dengan prosedur tersebut yaitu:

1)    Memerlukan memori yang besar. Jumlah simpul (node) di setiap tingkat dari pohon (tree) bertambah secara ekspononsial terhadap jumlah tingkat, dan kesemuanya itu harus disimpan sekaligus.

2)    Membutuhkan sejumlah besar pekerjaan, khususnya jika lintasan solusi terpendek cukup panjang. Karena jumlah simpul yang diperlukan untuk diperiksa bertambah secara eksponensial.

3)    Ketidakrelevanan operator akan menambah jumlah simpul yang harus diperiksa dengan sangat besar.

 

Keuntungan :

1)    Tidak akan menemui jalan buntu

2)    Menjamin ditemukannya solusi (jika memang ada) dan solusi yang ditemukan pasti yang paling baik

3)    Jika ada satu solusi maka bread-first search akan menemukannya.

Kelemahan :

1)    Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon

2)    Membutuhkan waktu yang cukup lama, karena menguji n level untuk mendapatkan solusi pada level yang ke-(n+1)

2.    Pencarian Mendalam Pertama (Depth-First Search) 

Algoritma DFS pertama kali diperkenalkan oleh Tarjan dan Hopcroft 20 tahun lalu. Mereka menunjukkan bagaimana Depth First Search (DFS) merupakan metode pencarian secara mendalam dan bagian dari blind search atau pencarian buta. Pada metode Depth-First Search, proses pencarian akan dilakukan pada 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.

a.   Keuntungan Depth First Search

1)    Membutuhkan memori yang relatif kecil, karena hanya node – node pada lintasan yang aktif saja yang disimpan.

2)    Secara kebetulan metode Depth First Search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

b.   Kelemahan Depth First Search

1)    Memungkinkan tidak ditemukannya tujuan yang diharapkan.

2)    Hanya akan mendapatkan satu solusi pada setiap pencarian.

 

Analisis Algoritma DFS

Sistem yang dibangun untuk menyelesaikan masalah, menggunakan metode pencarian Depth First Search (DFS). DFS akan mencari keseluruhan kemungkinan rute yang dapat terjadi dari data yang tersedia kemudian hasil dari seluruh pencarian akan dibandingkan untuk mendapatkan hasil yang tercepat atau termurah tergantung kondisi yang diinginkan. Pencarian solusi DFS dicirikan dengan simpul-simpul terdalam terdalam terlebih dahulu. Pertama simpul awal dibangkitkan, kemudian simpul pada arah kedua, pada simpul arah ketiga dan seterusnya. Jadi pencarian mengikuti sebuah lintasan tunggal mulai dari simpul awal terus menurun kebawah ke simpul-simpul arah bawahnya.

Jika pencarian mencapai level terdalam, maka pencarian dilakukan level sebelumnya. Berikut adalah cara kerja algoritma DFS pada aplikasi pencarian rute bus kota. Contoh kasus yang dijelaskan dimisalkan yaitu rute bus dari palur ke klewer berdasarkan database.

A = Bus Atmo

B = Bus Damri

 

Pengecekan rute ke klewer , dimulai dari titik awal Palur menuju ke titik selanjutnya yaitu Panggung, pengguna dapat menggunakan bus Atmo dan Damri dan selanjutnya pada titik Panggung terdapat 2 cabang titik yaitu St. Balapan dan Ps.Gede, maka pengecekan dilakukan pada node paling kiri dulu, dikarenakan pada titik St. Balapan tidak ditemukan data Klewer maka kemudian pengecekan rute dilanjutkan pada node selanjutnya dan jika ditemukan data lokasi sama dengan data lokasi tujuan maka pencarian dihentikan seperti yang ditunjukkan pada gambar 5, bus yang dapat digunakan yaitu bus Damri dari titik Panggung dan sehingga dapat dihasilkan data rute dari Palur menuju Klewer adalah seperti pada tabel hasil pencarian berikut :

 

B.   Metode Pencarian Heuristik

Pencarian Heuristik merupakan teknik yang digunakan untuk meningkatkan efisiensi dari proses pencarian. Pencarian buta tidak selalu dapat diterapkan dengan baik, hal  ini disebabkan waktu aksesnya yang cukup lama serta besarnya memori yang diperlukan. Kelemahan ini sebenarnya dapat diatasi jika ada informasi tambahan dari domain yang bersangkutan. Dalam pencarian state space, heuristic adalah aturan untuk memilih cabang-cabang yang paling mungkin menyebabkan penyelesaian permasalahan dapat diterima. 2 metode pencarian heuristik diantaranya :

1.    Pembangkit dan penggujian (Generate and Test)

·         Penggabungan antara depth first search dengan pelacakan mundur (backtracking)

·         Jika pembangkit possible solution dikerjakan secara sistimatis, maka prosedur akan mencari solusinya, jika ada

·         Nilai pengujian berupa jawaban ya atau tidak

2.    Pendakian bukit (Hill Climbing)

Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan fungsi heuristik. Pembangkitan keadaan  berikutnya  sangat  tergantung  pada  feedback dari  prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.

Inne Meilyanti

Wahyuni 

Referensi

1.    http://library.binus.ac.id/eColls/eThesisdoc/Bab2HTML/2007300192IFBab2/page10.html

2.    http://www.slideshare.net/ceezabramovic/metode-pencarian-heuristik

PENGANTAR TEKNOLOGI SISTEM CERDAS