Simulic
Bahasa Indonesia

Mencari jalan di labirin – BFS, DFS, dan A*

InformatikaAlgoritma dan pemecahan masalahUsia 17–18

Memuat…

Bagikan Laporkan masalah

Sebuah kisi dengan dinding, satu sel awal, dan satu sel tujuan. Siswa memilih pencarian melebar (BFS, memakai antrean), pencarian mendalam (DFS, memakai tumpukan), atau A*, lalu mengamati setiap langkah: sel yang menunggu diberi nomor sesuai urutan diambil, sel yang sudah dijelajahi diwarnai menurut jaraknya, dan akhirnya jalan yang ditemukan muncul. Gambar atau hapus dinding, geser titik awal dan tujuan, buat labirin baru, lalu bandingkan jumlah sel yang dijelajahi dan panjang jalan setiap algoritma.

Pelajaran: Algoritma pencarian jalan pada kisi: pencarian melebar (BFS), pencarian mendalam (DFS), dan A*

Yang ditunjukkan

Labirin dimodelkan sebagai kisi sel; setiap langkah menuju sel tetangga di atas, bawah, kiri, atau kanan, dan setiap langkah berbiaya sama. Pencarian melebar menyimpan sel yang menunggu dalam antrean: ia menjelajahi semua sel berjarak satu langkah, lalu dua langkah, sehingga saat pertama kali mencapai tujuan ia sudah memiliki jalur terpendek. Pencarian mendalam memakai tumpukan dan mengikuti satu arah sampai buntu, sehingga jalannya sering lebih panjang. A* mengurutkan sel menurut f = g + h, dengan h adalah jarak Manhattan ke tujuan.

Cara menggunakan

Pilih BFS, DFS, atau A* lalu tekan Per langkah untuk mengikuti sel bernomor yang menunggu, atau Jalankan untuk melihat animasi. Bandingkan tabel hasil setelah setiap percobaan. Gunakan Gambar dinding, Hapus dinding, Atur awal, dan Atur tujuan untuk mengubah kisi, atau pilih Jenis kisi lalu tekan Kisi baru.

Parameter yang dapat diubah

  • Algoritma BFS – pencarian melebar, DFS – pencarian mendalam, A* – dipandu perkiraan jarak
  • Jenis kisi Labirin berputar, Rintangan acak, Kisi kosong
  • Jumlah kolom kisi 11–41 sel
  • Dinding tambahan yang dibuang (labirin) 0–60 %
  • Kepadatan rintangan 0–45 %
  • Kecepatan 1–100 langkah/detik

Pertanyaan untuk dijelajahi

  1. Mengapa jalan yang ditemukan BFS selalu merupakan jalur terpendek, sedangkan jalan DFS sering tidak?
  2. Pada kisi kosong, algoritma mana yang menjelajahi sel paling sedikit, dan mengapa?
  3. Dapatkah Anda membuat labirin tempat DFS mencapai tujuan dengan menjelajahi lebih sedikit sel daripada BFS?

Simulasi terkait