GraphsLanjutFase E–FE1E5
BFS VS A* RACE
Visualisasi ini membandingkan dua algoritma pencarian jalur secara berdampingan: BFS memperluas simpul secara buta (menyebar merata ke segala arah), sedangkan A* menggunakan heuristik f = g + h untuk mengarahkan pencarian menuju tujuan. Hasilnya A* mencapai target dengan jauh lebih sedikit simpul yang dieksplorasi. Visualisasi menampilkan dua grid yang berlomba dengan penghitung jumlah sel yang dikunjungi masing-masing.
Example use case
Membandingkan strategi pathfinding pada AI game untuk menentukan metode paling efisien menuju target.
Syllabus
Dibanding BFS yang menyebar ke segala arah, A* memakai heuristik sehingga mengunjungi jauh lebih sedikit sel untuk sampai tujuan.
Objectives
- ·Memahami perbedaan cara BFS dan A* menjelajahi grid
- ·Menjelaskan kenapa heuristik membuat A* lebih hemat langkah
- ·Menerapkan perbandingan untuk memilih algoritma pathfinding yang pas
How It Works
- ·BFS memperluas semua tetangga merata tanpa tahu arah tujuan
- ·A* menghitung f = g + h sehingga condong bergerak ke arah goal
- ·Kedua algoritma dijalankan berdampingan pada grid yang sama
- ·Penghitung sel yang dikunjungi menunjukkan siapa yang lebih efisien
- ·A* biasanya menang karena tidak membuang waktu ke arah yang salah
Prerequisites
- ·Breadth-First Search
- ·A* Search
Real-World Uses
- ·Memilih mesin pathfinding tercepat untuk AI musuh di game
- ·Menentukan algoritma rute agar aplikasi maps hemat baterai HP
- ·Membandingkan dua cara cari rute saat ojek online hitung jalur
Complexity BFS O(V+E) melebar; A* O(E) lebih terarah berkat heuristik