Module Question 2
- 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.
Status: 100% sudah tercapai
Keterangan: Saya sudah mengerjakan essay ini dengan baik dan benar
Bukti:
Answers:
-
- Uninformed Search (blind search) adalah algoritma pencarian yang tidak memiliki informasi tambahan tentang seberapa dekat suatu keadaan dengan tujuan. Algoritma hanya menggunakan informasi dasar seperti kondisi awal, kemungkinan langkah, dan tujuan. Contohnya Breadth-First Search (BFS) dan Depth-First Search (DFS).
Informed Search menggunakan informasi tambahan atau heuristik untuk memperkirakan langkah mana yang paling mendekati tujuan. Dengan demikian, pencarian dapat dilakukan lebih terarah dan sering kali lebih efisien. Contohnya adalah A* dan Greedy Best-First Search.
- Depth-First Search (DFS) akan lebih efisien dibandingkan Breadth-First Search (BFS) ketika solusi yang dicari berada jauh di dalam struktur atau salah satu cabang tertentu, terutama jika jumlah cabang sangat banyak.
-
- Heuristic function adalah fungsi yang memberikan perkiraan biaya atau jarak dari suatu kondisi saat ini menuju tujuan. Heuristik membantu algoritma menentukan pilihan yang kemungkinan paling dekat dengan solusi.
Dalam algoritma A*, heuristic function biasanya ditulis sebagai h(n). A* menggunakan rumus:f(n) = g(n) + h(n)
-
- Salah satu masalah dunia nyata yang dapat diselesaikan menggunakan search algorithm adalah mencari rute terbaik menggunakan GPS, seperti Google Maps.
Dalam sistem GPS, lokasi jalan dapat direpresentasikan sebagai graph, di mana persimpangan menjadi node dan jalan menjadi edge. Algoritma pencarian kemudian digunakan untuk menemukan rute dari lokasi awal menuju tujuan.