Pencarian Heuristik dan Algoritma Informasi

Konsep Heuristik dan Fungsi Evaluasi

Pada pertemuan sebelumnya, kita telah membahas pencarian buta (uninformed search) seperti BFS dan DFS, yang bekerja tanpa informasi tambahan tentang posisi goal. Namun, dalam kasus nyata — seperti navigasi robot, rute GPS, atau pencarian solusi pada permainan catur — diperlukan pendekatan yang lebih cerdas untuk mempercepat pencarian. Pencarian heuristik (heuristic search) disebut juga informed search, karena menggunakan informasi tambahan (heuristik) untuk memperkirakan seberapa dekat suatu state dengan goal. Dengan heuristik, sistem AI dapat memilih jalur yang lebih menjanjikan, bukan sekadar mencoba semua kemungkinan seperti BFS/DFS.

Kata heuristic berasal dari bahasa Yunani heuriskein, yang berarti menemukan atau menemukan jalan. Heuristik adalah fungsi estimasi yang digunakan untuk menilai seberapa baik suatu keadaan (state) dalam mendekati tujuan (goal). Heuristik tidak selalu benar atau akurat, tetapi memberikan petunjuk (guidance) agar proses pencarian menjadi lebih efisien.

Fungsi evaluasi digunakan untuk memilih node terbaik yang akan diekspansi (dilanjutkan penelusurannya) berdasarkan gabungan antara biaya aktual dan estimasi heuristik.

Best-First Search, A* Algorithm

Setelah memahami konsep heuristik (h) dan fungsi evaluasi (f), langkah berikutnya adalah mempelajari dua algoritma utama dalam pencarian heuristik, yaitu:
- Best-First Search (BFS heuristik)
- A* (A-Star) Algorithm