Module Question 2
1. Explain the primary difference between an uninformed and an informed search algorithm.
Jawaban:
– Uninformed Search (Pencarian Tanpa Informasi): Algoritma ini berjalan tanpa memiliki informasi tambahan mengenai seberapa dekat posisi saat ini dengan titik tujuan (goal). Algoritma menelusuri jalur secara sistematis/buta berdasarkan struktur pohon atau graf. Contoh: Breadth-First Search (BFS) dan Depth-First Search (DFS).
– Informed Search (Pencarian Berinformasi): Algoritma ini menggunakan informasi tambahan berupa fungsi heuristik untuk memperkirakan jarak atau biaya terdekat menuju titik tujuan, sehingga pencarian menjadi jauh lebih terarah dan efisien. Contoh: Algoritma A* dan Greedy Best-First Search.
1. In what scenario would Depth-First Search be more efficient than Breadth-First Search?
Jawaban:
DFS lebih efisien daripada BFS dalam skenario berikut:
– Solusi Berada Sangat Dalam (Deep Solution): Ketika letak titik solusi berada di bagian paling bawah pohon pencarian dan cabang jalurnya sangat lebar.
– Keterbatasan Memori (RAM): DFS jauh lebih hemat memori karena hanya menyimpan satu jalur aktif dari atas ke bawah (kompleksitas ruang linier O(bm)), sedangkan BFS harus menyimpan seluruh node di setiap tingkatan (kompleksitas ruang eksponensial O(b^d)) yang riskan membuat memori penuh.
2. What is a heuristic function, and what role does it play in the A* algorithm?
Jawaban:
– Pengertian Fungsi Heuristik h(n): Adalah rumus perkiraan atau estimasi biaya terendah dari posisi node saat ini (n) menuju ke titik tujuan.
– Peran dalam Algoritma A*: Algoritma A* menghitung total biaya f(n) = g(n) + h(n), di mana g(n) adalah biaya nyata yang sudah ditempuh dan h(n) adalah estimasi biaya ke titik tujuan. Fungsi h(n) mengarahkan pencarian agar selalu mengutamakan jalur yang paling mendekati lokasi tujuan, sehingga mencegah algoritma membuang waktu memeriksa jalur yang salah.
3. Describe a real-world problem (e.g., GPS navigation) that can be solved using a search algorithm.
Jawaban:
– Deskripsi Masalah: Aplikasi peta digital (seperti Google Maps atau Waze) harus menemukan rute jalan tercepat atau terpendek dari titik keberangkatan ke titik tujuan di antara ribuan persimpangan jalan.
– Penerapan Algoritma Pencarian:
* Node (Titik): Persimpangan jalan atau lokasi.
* Edge (Garis): Jalan raya penghubung, dengan bobot berupa jarak tempuh atau estimasi waktu.
* Solusi dengan A* Search: GPS menerapkan algoritma A* Search dengan memperhitungkan biaya jalan yang telah dilalui g(n) dan estimasi jarak garis lurus ke lokasi tujuan h(n) untuk menentukan rute tercepat secara instan tanpa perlu memeriksa seluruh jalan di kota tersebut.