Search Algorithms dalam Kecerdasan Buatan (AI)

📑 Daftar Isi

• 1. Pendahuluan Search Algorithms
• 2. Mendefinisikan Search Problem
• 3. Uninformed Search (Blind Search)
• 4. Informed Search (Heuristic Search)
• 5. A* Search Algorithm
• 6. Merancang Heuristic Functions
• 7. Perbandingan Algoritma
• 8. Aplikasi Praktis

Apa Itu Search Algorithms dalam AI?

Search Algorithms adalah metode fundamental dalam kecerdasan buatan yang digunakan untuk menemukan solusi optimal dalam ruang masalah (state space) yang sangat besar. Algoritma pencarian memungkinkan AI untuk menjelajahi berbagai kemungkinan dan menemukan jalur terbaik dari state awal menuju state tujuan.

🎯 Definisi Search Problem

Search Problem adalah permasalahan yang didefinisikan oleh:

• State Space: Himpunan semua state yang mungkin
• Initial State: State awal dari mana pencarian dimulai
• Actions: Operasi yang dapat dilakukan untuk berpindah antar state
• Successor Function: Fungsi yang menentukan state baru dari state saat ini dan action yang diambil
• Goal Test: Fungsi untuk mengecek apakah suatu state adalah state tujuan
• Path Cost: Biaya untuk melakukan suatu action (opsional)

State Space vs Search Tree

Penting untuk memahami perbedaan antara State Space Graph dan Search Tree:

State Space Graph

Representasi abstrak dari semua state dan transisi yang mungkin. Setiap node adalah state, dan setiap edge adalah action.

• Nodes = States
• Edges = Actions
• State bisa muncul sekali saja

Search Tree

Struktur yang dikonstruksi saat melakukan pencarian. Setiap node adalah entire path dalam state space graph.

• Nodes = Paths
• Children = Expansions
• State bisa muncul berulang kali

💡 Insight Penting: Kita konstruksi state space dan search tree secara on-demand (sesuai kebutuhan) dan berusaha mengonstruksi sesedikit mungkin untuk efisiensi. Ini karena state space bisa sangat besar (eksponensial).

Mendefinisikan Search Problem

Contoh 1: Pacman

Mari kita lihat bagaimana problem Pacman dapat dimodelkan sebagai search problem:

1Problem: Eat All Dots

• States: {(x,y), dot booleans} - posisi Pacman dan status setiap dot
• Actions: North, South, East, West (NSEW)
• Successor: Update location dan possibly a dot boolean
• Goal test: Apakah semua dots sudah dimakan (dots all false)

2Problem: Go to Destination

• States: (x,y) location
• Actions: NSEW
• Successor: Update location only
• Goal test: is (x,y) = END

Contoh 2: Symbolic Integrator (SAINT, 1961)

SAINT adalah salah satu program AI pertama yang menggunakan search untuk memecahkan masalah kalkulus:

• States: Ekspresi simbolik matematika
• Actions: "Common techniques" dalam kalkulus
• Successor: Ekspresi baru setelah applying technique
• Goal test: Apakah ekspresi sudah dalam "standard form"

Contoh 3: Machine Translation

Menerjemahkan "你好嗎" ke bahasa Inggris:

• States: Current word sequence
• Actions: The next word to add
• Successor: Concatenation of current sequence and next word
• Goal test: Apakah current sequence memiliki makna yang sama dengan "你好嗎"

Uninformed Search (Blind Search)

Uninformed Search atau blind search adalah strategi pencarian yang tidak memiliki informasi tambahan tentang state selain yang diberikan dalam definisi problem. Algoritma hanya tahu cara membedakan goal state dari non-goal state.

General Framework untuk Search

Semua algoritma search mengikuti framework umum yang sama dengan membagi nodes menjadi 3 kelompok:

🔴 Expanded

Nodes yang sudah dieksplorasi dan successornya sudah digenerate.

🟡 Frontier

Nodes yang sudah ditemukan tapi belum dieksplorasi. Ini adalah "garis depan" pencarian.

⚪ Unreached

Nodes yang belum ditemukan sama sekali.

Frontier ← { initial_state } Reached ← { initial_state } While Frontier is not empty: Pop a node s from Frontier // Cara memilih membedakan algoritma If s is a goal state, then terminate For all action a: s' ← successor(s, a) If s' not in Reached: Push s' to Frontier Reached[s'] ← True

