- Explain the primary difference between an uninformed and an informed search algorithm.
- In what scenario would Depth-First Search be more efficient than Breadth-First Search?
- What is a heuristic function, and what role does it play in the A* algorithm?
- Describe a real-world problem (e.g., GPS navigation) that can be solved using a search algorithm.
jawab:
- Perbedaan utama antara uninformed search dan informed search
Uninformed search adalah algoritma pencarian yang bekerja tanpa informasi tambahan mengenai letak tujuan, sehingga hanya mencari berdasarkan aturan tertentu. Contohnya adalah Breadth-First Search (BFS) dan Depth-First Search (DFS). Sedangkan informed search menggunakan informasi tambahan atau heuristic untuk memperkirakan jalur terbaik menuju tujuan, sehingga pencarian bisa lebih cepat dan efisien. Contohnya adalah algoritma A*. - Kapan Depth-First Search lebih efisien dibandingkan Breadth-First Search?
Depth-First Search (DFS) lebih efisien ketika solusi berada pada tingkat yang cukup dalam dan memori yang tersedia terbatas. Hal ini karena DFS hanya menyimpan jalur yang sedang ditelusuri, sedangkan BFS harus menyimpan semua simpul pada setiap tingkat pencarian. Oleh karena itu, DFS lebih hemat memori dibandingkan BFS. - Apa itu heuristic function dan perannya dalam algoritma A*?
Heuristic function adalah fungsi yang digunakan untuk memperkirakan jarak atau biaya dari suatu titik menuju tujuan. Dalam algoritma A*, heuristic membantu menentukan jalur yang paling menjanjikan sehingga proses pencarian menjadi lebih cepat dan efisien. Algoritma A* menggabungkan biaya yang sudah ditempuh dengan perkiraan biaya menuju tujuan untuk memilih jalur terbaik. - Contoh masalah dunia nyata yang dapat diselesaikan dengan algoritma pencarian
Salah satu contoh adalah sistem navigasi GPS, seperti Google Maps. GPS menggunakan algoritma pencarian untuk menentukan rute tercepat atau terpendek dari lokasi awal ke tujuan. Algoritma akan mempertimbangkan berbagai faktor seperti jarak, kondisi lalu lintas, dan waktu tempuh agar pengguna mendapatkan rute yang paling efisien.