Apa yang dimaksud dengan pencarian buta tanpa informasi dan pencarian heuristik dengan informasi

Sudah saatnya kita mengenal algoritma pada Blind Search (pencarian buta) dan Heuristic Search (pencarian terbimbing). Khususnya bagi pelajar dan mahasiswa, apalagi yang sudah melewati kedua status tersebut yang masih fokus di dunia programming.

Blind Search dan Heuristic Search merupakan sub bahasan yang sifatnya fundamental dalam mata kuliah Kecerdasan Buatan (Artificial Intelligence). Bahkan dalam dunia nyata, kita sering dituntut untuk berpikir dengan cara-cara tersebut. Seperti ketika bermain puzzle, catur, kubus cerdas, atau mengira-ngira rute perjalanan mana yang akan kita tempuh. Semua itu terkait dengan otak kita yang sudah otomatis berpikir dengan algoritma blind search atau heuristic search, atau bahkan lebih kompleks lagi.

Blind Search merupakan pencarian asal ketemu. Jika solusi sudah ketemu, maka pencarian akan dihentikan. Jika dibuat skemanya, pencarian buta hanya mengenal tiga bagian, [masalah]-[pencarian]-[solusi]. Misalkan dalam kotak ada 3 kelereng warna merah, 3 biru, dan 3 kuning. Masalahnya adalah, ambillah satu kelereng yang berwarna merah. Solusi, setelah melakukan pencarian, kemudian didapat satu kelereng warna merah, nah, itulah solusinya.

Berbeda dengan Heuristic Search, Heuristic Search adalah pencarian bersyarat (terbimbing). Artinya, solusi yang diperoleh adalah solusi yang terbaik, bukan solusi sekali ketemu. Bagian-bagiannya adalah [masalah]-[pencarian]-[syarat]-[solusi]. Misal contoh masalah pada kasus di atas, Ambillah kelereng merah yang tidak pecah dan tidak lonjong. Sehingga ketika ketemu kelereng merah dan ada pecahnya, itu masih bukan solusi karena tidak sesuai dengan syarat (tidak pecah dan tidak lonjong).

Sehingga perbedaan mendasar dari Blind Search dan Heuristic Search adalah :

• Blind Search merupakan pencarian biasa, sedangkan Heuristic Search adalah pencarian bersyarat
• Variabel data pada Blind Search tidak mempunyai atribut / informasi tambahan, sedangkan pada Heuristic Search memiliki. Contoh pada kasus di atas, "pecah" dan "lonjong" merupakan atribut dari "kelereng".

Konsep Blind Search dan Heuristic Search memiliki beberapa penerapan algoritma. Algoritma yang termasuk Blind Search yaitu Breadth First Search (BFS), Depth First Search (DFS), Uniform Cost Search (UCS), Depth-Limited Search (DLS), Iterative-Deeping Search (IDS), dan Bi-directional search (BDS). Hanya saja yang paling banyak dibahas adalah Breadth First Search (BFS) dan Depth First Search (DFS). Sedangkan untuk contoh algoritma Heuristic Search yaitu Generate and Test, Simple Hill Climbing, Steepest-Ascent Hill Climbing, Simulated Annealing, Greedy, Best-First Search, dan A* (A Star).

1. DFS : Implementasi Algoritma Depth First Search (DFS) dengan PHP

Ada yang mau beri saran untuk implemenetasinya?

Metode Pencarian/Pelacakan (Search Method) Pada Artificial Intelligence

Pada saat menentukan suatu keberhasilan pada sistem kecerdasan yaitu melalui kesuksesan pencarian  dan pencocokan. Adapun  2 (dua)  teknik pencarian / pelacakan yang dipakai,  yaitu  pencarian  buta  (blind search) dan pencarian terbimbing (heuristic search).

Pencarian Buta / tanpa informasi (Blind Search)

Pada metode pencarian buta (blind search)  umumnya menggunakan 2 metode yang digunakan,  antara lain:

• 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.
• Pencarian Mendalam Pertama (Depth-First Search) ; metode Depth-First Search ini akan dilakukan pada proses pencarian semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level  yang lebih tinggi. Proses ini  akan terus diulangi hingga mendapatkan solusi.

Pencarian Heuristik / dengan informasi (Heuristic Search)

Dalam pencarian  buta tidak dapat sering diterapkan dengan baik, hal  ini dikarenakan dalam waktu aksesnya cukup lama dan besarnya memori yang dipakai. Kelemahan ini dapat diatasi jika memiliki informasi tambahan dari domain yang bersangkutan. Ada 4 metode dalam pencarian heuristik, antara lain:

• Pembangkit dan penggujian (Generate and Test); Metode  ini merupakan  penggabungan  antara  depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju suatu keadaan awal. Nilai Pengujian berupa jawaban baik berupa ‘ya’ atau ‘tidak’. 
• Pendakian bukit (Hill Climbing) ; Pada metode ini hampir sama seperti metode pembangkitan dan pengujian, namun proses pengujian ini dilakukan dengan  fungsi heuristik. Pembangkitan kondisi  yang  berikutnya sangat  tergantung  pada  feedback dari  prosedur pengetesan. Tes  fungsi heuristik  akan menunjukan seberapa baiknya nilai perkiraan yang diambil terhadap kondisi-kondisi lainnya yang mungkin terjadi. 
• Pencarian terbaik pertama (Best First Search) ; metode best-first search merupakan metode yang  mengambil kelebihan dari kedua metode kombinasi dari metode depth-first search dengan metode breadth-first search. Apabila ada pencarian dengan metode hill climbing tidak dapat untuk balik ke node pada level yang lebih rendah walaupun node pada level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain halnya dengan metode best-first search ini. Pada metode best-first search, pencarian dapat mengunjungi node yang ada dilevel yang lebih rendah, jika node pada level yang lebih tinggi memiliki nilai heuristik yang lebih buruk. 
• Simulated Annealing ; Ide dasar terbentuk simulated Annealing yaitu dari pemrosesan logam. Annealing (memanaskan kemudian mendinginkan) dalam pemrosesan logam adalah suatu proses bagaimana  membuat bentuk cair yang sedikit demi sedikit menjadi bentuk yang lebih padat seiring dengan penurunan pada temperatur. Simulated annealing umumnya digunakan dalam penyelesaian masalah yang dimana perubahan keadaan dari suatu kondisi ke kondisi yang lainnya membutuhkan ruang yang sangat besar, misalkan perubahan gerakan dengan menggunakan  permutasi pada masalah Travelling Salesman Problem.