🎯 Kunci Utama: Perbedaan utama antar algoritma uninformed search terletak pada bagaimana kita memilih node dari Frontier untuk di-expand. Ini disebut search strategy.

1. Depth-First Search (DFS)

Strategi DFS

Pop the NEWEST node from Frontier (LIFO - Last In First Out)

DFS menjelajahi satu cabang secara mendalam sebelum backtrack dan mencoba cabang lain.

Frontier ← { initial_state } // Stack (LIFO) While Frontier is not empty: Pop the newest node s from Frontier For all action a: s' ← successor(s, a) If s' not in Reached: If s' is a goal state, terminate Push s' to Frontier Reached[s'] ← True

✅ Kelebihan DFS

• Memory efficient: Hanya menyimpan nodes di current path
• Space complexity: O(bm) dimana b = branching factor, m = maximum depth
• Cepat jika solusi ada di cabang pertama

❌ Kekurangan DFS

• Not optimal: Tidak menjamin solusi terpendek
• Not complete: Bisa stuck di infinite path
• Time complexity: O(b^m) - bisa sangat lambat
• Bisa explore cabang yang salah sangat dalam

Memory-Efficient DFS

DFS bisa dibuat lebih memory-efficient dengan menghilangkan pengecekan "Reached":

// Memory Efficient DFS - untuk Acyclic Graphs Frontier ← { initial_state } While Frontier is not empty: Pop the newest node s from Frontier For all action a: s' ← successor(s, a) If s' is a goal state, terminate Push s' to Frontier // Untuk Cyclic Graphs: cek apakah s' bukan ancestor dari s

2. Breadth-First Search (BFS)

Strategi BFS

Pop the OLDEST node from Frontier (FIFO - First In First Out)

BFS menjelajahi semua nodes di level tertentu sebelum pindah ke level berikutnya.

Frontier ← { initial_state } // Queue (FIFO) While Frontier is not empty: Pop the oldest node s from Frontier For all action a: s' ← successor(s, a) If s' not in Reached: If s' is a goal state, terminate Push s' to Frontier Reached[s'] ← True

✅ Kelebihan BFS

• Complete: Selalu menemukan solusi jika ada
• Optimal: Menemukan solusi dengan depth terkecil (jika semua actions memiliki cost sama)
• Systematic exploration: Level by level

❌ Kekurangan BFS

• Memory intensive: Menyimpan semua nodes di current level
• Space complexity: O(b^d) dimana d = depth of solution
• Time complexity: O(b^d)
• Lambat untuk deep solutions

3. Iterative Deepening Search (IDS)

IDS menggabungkan space advantage dari DFS dengan time advantage dan completeness dari BFS:

Strategi IDS

1. Run DFS dengan depth limit 1. Jika tidak ada solusi...
2. Run DFS dengan depth limit 2. Jika tidak ada solusi...
3. Run DFS dengan depth limit 3. Dan seterusnya...

💡 Efisiensi IDS: Meskipun terlihat wasteful karena re-explore nodes, IDS sebenarnya efisien karena sebagian besar work terjadi di level terakhir. Dengan branching factor 10 dan solution di depth 5:

• BFS: 10 + 100 + 1,000 + 10,000 + 100,000 = 111,110 nodes
• IDS: 50 + 400 + 3,000 + 20,000 + 100,000 = 123,450 nodes

Overhead hanya sekitar 10%!

4. Uniform Cost Search (UCS) / Dijkstra's Algorithm

Ketika actions memiliki different costs, kita memerlukan algoritma yang mempertimbangkan path cost, bukan hanya depth.

Strategi UCS

Pop the node with SMALLEST cumulative path cost g(s) from Frontier

UCS menjamin solusi dengan cost terendah (optimal).

Frontier ← { initial_state } // Priority Queue by g(s) g(initial_state) ← 0 While Frontier is not empty: Pop node s with smallest g(s) from Frontier If s is a goal state, then terminate For all action a: s' ← successor(s, a) If s' not in Reached: Push s' to Frontier Reached[s'] ← True g(s') ← min( g(s'), g(s) + cost(s, a) )

✅ Kelebihan UCS

• Complete: Selalu menemukan solusi
• Optimal: Menemukan solusi dengan cost minimum
• Handles variable costs: Bekerja dengan action costs yang berbeda

❌ Kekurangan UCS

• Explores in all directions: Tidak fokus ke goal
• Space complexity: O(b^(C*/ε)) dimana C* = optimal cost, ε = minimum cost
• Bisa lambat: Explore banyak nodes yang tidak perlu

