Pencarian heuristik — Greedy best-first & A*

Problem solving agent, uninformed vs informed search, fungsi heuristik, dan kenapa A* optimal jika heuristiknya admissible.

SlideInformed SearchHal. 11–18 · evaluasi A*, penelusuran, dan heuristik admissible

Banyak masalah AI dirumuskan sebagai pencarian di ruang keadaan (state space search). Agen pemecah masalah mendefinisikan:

State awal dan goal test (kapan masalah selesai),
Aksi yang tersedia di setiap state dan model transisi (aksi membawa ke state mana),
Biaya jalur (path cost) $g(n)$ .

Contoh: puzzle 8-kotak, rute di peta, penjadwalan, bahkan langkah catur.

Yang akan kamu pahami

Hitung prioritas frontier, bedakan keputusan Greedy dari A*, dan jelaskan bagaimana heuristik dapat memengaruhi optimalitas.

Uninformed vs informed

Uninformed search (BFS, DFS, UCS/Dijkstra, iterative deepening) tidak tahu apa-apa tentang posisi goal. Ia menjelajah secara sistematis ke segala arah.

Informed search memakai heuristik $h(n)$ : perkiraan biaya termurah dari $n$ ke goal. Pada grid, heuristik yang umum adalah jarak Manhattan $|x_1 - x_2| + |y_1 - y_2|$ .

Greedy best-first: pilih node dengan $h(n)$ terkecil. Rakus mendekati goal, cepat, tapi bisa tertipu jalan buntu dan tidak optimal.
A*: pilih node dengan $f(n) = g(n) + h(n)$ , yaitu biaya yang sudah dikeluarkan ditambah perkiraan sisa.

Perhatikan jumlah node dijelajahi di bawah grid. A* biasanya menjelajah jauh lebih sedikit daripada Dijkstra, dengan biaya jalur yang sama. Greedy bisa lebih sedikit lagi, tapi coba buat dinding berbentuk “U” yang menghadap goal: greedy akan masuk perangkap dan jalurnya jadi lebih mahal.

Telusuri frontier A*

Gunakan sisi S→A = 4, S→B = 1, B→A = 1, dan A→G = 2. Heuristiknya h(A) = 1, h(B) = 2, dan h(G) = 0. Coba prediksi node berikutnya sebelum menekan maju.

Prioritas frontier A* berubah ketika g turun

1/3Ekspansi S. B punya h lebih besar dari A, tetapi biaya total taksirannya lebih rendah.A: 4 + 1 = 5 · B: 1 + 2 = 3 · pilih B

Greedy akan mengambil A dulu karena h(A) lebih kecil, kemudian mengambil G dengan biaya jalur 6. A* mendapat biaya 4 pada graf ini.

Kapan A* optimal?

Jarak Manhattan admissible pada grid 4-arah karena setiap langkah minimal berbiaya 1, sehingga tidak mungkin sampai lebih murah dari jarak Manhattan.

$h(n) = 0$ membuat A* menjadi Dijkstra: tetap optimal, tapi menjelajah banyak.
$h$ yang makin mendekati $h^*$ (tetap admissible) membuat A* menjelajah makin sedikit.
$h$ yang overestimate membuat A* lebih cepat tapi bisa tidak optimal.

Perbandingan

Algoritma	Lengkap?	Optimal?	Strategi
BFS	ya	ya (biaya seragam)	FIFO
DFS	tidak (graf tak hingga)	tidak	LIFO
UCS / Dijkstra	ya	ya	$\min g(n)$
Greedy best-first	tidak	tidak	$\min h(n)$
A*	ya	ya (h admissible)	$\min g(n) + h(n)$