Assigment 2-Irza Uki Mayorin Atmodjo-BD107-2681494442

pertanyaan:

1. Explain the primary difference between an uninformed and an informed search algorithm.
2. In what scenario would Depth-First Search be more efficient than Breadth-First Search?
3. What is a heuristic function, and what role does it play in the A* algorithm?
4. Describe a real-world problem (e.g., GPS navigation) that can be solved using a search algorithm.

status : 100%

keterangan: saya telah mengerjakan tugas ini dengan baik dan benar

BUKTI:

1.Uninformed Search adalah algoritma pencarian yang tidak memiliki informasi tambahan mengenai seberapa dekat suatu langkah dengan tujuan. Algoritma ini hanya menggunakan informasi dasar, seperti kondisi awal dan aturan pencarian.

Contoh: Breadth-First Search (BFS) dan Depth-First Search (DFS).

Informed Search adalah algoritma pencarian yang menggunakan informasi tambahan berupa heuristik untuk memperkirakan langkah yang paling mendekati tujuan sehingga pencarian dapat dilakukan dengan lebih efisien.

Contoh: Greedy Best-First Search dan A Search*.

2.Depth-First Search (DFS) dapat lebih efisien daripada Breadth-First Search (BFS) ketika solusi berada jauh di dalam suatu cabang pencarian dan penggunaan memori perlu dibatasi.

DFS menelusuri satu cabang hingga sedalam mungkin sebelum kembali ke cabang lain, sedangkan BFS memeriksa semua simpul pada tingkat yang sama terlebih dahulu.

Contohnya, ketika mencari solusi dalam struktur pohon yang sangat dalam, DFS dapat menggunakan memori lebih sedikit karena hanya menyimpan jalur yang sedang ditelusuri dan cabang yang belum selesai. Namun, DFS tidak selalu lebih cepat dan bisa melewatkan solusi terdekat jika memilih cabang yang salah.

3.Fungsi heuristik adalah fungsi yang digunakan untuk memperkirakan biaya atau jarak dari suatu posisi saat ini menuju tujuan.

Dalam algoritma A*, fungsi heuristik dilambangkan dengan $h(n)$. A* menggabungkan biaya yang telah dikeluarkan untuk mencapai simpul saat ini, yaitu $g(n)$, dengan perkiraan biaya menuju tujuan, yaitu $h(n)$.

Rumus A* adalah:

Keterangan:

• $f(n)$: perkiraan total biaya jalur melalui simpul $n$.

• $g(n)$: biaya dari titik awal menuju simpul $n$.

• $h(n)$: perkiraan biaya dari simpul $n$ menuju tujuan.

Peran fungsi heuristik adalah membantu A* memilih simpul yang paling menjanjikan untuk dieksplorasi terlebih dahulu sehingga pencarian dapat menjadi lebih efisien. Jika heuristik tidak melebih-lebihkan biaya sebenarnya menuju tujuan, A* dapat menemukan solusi optimal dengan kondisi implementasi yang sesuai.

4.Salah satu contohnya adalah menentukan rute tercepat menggunakan GPS atau aplikasi navigasi, seperti Google Maps.

Ketika seseorang ingin pergi dari rumah ke kantor, aplikasi navigasi menggunakan algoritma pencarian untuk menentukan jalur yang sesuai berdasarkan jaringan jalan yang tersedia.

Prosesnya meliputi:

1. Menentukan lokasi awal dan tujuan.

2. Merepresentasikan persimpangan sebagai simpul (node) dan jalan sebagai sisi (edge).

3. Menghitung biaya perjalanan berdasarkan jarak, waktu tempuh, atau kondisi lalu lintas.

4. Menggunakan algoritma seperti A* atau Dijkstra untuk mencari rute yang paling sesuai.

5. Menampilkan rute yang direkomendasikan kepada pengguna.