GrafLanjutFase E–FE1E5

Adu Cepat BFS vs A*

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.

Contoh kasus

Membandingkan strategi pathfinding pada AI game untuk menentukan metode paling efisien menuju target.

Silabus

Dibanding BFS yang menyebar ke segala arah, A* memakai heuristik sehingga mengunjungi jauh lebih sedikit sel untuk sampai tujuan.

Tujuan Belajar

·Memahami perbedaan cara BFS dan A* menjelajahi grid
·Menjelaskan kenapa heuristik membuat A* lebih hemat langkah
·Menerapkan perbandingan untuk memilih algoritma pathfinding yang pas

Cara Kerja

·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

Prasyarat

·Breadth-First Search
·A* Search

Contoh Nyata

·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

Kompleksitas BFS O(V+E) melebar; A* O(E) lebih terarah berkat heuristik