Informed Search (Heuristic) &
Eksplorasinya
Chastine Fatichah
Departemen Teknik Informatika
September 2025
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Capaian Pembelajaran Matakuliah
Mahasiswa mampu menjelaskan, mengidentifikasi, merancang,
dan menerapkan intelligent agent untuk problem yang sesuai
dengan memanfaatkan algoritma pencarian yang meliputi
uninformed search, informed search, heuristic search,
adversarial search, serta algoritma search untuk Constraint
Satisfaction Problem
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Pokok Bahasan
Informed search strategies
• Heuristic
• Greedy Best-First Search
• A* Search
• Iterated Deepening A* (IDA)
• Recursive Best-first Search
(RBFS)
• Simplified Memory Bounded
A* (SMA)
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Informed Search
• Uninformed Search: menggenerate state baru, di cek apakah goal atau
tidak → kurang efisien
• Uniform Cost Search (UCS)
• Strategi: expand lowest path cost
• Kelebihan: complete and optimal
• Kekurangan: melakukan eksplorasi di semua arah dan tidak ada informasi
tentang lokasi goal
• Informed Search: menggunakan informasi tambahan → lebih efisien
• Heuristic function ➔ informasi estimasi menuju goal
• Best-First Search
• Greedy Best-First
• A*
• Iterated Deepening A* (IDA)
• Recursive Best-first Search (RBFS)
• Simplified Memory Bounded A* (SMA)
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Heuristics Function
• Fungsi Heuristik
▪ Sebuah fungsi yang mengestimasi
seberapa dekat state sekarang ke state
tujuan (goal)
▪ Dirancang untuk search problem tipe
tertentu
▪ Contoh: Manhattan distance, Euclidean
distance, … Heuristics
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Contoh: Fungsi Heuristik (Romania problem)
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
h(x)
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Contoh: Fungsi Heuristik (8-puzzles problem)
Start State Goal State
h(x): banyaknya angka yang salah penempatan berdasarkan state tujuan
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Tree-Search & Graph-Search Pseudocode
[Link]/informatika Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley Konsep Kecerdasan Artifisial EK234201
Greedy Best First Search
• Best First Search mengekspand node yang mendekati goal
• Evaluation Function h(n) (Heuristics)
➔ Estimasi cost dari state n ke goal state
• Misalnya, hSLD(n) = Straight-Line Distance (jarak lurus)
• Kasus secara umum:
• Best-first search langsung menuju goal (yang salah)
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Contoh: Romania problem
h(x)
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Contoh: Greedy Best First Search
(Romania problem)
Arad 366
253 374
329
Sibiu Zerind
Timisoara
366 176 380 193
Arad Fagaras Oradea Rimnicu Videa
253 0
Sibiu Buchares
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Greedy Best First Search
• Complete?
• Tidak, bisa terjadi looping, misal : Oradea sebagai goal : Iasi →
Neamt → Iasi → Neamt …
• Time?
• O(bm) namun dengan heuristik yang baik akan memberikan
perbaikan yang besar
• Space?
• O(bm) Setiap node disimpan dalam memory
• Optimal?
• Tidak, mestinya tidak melalui Fagaras untuk mencapai optimalnya
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
A* Search
• Ide : menghindari untuk expand path yang memerlukan
biaya besar
• Kombinasi UCS dan Greedy Search
• Evaluation Function : f(n) = g(n) + h(n)
• g(n) = Cost yang dicapai sampai di state n
• h(n) = Estimasi cost untuk sampai ke goal dari n
• f(n) = Estimasi total cost dari path n sampai goal
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Contoh: A* Search (Romania problem)
Arad 366 = 0 + 366
393 = 140 + 253 449 = 75 + 374
447 = 118 + 329
Sibiu Zerind
Timisoara
646 = 280 + 366 415=239+176 671=291+380413=220+193
Arad Fagaras Oradea Rimnicu Videa
417=317+100 553=300+253
591=338+253 450=450+0 526 = 366 + 160
Sibiu Buchares Craiova Pinesti Sibiu
Bucharest Sibiu Rimnicu Videa
418=418+0 591=338+253 450=450+0
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Apakah A* optimal?
h=6
1 A 3
S h=7
G h=0
• Tidak Berhasil jika actual goal cost < estimated goal cost
• Diperlukan estimasi cost yang kurang dari actual cost!
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Admissible Heuristic
• A* : admissible heuristic → tidak overestimate jika
• dimana adalah actual cost terkecil dari n ke goal
• h(n) >= 0 sehingga h(G) = 0 untuk goal G
• Contoh, hSLD(n) tidak overestimate terhadap jarak pada jalan
sebenarnya
• A* search → Optimal
[Link]/informatika Konsep Kecerdasan Artifisial EK234201)
Optimality of A* Tree Search
Asumsi:
• A adalah optimal goal node
• B adalah suboptimal goal node … …
• h is admissible
Claim:
A akan keluar dari fringe sebelum B
Proof:
• Jika B ada di fringe
• Beberapa ancestor n dari A ada di fringe juga
• Claim: n akan diexpand sebelum B Definition of f-cost
1. f(n) lebih kecil atau sama dengan f(A) Admissibility of h
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
h = 0 at a goal
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Optimality of A* Tree Search
Proof:
…
• Jika B ada di fringe
• Beberapa ancestor n dari A ada di fringe
juga
• Claim: n akan diexpand sebelum B
1. f(n) lebih kecil atau sama dengan f(A)
2. f(A) lebih kecil dari f(B)
B is suboptimal
h = 0 at a goal
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Optimality of A* Tree Search
Proof:
…
• Jika B ada di fringe
• Beberapa ancestor n dari A ada di fringe
juga
• Claim: n akan diexpand sebelum B
1. f(n) lebih kecil atau sama dengan f(A)
2. f(A) lebih kecil dari f(B)
3. n diexpand sebelum B
• Semua ancestor dari A diexpand sebelum B
• A diexpand sebelum B
• A* search adalah optimal
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
UCS vs A* Contours
Uniform-cost search expand semua
“directions”
Start Goal
A* search expand hanya arah menuju
goal, tetapi tetap memastikan
keoptimalan Start Goal
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
A* Search
• Complete ?
• Ya, selama jumlah node f <= f(G) terbatas
• Time ?
• Exponensial
• Space ?
• Setiap node disimpan dalam memory
• Optimal ?
• Ya
• A* mengekspand node-node dengan f(n) < C*
• A* mengekspand beberapa node dengan f(n)=C*
• A* tidak akan mengekspand node dengan f(n)>C*
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
A* Applications
• Video games
• Pathing / routing problems
• Resource planning problems
• Robot motion planning
• Language analysis
• …
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Konsistensi Fungsi Heuristik
• Fungsi Heuristic h(n) dikatakan konsisten jika setiap node n dan setiap successor n’
dari n yang digenerate aksi a, maka estimasi cost dari n sampai ke goal tidak lebih
besar dari cost sampai step n’ ditambah estimasi cost n’ ke goal
h(n) <= c(n,a,n’) + h(n’)
• Jika h(n) konsisten maka nilai dari f(n) melalui suatu path tidak berkurang
f(n’) = g(n’)+h(n’)
= g(n) + c(n,a,n’) + h(n’)
>= g(n) + h(n)
= f(n)
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Contoh: 8-puzzles
Actions
Start State Goal State
• Berapa banyak state? Rata-rata ➔ b = 3, d =22
• Apa saja aksinya?
• Berapa banyak successors dari start state? 4
• Bagaimana menentukan cost?
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Contoh: 8-puzzles I
• Heuristik: banyaknya kotak yang salah penempatan
• Mengapa admissible?
• h(start) = 8
Start State Goal State
[Link]/informatika Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
Konsep Kecerdasan Artifisial EK234201
Contoh: 8-puzzles II
• Heuristik: Manhatan distance → jumlah jarak masing-masing
kotak ke tujuan
• Mengapa admissible?
• h(start) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18
Start State Goal State
[Link]/informatika Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
Konsep Kecerdasan Artifisial EK234201
Informed Search Strategies
• Greedy Best-First
• A*
• Iterated Deepening A* (IDA)
• Recursive Best-first Search (RBFS)
• Simplified Memory Bounded A* (SMA)
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Latihan
• Selesaikan menggunakan Greedy Best-First Search dan A*
Search
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Tugas 3 Individu
• Dikumpulkan: 18 September 2025
• Terdapat kasus 8-puzzles dengan informasi state awal dan goal sebagai
berikut:
• Selesaikan kasus 8-puzzles diatas menggunakan 2 metode informed
search dengan actual cost adalah satu setiap aksi dan fungsi heuristik
adalah Manhattan distance (jumlah jarak masing-masing kotak ke
tujuan) atau jumlah kotak salah tempat
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
Tugas 4 Kelompok
• Deadline pengumpulan 2 Oktober 2025
• Buat implementasi program dua algoritma informed search
pada satu contoh kasus dan buat analisis perbandingan dari
hasil solusi kedua algoritma tersebut.
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
- TERIMA KASIH -