Pascasarjana Diary

Pertemuan 2 · State Search & Algorithms

Cara tujuh algoritma memilih node berikutnya

Slide pdf dan lab memakai graph yang sama: start S, goal Z. Setiap tab menjalankan loop yang sama. Yang berubah hanya siapa yang dibuka berikutnya.

Buka lab Buka PDF

State space, dari slide 3–8

Slide membuka dengan definisi masalah: sebutkan state, initial state, goal state, dan aturan pindah. Baru sesudah itu ada algoritma.

Kasusnya petani, serigala, angsa, dan beras. Perahu muat petani plus paling banyak satu barang. Serigala tidak boleh ditinggal bersama angsa. Angsa tidak boleh ditinggal bersama beras.

State ditulis (Wolf, Goose, Rice, Farmer). Angka 1 berarti masih di origin. Awal (1,1,1,1). Goal (0,0,0,0): semua sudah di seberang.

Ada 24 = 16 kombinasi. Buang yang ilegal (serigala+angsa atau angsa+beras tanpa petani), sisanya state yang boleh dikunjungi. Contoh langkah legal pertama: petani membawa angsa. Origin jadi (1,0,1,0), destination (0,1,0,1). Itu angka yang sama dengan slide 5.

Setelah state digambar sebagai titik dan langkah legal sebagai garis, teka-teki itu jadi mencari path. Chess, navigasi robot, dan lab S–Z memakai kerangka yang sama.

Graph di lab, dari slide 9 dan 22

Kasus kedua di PDF adalah graph S–A–B–C–D–E–F–Z. Lab memakai graph itu, undirected, dengan cost di edge dan heuristic h(n) di node. h adalah perkiraan sisa cost ke Z, tabel yang sama dengan slide 22.

4 3 5 3 3 5 2 4 5 2 5 Sh=10 Ah=8 Bh=6 Dh=4.5 Ch=3.7 Fh=2 Eh=2 Zh=0
Node S A B C D E F Z
h(n) 10 8 6 3,7 4,5 2 2 0
g cost yang sudah dibayar dari S (jumlah bobot edge) h perkiraan sisa cost ke Z f = g + h, perkiraan total path sampai goal

Hop (berapa kali pindah) dan g (berapa yang sudah dibayar) adalah dua pertanyaan. BFS menjawab hop. A*, B&B, dan DP menjawab g termurah.

Loop yang sama di setiap tab

Buku teks membagi search jadi uninformed (tanpa petunjuk ke goal) dan informed (pakai heuristic). Lab menaruh keduanya di loop yang sama.

  1. Frontier mulai berisi S.
  2. Pilih satu node menurut aturan algoritma.
  3. Kalau node itu Z, berhenti.
  4. Kalau bukan, expand: lihat tetangga, masukkan kandidat baru ke frontier, ulangi.

Frontier adalah antrean kandidat yang belum dibuka. Expand membuka sebuah node. Aturan pilih itulah yang membentuk path. Slide 7 menggambar ini sebagai pohon: root, successor, leaf.

Breadth-First Search

next = depan queue (FIFO) · buka per hop

BFS memilih node paling dangkal di frontier. Implementasinya queue: yang masuk lebih dulu dikerjakan lebih dulu. Cost edge dan h tidak dibaca. Berkeley CS188: BFS optimal untuk jumlah langkah, dan hanya optimal untuk cost jika semua edge sama mahalnya. Di graph ini edge tidak sama, jadi path-nya pendek dalam hop dan mahal dalam g.

  1. Expand S. Queue: A, B (keduanya depth 1).
  2. Expand A. Tetangga baru: D. Queue: B, D.
  3. Expand B. Tetangga baru: C. Queue: D, C.
  4. Expand D (depth 2). F dan Z masuk belakang (depth 3). Queue: C, F, Z.
  5. C dan F dikerjakan dulu karena mereka sudah antre. Baru kemudian Z.

Path lab: S → A → D → Z · 3 hop · g = 4+3+5 = 12

