METODE PENCARIAN

Pencarian adalah suatu proses mencari solusi suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan(state space). Sedangkan Metode Pencarian adalah bagian dari kesimpulan dimana setiap pendapat yang diberikan menggambarkan hipotesis dalam sebuah rangkaian deduktif.Metode pencarian dianggap penting dalam sebuah perencanaan karena dalam sebuah permainan akan menentukan apa yang harus dilakukan, dimana setiap pendapat menggambarkan kemungkinan posisi suatu saat. Selain itu metode pencarian juga dikatakan penting untuk menyelesaikan permasalahan karena setiap pendapat menggambarkan langkah - langkah untuk menyelesaikan suatu permasalahan.

A. Metode Pencarian Buta
1. Breadth First Search (BFS)
BFS merupakan pencarian yang dilakukan dengan mengunjungi setiap node secara sistematis pada tiap level hingga keadaan tujuan (goal state) ditemukan. Dengan kata lain semua node pada level n akan dikunjungu terlebih dahulu sebelum mengunjungi node - node pada level n+1. Pencarian dimulai node akar terus ke node level satu dari kiri ke kanan begitu juga ke node level selanjutnya. Untuk lebih jelasnya seperti pada gambar di bawah ini :

Contoh penerapan dari Breadth First Search pada simulasi rute terpendek lokasi pariwisata di nias. Dengan cara kerjanya adalah pengguna memasukkan tujuan awal dan akhir dari lokasi pariwisata yang ingin dikunjungi. Kemudian program akan menelusiri dari titik pangkal karena titik tersebut merupakan titik dengan level tertinggi. Maka selanjutnya program akan melanjutkan penelusuran dengan menjelajahi titik - titik pada level dibawahnya. Setelah semua titik dijelajahi oleh program maka akan ditemukan jalur terpendek dari rute perjalanan tersebut. 

2. Depth First Search (DFS)
DFS merupakan pencarian yang dilakukan dari node awal secara mendalam (deep) hingga akhir node yang paling akhir (dead-node). Dengan kata lain pencarian dimulai dari akar ke level yang lebih tinggi dan prosesnya diulangi sampai ditemukan solusinya.

Contoh penerapan dari Depth First Search pada pencarian rute bis kota berbasis web mobile. Cara kerja dari penerapan tersebut adalah Depth First Search akan mencari semua solusi yang dapat terjadi pada semua rute dimulai dari simpul yang paling kiri dengan level paling tinggi sampai ke simpul paling kanan dengan level terdalam. Lalu hasil pencarian dengan metode Depth First Search dapat menampilkan semua solusi yang dapat terjadi sesuai dengan keinginan si pemakai baik dari segi jarak atau biaya yang paling optimal.


B. Metode Pencarian Heuristik
1. Generate & Test (GT)
GT merupakan metode yang paling sederhana dalam pencarian heuristik. Algoritma yang diguanakan oleh GT menggunakan prosedur DFS karena suatu solusi harus dibangkitkan secara lengkap sebelum dilakukan test.
Terdapat 2 prosedur penting di dalam GT yaitu :

• Pembangkit (generate,) yang membangkitkan semua solusi yang memungkinkan.
• Test, yang menguji solusi yang di bangkitkan.

Contoh penerapan dengan menggunakan Generate & Test adalah Travelling Salesman Problem. Dimana seorang salesman ingin mengunjungi sejumlah n kota. Akan dicari rute terpendek di mana setiap kota hanya boleh dikunjungi tepat 1 kali. Jarak antara tiap- tiap kota sudah diketahui. Misalkan ada 4 kota dengan jarak antara tiap - tiap kota seperti terlihat pada gambar berikut

Lalu untuk membangkitkan solusi - solusi yang mungkin dengan menyusun kota kota tersebut dalam urutan abjad seperti :

• A-B-C-D
• A-B-D-C
• A-C-B-D
• A-C-D-B
• Dst

Untuk mengetahui jumlah seluruh kombinasi abjad  yang mungkin menjadi sebuah solusi dengan (n!). Lalu dipilih keadaan awal misalnya ABCD dengan panjang lintasan 19. Lakukan backtracking untuk mendapatkan lintasan ABDC misalkan panjang lintasannya 18. Bandingkan lintasan ABDC dengan sebelumnya, dan lintasan terpendek yang akan dilakukan backtracking lagi. Solusi terbaik adalah menemukan lintasan terpendek dari kota yang dilewati. Untuk lebih jelasnya dapat dilihat dalam bentuk table dibaawah ini.

