Tugas · Pertemuan 2

Maze 1 ke 64, tujuh cara jalan

Jalan kaki dari kotak 1 ke kotak 64. Kotak abu-abu adalah tembok, tidak boleh dilewati. Tiap pindah ke tetangga = 1 langkah. Pilih tab, tekan Step. Maze-nya sama; yang berubah hanya cara memilih kotak berikutnya.

Istilah

Dari kotak 2 ada dua arah: kanan ke 3, bawah ke 10. Kanan kelihatan lebih dekat ke 64, tapi nabrak tembok dan harus muter (16 langkah). Bawah lebih belok, totalnya 14. Tiap algoritma memilih arah dengan aturan sendiri.

d
Depth: berapa kali sudah geser dari 1. Lewat 1→2→10, d = 2. BFS baca d.
g
Cost yang sudah dibayar dari 1. Di maze ini tiap geser = 1, jadi g = d. Di graph S–Z, g bisa lebih besar dari d.
h
Tebakan sisa jarak ke 64, tembok diabaikan. Dari 1: 7 kanan + 7 bawah = 14.
f
g + h. Kalau tebakan tepat, total jalan segini. A* buka f terkecil.
frontier
Daftar kotak kandidat yang belum dibuka. Bukan path yang sedang dilalui.
buka
Berdiri di satu kotak, lihat tetangganya, masukkan ke frontier.

Tujuh algoritma

Loop-nya sama: buka satu kotak, masukkan tetangga. Yang beda: siapa yang dipilih.

BFS
Queue: habisi d=1 baru d=2. Path 14, buka 41 kotak. Pakai kalau tiap geser harganya sama. Satu level utuh harus disimpan.
DFS
Stack: satu lorong sampai buntu. Dari 2 masuk 3, path 16. Hemat memory, tidak jamin terpendek.
Hill
Dari kotak sekarang ambil h terkecil, yang kalah dibuang. Di 32, h harus naik ke 31, macet. Hemat, tidak ada cadangan.
Best-First
Buka h terkecil di frontier, g tidak dibaca. Di 2 ambil 3, bukan 10. Path 16. Cepat kalau tebakan bagus; di sini tertipu jalur kanan.
A*
Buka f = g+h terkecil. 31 f=16, 35 f=14, jadi masuk 10. Path 14, buka 27 kotak. Path terpendek asal h tidak melebih-lebihkan.
B&B
Buka g terkecil, semua rute disimpan. Setelah 64 ketemu, rute yang lebih mahal dibuang. Path 14, buka 41. Tidak butuh h, boros memory.
DP
Seperti B&B, tapi tiap kotak hanya satu kedatangan termurah. Path 14, tetap buka 41 karena tidak pakai h. Di maze ini sama dengan BFS.
1. Pilih tab Aturan pilih yang berubah. Maze-nya tidak.
2. Tekan Step Satu tekan = buka satu kotak, lalu masukkan tetangganya.
3. Baca angka kecil BFS/DFS: d. Hill/Best: h. A*: f. B&B/DP: g.

Breadth-First Search

Siap
  • Baru dibuka
  • Berikutnya
  • Path
  • Sudah dibuka
  • Tembok

Langkah 0 / 0

Pohon hierarki · BFS

Akar = 1. Anak = kotak yang dimasukkan waktu induknya dibuka. Garis hijau = path yang dipakai algoritma ini. Ganti tab untuk pohon algoritma lain.

Slide assignment · Lab graph S–Z · Walkthrough