Slide 13: solusi pasti ketemu jika ada, memory boros karena satu level utuh disimpan. Z sudah kelihatan di langkah 4, tapi BFS tetap menghabiskan sisa depth 2.

Lab, langkah 4 (Z baru masuk queue) · langkah 7 (goal)

Depth-First Search

next = puncak stack (LIFO) · satu cabang sampai buntu

DFS memilih node terdalam. Implementasinya stack: yang baru di-push dikerjakan dulu. Lab menambahkan tetangga dalam urutan abjad, jadi dari S yang di-push terakhir adalah B, dan B jadi puncak.

  1. Expand S. Stack: A di bawah, B di puncak.
  2. Pop B. A tetap menunggu. Push C. Puncak: C.
  3. Pop C. Push D lalu E. Puncak: E.
  4. Pop E. Push Z. Pop Z. Selesai.

Path lab: S → B → C → E → Z · 4 hop · g = 10

Angka 10 di graph ini kebetulan bagus. DFS tidak membandingkan A yang masih di stack. Slide 16: memory kecil, bisa tersesat di cabang yang dalam. Fewest hops dan cost termurah tidak dijamin.

Lab, langkah 2 (A tertinggal di stack) · langkah 5 (goal)

Hill Climbing

dari current saja, pindah ke tetangga dengan h terkecil

Slide 17 mengutip AIMA: seperti mendaki Everest dalam kabut, lalu lupa jalan yang sudah dibuang. Hill climbing adalah local search. Dari posisi sekarang ia melihat tetangga, mengambil h terkecil, dan membuang sisanya. Tidak ada frontier cadangan.

  1. Dari S (h=10): B h=6, A h=8. Ambil B. A dibuang.
  2. Dari B (h=6): C h=3,7, A h=8. Ambil C. A dibuang lagi.
  3. Dari C (h=3,7): E h=2, D h=4,5. Ambil E. D dibuang.
  4. Dari E (h=2): Z h=0. Ambil Z.

Path lab: S → B → C → E → Z · g = 10

Di graph ini greedy walk sampai Z. Slide 18 dan 21: kalau semua tetangga punya h lebih besar atau sama, algoritma berhenti di local optimum. Cabang yang sudah dibuang tidak bisa dipanggil lagi.

Lab, langkah 1 (A tidak disimpan) · langkah 4 (goal)

Best-First Search

f(n) = h(n) · greedy / heuristic search

Slide 22 menandai ini sebagai greedy search. Russell & Norvig: expand node yang kelihatannya paling dekat ke goal. Bedanya dengan Hill Climbing: kandidat yang tidak diambil tetap di frontier. g tidak masuk urutan, jadi rute yang sudah mahal tetap bisa menang giliran jika h-nya kecil.

  1. Expand S. Frontier menurut h: B (6), A (8).
  2. Expand B. Masuk C (3,7). A tetap menunggu.
  3. Expand C. Masuk E (2) dan D (4,5). Urutan: E, D, A.
  4. Expand E. Masuk Z (0). Z menang giliran.

Path lab: S → B → C → E → Z · g = 10

A (g=4, h=8) masih ada di frontier saat Z ketemu. Best-First tidak pernah memakai g=4 itu untuk menunda cabang B. Di graph lain, itu bisa memilih jalan yang kelihatan dekat dan ternyata mahal.

Lab, langkah 3 (A masih antre) · langkah 5 (goal)

A* Search

f(n) = g(n) + h(n) · informed search

Slide 28–29: yang diminimalkan adalah panjang path utuh, bukan jarak dari kepala path ke Z. AIMA dan Berkeley CS188 menulis rumus yang sama. g sudah dibayar. h menaksir sisa. f menaksir total. Jika h tidak melebih-lebihkan (admissible), expand Z yang pertama adalah path termurah.

