State Search Algorithms

• State search = algoritma mencari solusi potensial; langkah problem: definisi state space, initial state, goal state, dan aturan transisi.
• Contoh river crossing: state (Wolf, Goose, Rice, Farmer) dengan bit 1=origin; initial (1,1,1,1), goal semua di seberang; state ilegal dibuang dari graph.
• Representasi hierarkis: root → successor → leaf; search tree vs state graph (contoh graph S–Z dengan cost edge dan heuristic h(n)).
• BFS: FIFO, optimal hop jika edge uniform; kelebihan tidak deadlock, kelemahan boros memori.
• DFS: LIFO/stack, hemat memori; risiko local optima dan path suboptimal.
• Hill climbing & Best-First: pakai h(n) estimasi jarak ke goal; cepat tapi bisa stuck di local optima.
• A*: f(n)=g(n)+h(n); lebih baik dari best-first karena memasukkan cost aktual; B&B dan DP mencari optimum global (DP lebih efisien memori dengan reuse partial path).
• Aplikasi: games, robot navigation (Manhattan distance), 8-puzzle, TSP, map navigation (Romania step costs).

Loop search yang sama di slide dan lab: frontier, pilih node, cek goal, expand tetangga.

flowchart LR
  Start["Frontier = initial"]
  Pick["Pilih node (aturan algoritma)"]
  Goal{"Goal?"}
  Expand["Expand tetangga"]
  Done["Selesai"]
  Start --> Pick --> Goal
  Goal -->|ya| Done
  Goal -->|tidak| Expand --> Pick