Pertemuan 2 · State Search & Algorithms

Tujuh search algorithm di graph yang sama

Start S, goal Z. Pilih tab, tekan Step, baca panel kanan. Maze tugas 1–64 ada di tugas maze. Loop masih kabur: walkthrough.

1. Pilih tab Graph-nya sama. Yang berubah: siapa yang dibuka berikutnya.
2. Tekan Step Kuning = baru dibuka. Biru = masih antre. Hijau = path.
3. Baca g, h, f g sudah dibayar. h sisa perkiraan. f = g+h.

Breadth-First Search

Siap
  • Current
  • Frontier
  • Expanded
  • Path
  • Goal Z
  • Discarded

Langkah 0 / 0

Contoh Python

Baris kuning = yang sedang dijalankan. Silakan copy dan coba di editor. 

            


            

                
Pengingat state space

                

                    State adalah snapshot lengkap dunia. Puzzle petani memakai
                    (Wolf, Goose, Rice, Farmer)
                    dengan initial (1,1,1,1) dan goal
                    (0,0,0,0). Petani menyeberang paling banyak satu barang.
                    Wolf+goose atau goose+rice tidak boleh tertinggal tanpa petani.
                

                

                    Search: coba urutan state sampai ketemu goal. Expand membuka
                    sebuah node dan melihat tetangganya. Frontier adalah antrean
                    kandidat yang belum dibuka. Tiap algorithm beda di siapa yang dibuka berikutnya,
                    dan itu yang membentuk path.
                

                

                    Di graph ini, path dari S ke Z. Angka pada edge
                    adalah travel cost. Angka kecil di bawah node adalah heuristic
                    h(n), perkiraan sisa cost ke Z.
                    Hop (jumlah langkah) dan cost (jumlah bobot) adalah dua angka berbeda.
                

            


            

                
Ringkasan 7 algoritma

                
Siapa yang dibuka berikutnya

                

                    Setiap tab melakukan gerakan yang sama: expand satu node,
                    masukkan tetangganya ke frontier. Aturan pilih node itulah yang membentuk path.
                

                

                    Tiga angka di graph:
                    g cost yang sudah dibayar dari S
                    h perkiraan sisa cost ke Z
                    f = g + h, perkiraan total
                

                

                    

                        
Tidak pakai g atau h

                        
    
                            
  • BFS memakai queue. Node yang menunggu paling lama dibuka dulu, jadi graph diurai per hop. Di sini: S → A → D → Z (3 hop, g=12).
    • 
                            
  • DFS memakai stack. Node yang baru masuk dibuka dulu, jadi satu cabang diikuti sampai buntu. Memory kecil. Path pertama tidak dijamin pendek atau murah.
    • 
                        

                    

                    

                        
Pakai h

                        
    
                            
  • Hill Climbing dari posisi sekarang mengambil tetangga dengan h terkecil dan membuang yang lain. Bisa macet di local optimum.
    • 
                            
  • Best-First menyimpan semua kandidat dan membuka h terkecil. g tidak dihitung, jadi node bisa kelihatan dekat padahal jalannya sudah mahal.
    • 
                        

                    

                    

                        
Pakai g

                        
    
                            
  • A* membuka f = g + h terkecil. Jika h tidak melebih-lebihkan, solusi pertama adalah yang termurah. Di sini: S → B → C → E → Z (4 hop, g=10).
    • 
                            
  • B&B membuka g terkecil dan menyimpan semua rute. Begitu Z ketemu, path dengan g ≥ bound di-prune.
    • 
                            
  • DP sama seperti B&B, tapi ke tiap node hanya menyimpan kedatangan termurah.
    • 
                        

                    

                

                

                    BFS menjawab sedikit hop: S → A → D → Z (3 hop, g=12).
                    A* / B&B / DP menjawab termurah: S → B → C → E → Z (4 hop, g=10).
                

                

                    Maze assignment 1–64 memakai loop yang sama:
                    buka tugas maze.