🔍 Late vs Early Goal Test:

• Early Goal Test: Check saat generate successor - lebih cepat terminate
• Late Goal Test: Check saat pop dari frontier - diperlukan untuk UCS agar optimal

Untuk cost-sensitive search seperti UCS, gunakan Late Goal Test untuk menjamin optimalitas!

Informed Search (Heuristic Search)

Informed Search menggunakan domain-specific knowledge untuk guide pencarian menuju goal secara lebih efisien. Knowledge ini diwakili oleh heuristic function.

🎯 Heuristic Function h(s)

Heuristic function h(s) adalah estimasi cost dari state s ke goal state terdekat.

• h(s) = 0 jika s adalah goal state
• h(s) > 0 untuk non-goal states
• h(s) adalah "educated guess" - tidak harus perfect
• Good heuristic = berkorelasi tinggi dengan true distance

Contoh Heuristic Functions

🗺️ Navigation

Straight-line distance (Euclidean distance) dari current location ke destination

h(s) = √((x₂-x₁)² + (y₂-y₁)²)

🧩 8-Puzzle

Number of misplaced tiles: Berapa banyak tiles yang tidak pada posisi goal

Manhattan distance: Σ |x₁-x₂| + |y₁-y₂| untuk semua tiles

1. Greedy Best-First Search

Strategi Greedy

Pop the node with SMALLEST h(s) from Frontier

Greedy search selalu memilih node yang "terlihat paling dekat" dengan goal menurut heuristic.

Frontier ← { initial_state } // Priority Queue by h(s) While Frontier is not empty: Pop node s with smallest h(s) from Frontier For all action a: s' ← successor(s, a) If s' not in Reached: If s' is a goal state, terminate Push s' to Frontier Reached[s'] ← True

✅ Kelebihan Greedy

• Sangat cepat jika heuristic bagus
• Langsung ke goal seperti nicely-guided DFS
• Memory efficient seperti DFS

❌ Kekurangan Greedy

• Not optimal: Tidak menjamin solusi terbaik
• Not complete: Bisa stuck di local minima
• Worst case: Seperti badly-guided DFS jika heuristic buruk

⚠️ Trade-off Greedy Search: Greedy sangat bergantung pada kualitas heuristic. Dengan heuristic yang bagus, bisa jauh lebih cepat dari UCS. Dengan heuristic yang buruk, bisa jauh lebih lambat.

A* Search: The Best of Both Worlds

A* Search menggabungkan kelebihan UCS (optimal, complete) dengan kelebihan Greedy Search (efficient, guided by heuristic).

Evaluation Function A*

f(s) = g(s) + h(s)

Dimana:

• g(s): Backward cost - actual cost dari start ke s
• h(s): Forward cost - estimated cost dari s ke goal
• f(s): Estimated total cost melalui s

Frontier ← { initial_state } // Priority Queue by f(s) = g(s) + h(s) g(initial_state) ← 0 While Frontier is not empty: Pop node s with smallest f(s) from Frontier If s is a goal state, then terminate For all action a: s' ← successor(s, a) If s' not in Reached: Push s' to Frontier Reached[s'] ← True g(s') ← min( g(s'), g(s) + cost(s, a) ) // Note: UCS adalah special case dari A* dengan h(s) = 0

Hubungan Antar Algorithms

Algorithm	Evaluation Function	Karakteristik
Uniform Cost Search	f(s) = g(s)	Hanya backward cost, explore ke semua arah
Greedy Best-First	f(s) = h(s)	Hanya forward estimate, langsung ke goal
A* Search	f(s) = g(s) + h(s)	Balance antara path cost dan goal proximity
Weighted A*	f(s) = g(s) + w·h(s)	w > 1: lebih greedy, w < 1: lebih uniform

Visualisasi: UCS vs A*

🎯 Perbedaan Area Eksplorasi

UCS: Explore dalam lingkaran konsentris dari start, mengabaikan goal direction

A*: Explore dalam bentuk elips yang stretched menuju goal, jauh lebih focused

A* bisa 10-100x lebih cepat dari UCS dengan heuristic yang bagus!

Optimalitas A*: Admissibility vs Consistency

Admissible Heuristic

Heuristic h adalah admissible jika:

0 ≤ h(s) ≤ h*(s)

Dimana h*(s) adalah true minimum cost dari s ke goal. Artinya, heuristic never overestimates.

Consistent (Monotonic) Heuristic

Heuristic h adalah consistent jika untuk semua s dan s':