2. Hill Climbing (HC)
Metode HC mirip dengan metode GT namun pembedanya adalah umpan balik (feedback) yang berasal dari prosedur pengujian digunakan untuk memutuskan arah gerak dari pencarian. Terdapat 2 macam metode HC yaitu : 

• Simple Hill Climbing, langsung memilih new state yang memiliki jalur lebih baik dari pada jalut - jalur sebelumnya tanpa memperhitungkan jalur - jalur lain yang lebih "curam".
• Steepest-Ascent Hill Climbing, akan mengevaluasi semua state yang berada di bawah current state dan memilih state dengan jalur yang paling "curam".

Contoh kasus pada Hill Climbing sama dengan Generate & Test yaitu menggunakan kasus Travelling Salesman Prolem. Disini operator yang digunakan adalah operator yang bisa menghasilkan kombinasi lintasan kota yang berbeda yaitu dengan menukar urutan posisis 2 kota dalam suatu lintasan. Bila ada kota n maka kombinasi lintasannya adalah : 

Dari perhitungan kombinasi diatas maka jika terdapat 4 kota maka kombinasinya ada 6 yaitu :

1. (1,2) tukar urutan posisi kota 1 dengan kota 2
2. (2,3) tukar urutan posisi kota 2 dengan kota 3
3. (3,4) tukar urutan posisi kota 3 dengan kota 4
4. (4,1) tukar urutan posisi kota 4 dengan kota 1
5. (2,4) tukar urutan posisi kota 2 dengan kota 4
6. (1,3) tukar urutan posisi kota 1 dengan kota 3

Pada pencarian ini, penggunaan urutan dari kombinasi harus konsisten. Setelah kombinasi ditentukan maka digunakan kombinasi Simple Hill Climbing dengan keadaan awal ABCD.

 

Keadaan awal, lintasan ABCD = 19. Level pertama, Hill Climbing mengunjungi BACD = 17. Karena BACD lebih kecil dari ABCD maka BACD yang dipilih selanjutnya dengan operator tukar 1,2.Untuk level kedua mengunjungi ABCD karena operator tukar 1,2 sudah dipakai BACD dan pilih node lain yaitu BCAD = 15 karena BCAD lebih kecil dari BACD. Untuk level ketiga mengunungi CBAD = 20 karena CBAD lebih besar dari BCAD maka kita pilih node lain yaitu BCDA = 18. Namun masih lebih besar jadi pilih DCAB = 17. Namun masih lebih besar kita pilih node BDAC = 14 karena nilai nodenya sudah lebih kecil dari BCAD.

Untuk level keempat mengunjungi DBAC - 15, karena DBAC lebih besar dari BDAC jadi kita pilih node lain yaitu BDCA = 13 dan nilai node BDCA sudah lebih kecil dari BDAC. Level kelima mengunjungi DBCA = 12. Karena nilai node DBCA sudah lebih kecil dari BDAC maka nodenya langsung dipilih. Untuk level keenam mengunjungi BDCA karena operator tukar 1,2 sudah dipakai DBCA maka pilih node lain yaitu DCBA, lalu pilih DBAC, lalu pilih ABCD, lalu pilih DACB dan pilih CBDA. Karena sudah tidak ada node yang memiliki nilai heuristik yang lebih kecil dibandingkan dengan nilai heuristik DBCA maka node DBCA adalah lintasan terpendek (solusi).

Sumber Referensi :

• Anonim. "Bab 4 Algoritma Pencarian (Searching Algorithm)". 
• Handoko Prio. "Bab 2 Teknik Dasar Pencarian". 
• Zamanhuri Irvanizam, Gani Taufiq A. "Heuristic Search".
• Herwanto Arif, Eka Purnama Bambang. 2013. "PENERAPAN METODE DEPTH FIRST SEARCH PADA PENCARIAN RUTE BUS KOTA BERBASIS WEB MOBILE DI SOLO".
• Zai Delima, Budiati Haeni, Sandino Berutu Sunneng. 2016. "SIMULASI RUTE TERPENDEK LOKASI PARIWISATA DI NIAS DENGAN METODE BREADTH FIRST SEARCH DAN TABU SERCH".