Dibawah ini merupakan  contoh-contoh dari metode pencarian pada kecerdasan buatan (Artificial Intelligence/AI):

• Contoh Breadth-First Search.Dapat dilihat pada contoh ini bahwa gerakan kebawah meproses tingkat demi tingkat hingga tujuannya tercapai. Maka urutan proses seaching Bread-First Search ditunjukkan pada gambar adalah dimulai  dari S-A-D-B-D-A-E-C-E-E-B-B-F-D-F-B-F-D-E-A-C dan berakhir pada G. 

• Contoh Depth-First Search. Contoh ini merupakan depth-first karena hanya satu alternatif dipilih dan didesak pada setiap simpul sampai tujuan tercapai atau simpul tercapai bila gerak yang jauh lebih ke bawah tidak mungkin. Pada saat gerak yang jauh lebih kebawah itu tidak mungkin, maka dalam pencariannya dimulai kembali pada simpul nenek moyang yang terdekat memiliki anak-anak yang tidak diselidiki. Pada urutan proses seaching Depth-First Search ditunjukkan pada gambar adalah dimulai  dari S-A-B-C-E-D-F- dan berakhir di G. 

• Pada gambar ini menunjukkan jarak garis lurus dari tiap-tiap kota ke tujuan.  Sehingga kita dapat mengetahui jarak-jarak antara masing-masing kota dan tujuan. Jika kita harus mencapai tujuan, maka lebih baik berada dalam suatu kota terdekat, tetapi tidak selalu begitu; Kota C lebih dekat dari pada seluruhnya kecuali kota F, tetapi kota C bukanlah tempat yang baik untuk ditempati. 

contoh Hill Climbing. Pada gambar ini menunjukkan apa yang terjadi jika pendakian bukit(hill climbing) digunakan terhadap masalah transversal map dengan menggunakan jarak terbang burung gagak untuk mengatur pilihan. Hill Climbing ini merupakan pencarian depth-first yang memiliki ukuran heurestik yang ,mengatur pilihan-pilihan sebab simpul diperluas. Angka-Angka disamping simpul merupakan jarak garis lurus dari kota yang memiliki terakhir ke kota tujuan. 

• Contoh gambar pohon pencarian yang mempunyai simpul resep ini menunjukkan bagian pohon pencarian yang berawal dari resep dasar untuk telur dadar aprikot. Transformasi-transformasi bahan membentuk pohon; Interestingness heurestics ( heuristik yang menarik)  mengarahkan pencarian best-first pada peluang-peluang yang lebih baik. Pada gambar ini kita dapat menemukan resep telur dadar strawberry dengan mengunakan transformasi subtitusi dasar resep dadar aprikot. Setelah mempunyai dadar strawberry, kita dapat melanjutkan untuk menemukan resep pisang strawberry, dengan menggunakan transformasi tambahan.  Sehingga pengetahuan yang lebih banyak biasanya dapat mengurangi waktu pencarian. 

• Contoh sebuah rute yang dapat dilewati sales tersebut dimana harus melewati setiap perumahan yang tepat sekali. Terdapat 4 Perumahan, dengan jarak  masing-masing kota AB=10, AC=20, AD=25, BC=15, BD=10 CD=30. Tujuannya adalah mencari jarak terpendek bagi sales untuk mengunjungi semua perumahan sekali. Penyelesaian menggunakan generate-test adalah dengan membangkitkan solusi-solusi yang mungkin ada sesuai permasalahan yang dihadapi oleh sales tersebut. Kombinasi abjad sebagai solusi yang mungkin adalah n! = 4! = 24. Tujuannya agar dapat mencari solusii rute terpendek.Rute dikatakan valid apabila jalur yang dilalui tidak berjarak 0. Jika rute valid, maka jarak dihitung kemudian dibandingkan untuk mendapatkan jarak yang sangat optimal.

Dari tabel diatas, solusi pertama yang dibangkitkan adalah ABCD = 45, solusi kedua ABDC=40. Ternyata solusi kedua menghasilkan jarak yang lebih pendek sehingga dipilih lintasan ABDC=40. Lakukan untuk langkah selanjutnya. Pada tabel didapat solusi terpendek lagi yang sama dengan ABDC yaitu CDBA atau DBAC. Kelemahan dari teknik generate & test ini memerlukan dibangkitkan semua kemungkinan yang ada sehingga jika ditambahkan satu perumahan untuk permasalahan TSP ini yaitu menjadi 5 perumahan akan memerlukan 120 kombinasi lintasan, kecuali diberikan kondisi tertentu misalnya perumahan awal bagi sales telah ditentukan.

REFERENSI :