h(s) ≤ h(s') + cost(s → s')

Ini adalah triangle inequality. Dan h(G) = 0 untuk goal state G.

📊 Teorema Optimalitas A*:

1. Jika h consistent: A* returns minimum-cost solution (selalu optimal)
2. Jika h admissible + tree: A* returns minimum-cost solution
3. Jika h consistent → h admissible (consistency lebih kuat)

Mengapa Admissibility Penting?

Admissibility memastikan bahwa nodes di shortest path akan di-expand sebelum goal:

Intuisi:

Untuk node A di optimal path ke goal G:

f(A) = g(A) + h(A) ≤ g(A) + h*(A) = cost(optimal path)

Sementara untuk suboptimal goal G₁ yang sudah di-reach:

f(G₁) = g(G₁) > cost(optimal path)

Karena f(A) ≤ f(G₁), node A akan di-expand dulu, sehingga optimal path ditemukan sebelum A* terminate di suboptimal goal.

Contoh: Admissible tapi Tidak Consistent

Perhatikan graph berikut:

Graph: S → A (cost 1), S → B (cost 1), A → C (cost 1), B → C (cost 2), C → G (cost 3)

Heuristic values: h(S)=2, h(A)=4, h(B)=1, h(C)=1, h(G)=0

Semua admissible (≤ true cost), tapi NOT consistent:
h(A)=4 > h(C)=1 + cost(A→C)=1, yaitu 4 > 2 ❌

Dalam kasus ini, dengan graph search biasa, A* mungkin menemukan suboptimal solution. Solusi:

• Tree search: Treat graph seperti tree (allow revisits)
• Perbaiki heuristic: Buat consistent

Merancang Heuristic Functions yang Baik

Sebagian besar pekerjaan dalam solving hard search problems adalah menciptakan good heuristics. Heuristic yang bagus dapat membuat perbedaan antara solve dalam seconds vs hours!

Prinsip Desain Heuristic

1. Relaxed Problems

Heuristic sering berasal dari solving relaxed version dari problem, dimana constraints dihilangkan.

2. Admissibility First

Pastikan heuristic admissible untuk guarantee optimalitas. Better: buat consistent.

3. Maximize h(s)

Dalam range admissible, higher h(s) is better - less nodes expanded.

4. Precomputation OK

Boleh precompute heuristic values jika membantu - one-time cost.

Contoh: 8-Puzzle Heuristics

8-Puzzle adalah classic benchmark untuk heuristics:

Heuristic	Nodes Expanded (4 steps)	Nodes Expanded (8 steps)	Nodes Expanded (12 steps)
UCS (h=0)	112	6,300	3,600,000
# Wrong Tiles	13	39	227
Manhattan Distance	12	25	73

🎯 Insight: Manhattan distance adalah heuristic yang lebih baik karena lebih informatif. Untuk dua heuristic admissible h₁ dan h₂, jika h₂(s) ≥ h₁(s) untuk semua s, maka h₂ dominates h₁ dan akan expand fewer nodes.

Teknik Membuat Heuristic

1. Relaxed Problem

Untuk 8-Puzzle:

• Relax "adjacent tiles": Tile bisa move ke mana saja → # misplaced tiles
• Relax "one tile per move": Bisa move beberapa tile sekaligus → Manhattan distance

2. Pattern Databases

Precompute exact cost untuk subset dari tiles, gunakan sebagai heuristic untuk full problem.

3. Linear Combination

Jika h₁, h₂, ..., hₙ admissible:

h(s) = max(h₁(s), h₂(s), ..., hₙ(s))

Juga admissible dan ≥ semua hᵢ!

4. Domain Knowledge

Untuk navigation: straight-line distance
Untuk robot motion planning: Euclidean distance ignoring obstacles
Untuk machine translation: unigram/bigram scores

Inadmissible Heuristics

Meskipun tidak optimal, inadmissible heuristics juga berguna:

• Bisa jauh lebih cepat dengan trade-off suboptimality kecil
• Weighted A* dengan w > 1 memberikan bounded suboptimality
• Berguna untuk very large problems dimana optimal solution not feasible

Perbandingan Lengkap Search Algorithms

Algorithm	Complete	Optimal	Time Complexity	Space Complexity
BFS	✅ Yes	✅ Yes (unit cost)	O(b^d)	O(b^d)
DFS	❌ No	❌ No	O(b^m)	O(bm)
IDS	✅ Yes	✅ Yes (unit cost)	O(b^d)	O(bd)
UCS	✅ Yes	✅ Yes	O(b^(C*/ε))	O(b^(C*/ε))
Greedy	❌ No	❌ No	O(b^m)	O(b^m)
A*	✅ Yes*	✅ Yes*	Exponential	Exponential

