GraphsLanjutFase E–FE1E5

SLIDING PUZZLE 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.

Example use case

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

Syllabus

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

Objectives

·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

How It Works

·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

Prerequisites

·Breadth-First Search
·Priority queue
·Graf berbobot

Real-World Uses

·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

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