Uninformed Search (Blind Search): Algoritma ini tidak memiliki informasi tambahan mengenai jarak atau biaya menuju goal state selain definisi masalah itu sendiri (start state, target state, dan aksi yang tersedia). Algoritma menjelajahi ruang pencarian secara sistematis tanpa memperhitungkan seberapa dekat suatu node dengan target.
- Contoh: Breadth-First Search (BFS), Depth-First Search (DFS), Uniform Cost Search (UCS).
Informed Search (Heuristic Search): Algoritma ini menggunakan pengetahuan atau informasi domain spesifik (berupa fungsi heuristik $h(n)$ ) untuk mengestimasi seberapa dekat suatu node ke tujuan. Informasi ini membimbing pencarian agar diprioritaskan pada jalur yang paling menjanjikan.
- Contoh: A* Search, Greedy Best-First Search.

Depth-First Search (DFS) lebih efisien dibandingkan Breadth-First Search (BFS) pada skenario berikut:

Keterbatasan Memori (Space Complexity):
- DFS memiliki space complexity $O(bm)$ (linier terhadap kedalaman maksimum $m$ ), sedangkan BFS membutuhkan $O(b^d)$ (eksponensial terhadap kedalaman solusi $d$ ). Jika ruang pencarian sangat luas/lebar, BFS akan menghabiskan memori RAM dengan cepat karena menyimpan seluruh child node di setiap level.
Solusi Berada di Kedalaman Pohon / Banyak Solusi (Deep & Abundant Solutions):
- Jika solusi terletak pada jalur yang dalam dan terdapat banyak solusi dalam ruang pencarian, DFS dapat menemukannya lebih cepat karena langsung menelusuri satu cabang hingga dasar tanpa perlu mengeksplorasi seluruh node di tingkat atasnya.

Heuristic Function $h(n)$ :

Fungsi evaluasi matematika yang memberikan estimasi biaya terendah dari node saat ini $n$ menuju node tujuan (goal node). Contoh fungsi heuristik umum adalah Euclidean Distance (jarak garis lurus) atau Manhattan Distance.
Peran Heuristik dalam Algoritma A:*

Algoritma A* menentukan urutan eksplorasi node berdasarkan fungsi evaluasi total:

$f(n) = g(n) + h(n)$
- $g(n)$ : Biaya sebenarnya yang telah ditempuh dari start node ke node saat ini $n$ .
- $h(n)$ : Estimasi biaya heuristik dari node $n$ ke goal node.
Fungsi $h(n)$ memandu A* agar mengarahkan pencarian secara cerdas ke arah target, meminimalkan eksplorasi cabang yang tidak relevan. Jika $h(n)$ bersifat admissible (tidak pernah mengestimasi biaya lebih tinggi dari biaya sebenarnya) dan consistent, maka algoritma A* dijamin menghasilkan solusi optimal/terpendek.

Skenario Masalah:

Aplikasi navigasi seperti Google Maps, Waze, atau sistem GPS pada kendaraan otonom perlu menentukan rute mengemudi tercepat dari titik asal (Start) ke lokasi tujuan (Destination).
Penerapan Algoritma Pencarian:
1. Pemodelan Graf: Peta jalan didefinisikan sebagai graf terarah di mana persimpangan/lokasi diwakili oleh Node, dan ruas jalan diwakili oleh Edge yang memiliki bobot (jarak, batas kecepatan, atau kondisi lalu lintas real-time).
2. Penggunaan Algoritma A:* Sistem menggunakan algoritma A* untuk menemukan jalur optimal.
  - $g(n)$ : Waktu tempuh aktual yang diakumulasikan dari titik awal hingga persimpangan $n$ .
  - $h(n)$ : Jarak garis lurus (Euclidean distance) dari persimpangan $n$ ke titik tujuan akhir.
3. Hasil: Algoritma secara efisien menghindari eksplorasi rute yang berlawanan arah dari target dan dengan cepat menemukan jalur tercepat bahkan dalam jaringan jalan yang sangat kompleks.