Nama :Rizki Maulana
Nim :2681494624
Matkul :Matkul :Artificial Intelligence 26/27 – BD107
- Explain the primary difference between an uninformed and an informed search algorithm.
Jawaban :
- Perbedaan utamna antara Uninformed Searchdan Informed Search terletak pada penggunaan informasi tambahan dalam proses pencarian solusi. Uninformed Search merupakan metode pencarian yang tidak menggunakan pengetahuan atau estimasi khusus mengenai kedekatan suatu keadaan (State) terhadap tujuan (Goal). Algoritma hanya menggunakan informasi dasar dari permasalahan, seperti keadaan awal, kemungkinan tindakan, dan keadaan tujuan. Contohnya adalah Breadth-First Search (BFS) dan Depth-First (DFS).
- In what scenario would Depth-First Search be more efficient than Breadth-First Search?
Jawaban :
- Depth-First Search (DFS)dapat lebih efisien dibandingkan Bradth-First Search (BFS) apalagi solusi berada pada kedalaman yang relatif jauh algoritma DFS menemukan jaluk menuju solusi tersebut lebih awal. DFS bekerja dengan mengekspolarasi suatu cabang secara mendalam hingga mencapai batas tertentu atau menemukan solusi, kemudia melakukan backtracking apabila solusi tidak ditemukan.
- DFS memiliki kebutuhanmemori yang relatif lebih renda dibandingkan BFS. BFS harus disimpan sejumlah besar node pada setiap tingkat pencarian, sedangkan DFS terutama menyimpan node yang berada pada jalur pencarian aktif.
- DFS memiliki kelemahankarena tidak menjamin ditemukannya solusi dengan jalur terpendek, khusus nya pada permasalahan yang memiliki banyak kemungkinan jalur, oleh karena itu pemilihan DFS atau BFS harus disesuaikan dengan karakteristik ruang pencarian dan tujuan yang ingin dicapai.
- What is a heuristic function, and what role does it play in the A* algorithm?
Jawaban :
- Heuristic Fuction merupakan suatu fungsi yang digunakan untuk memberikan estimasi mengenai biaya atau jarak dari suatu keadaan tertentu menuju keadaan tujuan. Fungsi ini biasanya dinyatakan sebagai h(n), dengan n menunjukan node atau keadaan yang sedang dievaluasi.
- dalam algoritma A* heuristic function memiliki peran penting dalam menentukan node yang akan dieksplorasi berikutnya. A* menggunakan fungsi evaluasi :
- f(n) = g(n) + h(n)
Keterangan :
- g(n)adalah biaya aktual yang telah ditempuh dari keadaan awal menuju node n.
- h(n)adalah estimasi biaya dari node n menuju keadaan tujuan.
- F(n)adalah estimasi total biaya suatu jalur melaluji node n.
Dengan menggabungkan biaya aktual dan estimasi biaya tersebut, A* dapat melakukan pencarian secara lebih terarah. Sebagai contoh, pada sistem navigasi GPS, jarak garis lurus antara posisi saat ini dengan lokasi tujuan dapat digunakan sebagai salah satuy bentuk estimasi heuristik.
- Describe a real-world problem (e.g., GPS navigation) that can be solved using a search algorithm.
Jawaban :
- Salah satu penerapan algoritma pencarian dalam kehidupan nyata adalah sisten navigasi GPS. Dalam sistem tersbut, lokasi dan persimpangan jalan dapat direpsentasikan sebagai node, sedangkan jalan yang menghubungkan setiap lokasi direpresentasikan sebagai edge. Dalam penerapannya, g(n) dapat merepresentasikan biaya perjalanan yang telah ditempuh, sedangkan h(n) dapat digunakan untuk memperkirakan jarak dari lokasi saat ini menuju tujuan. Dengan demikian, algoritma A* dapat membantu sistem menemukannya rute secara lebih efisien dibandingkan pencarian yang tidak menggunakan infomasi heuristik.