GrafLanjutFase E–FE1E5

Sliding Puzzle dengan A*

A* mencari solusi 8-puzzle dengan mengevaluasi setiap state memakai f = g + h, di mana g adalah jumlah langkah yang sudah ditempuh dan h adalah heuristik jarak Manhattan tiap ubin ke posisi targetnya. Algoritma selalu mengembangkan state dengan f terkecil dari open set, sehingga menemukan rangkaian geseran ubin paling pendek. Visualisasi menampilkan grid 3x3 yang bergeser tiap langkah beserta nilai g, h, open, dan closed.

Contoh kasus

Fitur auto-solve pada aplikasi puzzle geser (15-puzzle) yang mencari urutan gerakan tersingkat menuju susunan benar.

Silabus

A* mencari jalur terpendek dengan memilih node yang punya f = g + h terkecil, jadi pencariannya terarah ke tujuan.

Tujuan Belajar

·Memahami arti g (biaya nyata dari start) dan h (perkiraan jarak ke tujuan)
·Menjelaskan kenapa rumus f = g + h membuat A* lebih pintar dari BFS biasa
·Menerapkan A* untuk mencari rute pada grid berhalangan

Cara Kerja

·Simpan node yang belum diproses di open set, lalu ambil node dengan f terkecil
·Hitung f = g + h untuk tiap node: g biaya sejauh ini, h tebakan jarak ke goal
·Perbarui tetangga bila ditemukan jalur yang lebih murah, dan catat parent-nya
·Pindahkan node yang sudah selesai ke closed set agar tidak diproses ulang
·Berhenti saat goal tercapai, lalu telusuri parent mundur untuk membentuk jalur

Prasyarat

·Breadth-First Search
·Priority queue
·Graf berbobot

Contoh Nyata

·Google Maps memilih rute tercepat ke sekolah dengan menebak arah tujuan
·NPC musuh di game mengejar pemain sambil menghindari tembok
·Fitur auto-solve pada aplikasi puzzle geser mencari gerakan tersingkat

Kompleksitas O(E) dengan priority queue, tergantung kualitas heuristik h