* A* complete dan optimal jika heuristic admissible
b = branching factor, d = depth of solution, m = maximum depth, C* = optimal cost, ε = minimum cost

Kapan Menggunakan Algoritma Mana?

Gunakan BFS Jika:

• Semua actions unit cost
• Solution shallow
• Space tidak masalah
• Butuh optimal solution

Gunakan DFS Jika:

• Space sangat terbatas
• Solusi deep
• Any solution acceptable
• Tree structure (no cycles)

Gunakan IDS Jika:

• Butuh optimal + complete
• Space terbatas
• Tidak tahu depth of solution
• Large branching factor

Gunakan UCS Jika:

• Variable action costs
• Butuh optimal solution
• Tidak ada good heuristic
• Space cukup available

Gunakan Greedy Jika:

• Ada good heuristic
• Speed > Optimality
• Approximate solution OK
• Huge state space

Gunakan A* Jika:

• Ada admissible heuristic
• Butuh optimal solution
• Want speed of Greedy
• This is usually best choice!

🏆 Winner dalam Most Cases: A* dengan good heuristic adalah champion untuk most practical problems. Kombinasi optimal + efficient membuatnya pilihan default dalam game AI, robotics, navigation, dan planning.

Aplikasi Praktis Search Algorithms

Search algorithms adalah workhorses dalam AI modern, digunakan di berbagai aplikasi:

🗺️ Navigation & Routing

• Google Maps: A* dengan traffic-aware heuristic
• Robot path planning: A* dalam configuration space
• Autonomous vehicles: Real-time replanning dengan D*

🎮 Game AI

• Pathfinding: A* untuk NPC movement
• Strategy games: Minimax dengan alpha-beta pruning
• Puzzle solving: IDA* untuk Rubik's cube, Sokoban

🤖 Robotics

• Motion planning: RRT + A* hybrid
• Task planning: Forward state space search
• Manipulation: Configuration space search

📦 Logistics & Scheduling

• Warehouse optimization: Path planning untuk robots
• Delivery routing: TSP dengan search heuristics
• Job scheduling: State space search dengan constraints

🧬 Computational Biology

• Protein folding: Search dalam conformation space
• Sequence alignment: Dynamic programming variant
• Drug design: Molecular docking search

💡 Other Applications

• Theorem proving: Search untuk proof
• Circuit design: Search untuk optimal layout
• Natural language: Parsing, machine translation

Kesimpulan

Search algorithms adalah fondasi essential dalam kecerdasan buatan. Dari uninformed methods seperti BFS dan DFS yang menjelajahi secara blind, hingga informed methods seperti A* yang menggunakan domain knowledge untuk guide pencarian, setiap algoritma memiliki trade-offs dan use cases yang tepat.

🎯 Key Takeaways

• Uninformed search (BFS, DFS, UCS) tidak menggunakan domain knowledge, hanya problem definition
• BFS optimal untuk unit costs, DFS memory-efficient tapi not optimal
• UCS (Dijkstra) optimal untuk variable costs, explore uniformly ke semua arah
• Informed search menggunakan heuristic h(s) untuk guide pencarian
• Greedy Best-First cepat tapi not optimal, bisa mislead oleh bad heuristic
• A* combines best of both: f(s) = g(s) + h(s) - optimal + efficient
• Admissible heuristic (h ≤ h*) guarantees A* optimality
• Consistent heuristic (triangle inequality) ensures monotonic f-values
• Good heuristic design adalah kunci - bisa 1000x speedup!
• Choice of algorithm bergantung pada problem properties dan constraints

Memahami search algorithms tidak hanya penting untuk academic purposes, tetapi juga fundamental untuk building intelligent systems yang dapat solve complex real-world problems. Dari navigation apps di smartphone Anda hingga autonomous robots dan game AI, search algorithms bekerja di balik layar untuk find optimal solutions efficiently.

Dengan framework yang solid dalam uninformed dan informed search, plus kemampuan merancang good heuristics, Anda sekarang memiliki toolkit powerful untuk tackle wide variety of AI problems!

🚀 Ready to Implement?

Search algorithms adalah skill praktis yang dapat langsung diimplementasikan.

"Cara terbaik untuk mempelajari algoritma pencarian adalah dengan menerapkannya sendiri."