GrafLanjutFase E–FE1E5

Perbandingan Dijkstra vs A* Search

Video ini membandingkan dua algoritma pencari jalur terpendek pada labirin yang sama: Dijkstra dan A* Search. Dijkstra menjelajah ke segala arah berdasarkan jarak sejauh ini, sedangkan A* memakai heuristik untuk mengarah ke tujuan sehingga umumnya mengunjungi lebih sedikit sel. Visualisasi menampilkan kedua penelusuran berdampingan dengan hitungan cells visited sebagai ukuran efisiensi.

Contoh kasus

Membandingkan mesin routing peta digital untuk memilih algoritma tercepat saat menghitung rute pengantaran ojek online.

Silabus

Membandingkan algoritma pencari jalur berdampingan di labirin yang sama menunjukkan kapan tiap algoritma paling cocok dipakai.

Tujuan Belajar

·Memahami perbedaan cara BFS, Dijkstra, dan A* menjelajahi peta
·Menjelaskan kapan bobot dan heuristik memengaruhi pilihan algoritma
·Menerapkan perbandingan untuk memilih algoritma rute yang tepat

Cara Kerja

·Jalankan dua algoritma pada labirin identik secara bersamaan
·BFS optimal saat semua langkah berbobot sama
·Dijkstra menimbang biaya tiap jalur, cocok untuk graf berbobot
·A* menambah heuristik agar pencarian mengarah ke tujuan
·Bandingkan jumlah sel yang dikunjungi dan total biaya sebagai ukuran efisiensi

Prasyarat

·Breadth-First Search
·Dijkstra
·A* Search

Contoh Nyata

·Memilih BFS atau Dijkstra untuk peta game tergantung biaya tiap petak
·Menentukan mesin rute tercepat untuk pengantaran ojek online
·Menguji algoritma navigasi mana yang paling hemat untuk aplikasi maps

Kompleksitas BFS O(V+E); Dijkstra O((V+E) log V); A* O(E) terarah