Aritmetika di lab mengikuti slide 30:

  1. S: 0+10 = 10. Expand S. Anak: B 3+6 = 9, A 4+8 = 12.
  2. Min f adalah B (9). Expand B. C: 3+3+3,7 = 9,7. Lewat B ke A: g=8, sudah ada g=4, dibuang.
  3. C (9,7) mengalahkan A (12). Expand C. E: 6+2+2 = 10. D: 6+5+4,5 = 15,5.
  4. E (10) mengalahkan A (12). Expand E. Z: 8+2+0 = 10.
  5. Z (10) mengalahkan A (12) dan D (15,5). Goal.

Path lab: S → B → C → E → Z · 4 hop · g = 10

BFS memilih 3 hop dengan g=12. A* memilih 4 hop dengan g=10. A (f=12) ditunda karena perkiraan totalnya lebih mahal dari path lewat E.

Lab, langkah 2 (A via B dibuang, f B=9 vs A=12) · langkah 5 (goal)

Branch and Bound

buka g terkecil · simpan setiap partial path · prune by bound

Slide 33–35: B&B membuka rute yang sudah bayar paling sedikit, dan menyimpan lebih dari satu jalan ke node yang sama. Heuristic tidak dipakai. Setelah sebuah path sampai Z, cost-nya jadi bound. Path unfinished dengan g ≥ bound di-prune, karena melanjutkannya hanya menambah cost.

  1. Expand S (g=0). Frontier: B g=3, A g=4.
  2. Expand S→B (g=3). Sekarang ada dua jalan ke A: S→A (g=4) dan S→B→A (g=8). Keduanya disimpan.
  3. Berikutnya S→A (g=4), lalu S→B→C (g=6), lalu S→A→D (g=7).
  4. S→B→C→E (g=8) menghasilkan Z dengan g=10. Bound = 10. Sisa path dengan g ≥ 10 dibuang, termasuk S→A→D→Z (g=12).

Path lab: S → B → C → E → Z · g = 10 · global optimum

Slide 35: selalu menemukan global optimum; memory boros karena partial path ke node yang sama disimpan berkali-kali. Di langkah 2 lab, dua entri A kelihatan bersamaan.

Lab, langkah 2 (dua path ke A) · langkah 9 (bound 10, prune)

Dynamic Programming

buka g terkecil · satu kedatangan termurah per node

Slide 36–38: DP adalah B&B plus satu aturan. Sisa jalan dari D ke Z tidak peduli bagaimana kita sampai D. Kalau sudah di D dengan g=7, datang lagi dengan g=11 memulai sisa perjalanan dari posisi kalah, jadi 11 dibuang. Literatur sering menyebut aturan yang sama uniform-cost search atau Dijkstra: satu best g per node.

  1. Expand S. Catat B=3, A=4.
  2. Expand B (g=3). Lewat B ke A menghasilkan g=8. 8 > 4, dibuang. B&B tadi menyimpan 8.
  3. Expand A (g=4). B sudah settled, skip. Catat D=7.
  4. Expand C (g=6). Lewat C ke D = 11. 11 > 7, dibuang.
  5. Expand E (g=8). Z masuk dengan g=10, mengalahkan Z via D (g=12).

Path lab: S → B → C → E → Z · g = 10 · global optimum

Slide 38: hasil tetap optimum, memory lebih kecil karena tiap node disimpan sekali. Harganya: harus mengingat best cost setiap node yang sudah dicapai.

Lab, langkah 2 (A via B dibuang) · langkah 7 (goal)

Yang perlu diingat dari graph ini

BFS menjawab sedikit hop: S → A → D → Z (3 hop, g=12).

A*, B&B, dan DP menjawab termurah: S → B → C → E → Z (4 hop, g=10).

Hill Climbing dan Best-First mengikuti h dan di graph ini kebetulan sampai path yang sama dengan A*. Bedanya: Hill membuang tetangga yang kalah, Best-First menyimpannya, keduanya tidak menjamin g minimum.

DFS juga mendarat di path g=10, karena cabang B ada di puncak stack. Itu urutan tetangga, bukan jaminan algoritma.

Buka tab, tekan Step, dan cocokkan antrean di panel kanan dengan daftar di atas. Graph-nya tidak berubah. Aturan pilih yang berubah.

Mulai dari tab BFS