Problem Solving By

Searching
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
• Problem-solving agent
• Representasi masalah: state
space
• Pencarian solusi: Search
strategies
• Uninformed search strategy
• Depth-First Search
• Breadth-First Search
• Uniform Cost Search
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
 Reflex Agents Agents that Plan

Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Reflex Agents

• Pemilihan aksi berdasarkan persepsi

sekarang (dan mungkin memori)
• Bisa mempunyai memori atau model dari
kondisi (state) sekarang
• Tidak mempertimbangkan konsukensi
kedepan dari aksi yang dilakukan

Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Planning Agents

• Ask “what if”

• Keputusan berdasarkan hipotesis
konsukensi dari aksi yang dilakukan
• Harus mempunyai model bagaimana
seharusnya dunia mempertimbangkan
sebuah aksi (Consider how the world
WOULD BE)
• Harus merumuskan sebuah tujuan (goal)
• Optimal or not optimal
• Complete or not
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
• Planning vs. replanning

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Problem-Solving Agents

• Goal-based agent →
mempertimbangkan aksi-aksi yang akan
datang dan hasil yang ingin dicapai
• Agent problem solving → Menemukan
rangkaian aksi (sequence action) untuk
mencapai tujuannya
• Algoritma Uninformed → Tidak ada
informasi, hanya deskripsi pada masalah
tersebut

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Simple Problem-Solving Agent
Function Simple-Problem-Solving-Agent(percept) return an action
Input : percept //a percept
Static : seq //an action sequence, initially empty
state //some description of the current world state
goal //a goal, initially null
problem //a problem formulation

State  Update-State(state, percept)

If seq is empty then do
goal  Formulate-Goal(state)
problem  Formulate-Problem(state,goal)
seq  Search(Problem)

Action  First(seq)
Seq  Rest(seq)
Return action

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Mekanisme Kerja Problem-Solving Agent
• Perumusan tujuan (goal formulation): tentukan tujuan yang ingin
dicapai
• Kondisi saat ini
• Performance measure
• Perumusan masalah (problem formulation): tentukan tindakan/aksi
(action) dan keadaan (state) yang dipertimbangkan dalam mencapai
tujuan
• Pencarian solusi masalah (searching) : tentukan rangkaian aksi yang
perlu diambil untuk mencapai tujuan
• Input: problem, output: solusi dalam bentuk rangkaian aksi
• Pelaksanaan solusi (execution): laksanakan rangkaian aksi yang
sudah ditentukan di tahap sebelumnya
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
 Mendefinisikan Problem dan Solusi

• Problem dapat dirumuskan dengan 4 komponen

• Initial state
• Actions : Successor function :
• Successor-Fn(x) = <Action,Successor>
• Goal Test
• Path Cost
• Optimal Solution → path cost terkecil

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Contoh Kasus: Romania
• Seorang agent sedang berlibur
dan sekarang sedang di kota Arad
Romania
• Besok dia harus naik pesawat dari
Bucharest
• Goal dari agent sekarang adalah
pergi ke Bucharest
• Action yang tidak berhubungan
dengan goal akan dibuang ->
decision agent lebih sederhana

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Contoh Kasus: Romania

• Agent → Mencapai tujuan (ke Bucharest) dengan

naik mobil
• Kemana akan pergi setelah dari Arad ?
• Ada tiga jalan : ke Sibiu, Timisoara, Zerind
• Agent kita ini masih belum tahu jalan disana (mana yang
tercepat) tapi hanya memiliki peta.
• Dari informasi peta, dilakukan hipotesa terhadap ketiga
jalur tersebut untuk sampai ke Bucharest

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Contoh Kasus: Romania
(Agent & Environment)
•Static
• Tidak perlu memperhatikan perubahan yang terjadi pada
environment
•Observable
• Ada peta, initial state diketahui (di Arad)
•Discrete
• Enumeration action
•Deterministic
• Tidak bisa menangani terhadap hal-hal yang tidak diperkirakan

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Contoh Kasus: Romania
(Perumusan Tujuan, Masalah, & Solusi)
• Perumusan Tujuan
• Tiba di Bucharest besok
• Perumusan Masalah
• States : kota-kota
• Actions : mengemudi antar kota
• Pencarian Solusi
• Rangkaian kota : Arad, Sibiu, Fagaras, Bucharest

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Contoh Kasus: Romania
• Initial State →In(Arad)
• Actions : Successor function →
• {<Go(Sibiu),In(Sibiu)>,
<Go(Timisoara),In(Timisoara)>,
<Go(Zerind),In(Zerind)>}
• Goal Test → In(Bucharest)
• Path Cost →

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Contoh: Vacuum Cleaner
• States : Berada di salah satu dari dua
lokasi yang ada, setiap lokasi mungkin
bersih atau kotor. Jadi jumlah
kemungkinan state = 2 * 22
• Initial State ?
• Successor Function ? .
• Goal Test ?
• Path Cost ?

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Contoh: Vacuum Cleaner
• States : Berada di salah satu dari dua
lokasi yang ada, setiap lokasi mungkin
bersih atau kotor. Jadi jumlah
kemungkinan state = 2 * 22
• Initial State ? Sembarang state
• Successor Function ? (ke kiri, ke kanan,
bersihkan)
• Goal Test ? Semua lokasi bersih
• Path Cost ? Setiap aksi = 1 point

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Contoh Kasus: 8-Puzzle

• State : ?
• Initial State : ?
• Successor Function : ?
• Goal Test : ?
• Path Cost : ?

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Contoh Kasus: 8-Puzzles

•State : 8 kotak angka dan 1 kotak kosong

•Initial State : Sembarang state
•Successor Function : (ke kiri, ke kanan,
ke atas atau ke bawah)
•Goal Test : Tersusun kotak angka yang
diinginkan
•Path Cost : Setiap aksi bernilai 1 point

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Contoh Kasus: 8-Queens

• State : ?
• Initial State : ?
• Successor Function : ?
• Goal Test : ?

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Contoh Kasus: 8-Queens

• State : susunan 0..8 ratu pada papan catur

• Initial State : Tidak ada ratu pada papan
catur
• Successor Function : Masukkan ratu ke
papan catur
• Goal Test : Tidak ada ratu yang saling
serang

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Real World Problem

• Airline Travel Problem

• Touring Problem
• Traveling Salesman Problem
• VLSI Layout
• Robot Navigation
• Automatic Assembly Sequencing
• Internet Searching

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Searching for Solution
• Search problem terdiri dari:
• State space

“N”, 1.0
• Successor function
(with actions, costs)
“E”, 1.0

• Start state dan Goal test

• Solusi adalah urutan aksi (rencana) yang akan dilakukan dari start
state ke goal state
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 State Space Graph
• Sebuah state space graph
merupakan representasi matematika
pada sebuah search problem
• Nodes merepresentasikan konfigurasi state
• Arcs merepresentasikan successors (hasil
aksi)
• Goal test adalah himpunan goal nodes (bisa
hanya satu node)
• Setiap state hanya muncul sekali!

Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Search Trees
Start state
“N”, 1.0 “E”, 1.0

Next possible states

• Sebuah “what if” tree pada rencana dan luaran yang dihasilkan
• Start state adalah root node
• Anak merefer pada successors
• Nodes menunjukkan states
• Pada banyak problem, sebenarnya tidak pernah membangun tree
secara utuh Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 State Space Graphs vs. Search Trees

State Space Graph Search Tree

S

a G d e p
b c
b c e h r q
e
d f a a h r p q f
S h
p r p q f q c G
q
q c G a

Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 State Space Graphs vs. Search Trees

Consider this 4-state graph: How big is its search tree (from S)?

a s
a b
S G
b G a G
b a G b G

… …
Important: Lots of repeated structure in the search tree!
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Pencarian dengan sebuah Search Tree

• Search:
• Ekspansi potensi (tree nodes)
• Mencoba untuk ekspansi sedikit
mungkin node pada tree
• Fringe → kumpulan node hasil
generate yang belum diekspansi

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 General Tree Search
• Search Node → mulai root of search tree
sebagai Initial State
• Cek node apakah Goal?
• Jika bukan, expanding → menghasilkan state
baru
• Pertanyaan utama: fringe nodes yang akan di
explore berikutnya? → search strategy
• Ide utama:
• Fringe
• Expansion
• Exploration strategy
Function Tree-Search(problem,strategy) return a solution or a failure
initialize the search tree using the initial state
loop do
if there are no candidates for expansion then return failure
choose a leaf node for expansion according strategy
if the node contains a goal state then return the coresponding solution
else expand the node and add the resulting node to the search tree
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
 General Tree Search
Function Tree-Search(problem,fringe) return a solution or a failure
fringe  Insert(Make-Node(Initial-State[problem]),fringe)
loop do
if empty ?(fringe) then return failure
node  Remove-First(fringe)
if Goal-Test[problem] applied to State[node] succeds then
return Solution(node)
fringe  Insert-All(Expand(node,problem),fringe)
_________________________________________________________________________
Function Expand(node,problem) return a set of nodes
successor  the empty set
for each (action,result) in Successor-Fn[problem](State[node]) do
s  a new Node
State[s]  result Representasi Node:
Parent-node[s]  node • State
Action[s]  action • Parent-Node
Path-Cost[s]  Path-Cost[node] + Step-Cost(node,action,s) • Action
Depth[s]  Depth[node] + 1 • Path-Cost
add s to successor • Depth
return successors

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Contoh Tree Search
a G
b c
e
d f
S h
p q r

S s
s→d
d e p s→e
s→p
b c e h r q s→d→b
s→d→c
a a h r p q f s→d→e
s→d→e→h
p q f q c G
s→d→e→r
a s→d→e→r→f
q c G
s→d→e→r→f→c
a s→d→e→r→f→G
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
 Search Strategies
• Strategy → memilih node yang akan diekspansi:
• Completeness →Menemukan solusi jika ada
• Optimality → Optimal solution (cost terkecil)
• Time Complexity → berapa lama menemukan solusinya ?
• Space Complexity → berapa banyak memory yang
dibutuhkan ?
• Time dan Space Complexity bisa dilihat dari:
• b → maks branch factor
• d → depth dari solusi terkecil
• m → maks depth dari state space

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Uninformed Search Strategies

• Depth-first search
• Breadth-first search
• Depth-limited search
• Iterative deepening search
• Uniform-cost search
• Bidirectional search

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Depth-first Search
• Expand node yang terdalam A

• Fringe → LIFO stack

• Complete ? B C
• Tidak, jika memiliki depth tak terbatas,
• Modifikasi dengan limited depth
• Ya, jika depth terbatas D E F G

• Time ? O(bm)
• Bermasalah jika m jauh lebih besar dari d
• Space ? O(bm), linier space
• Optimal ? Tidak

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Depth-first Search
a G
b cc

ee
d f
S h
p q r

d e p

b c e h r q

a a h r p q f

p q f q c G

q c G
a

a Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Depth-first Search: 8-puzzles
1 2
Input:
4 5 3
7 8 6

1 2 1 2 3
4 5 3 4 5
7 8 6 7 8 6
b=3 b=3

1, L 2, R 5, U 3, D 5, R 6, U

Until leaf node,

no more children

Goal
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
 Breadth-first Search
• Ekspand node ke samping
• Fringe → FIFO queue
• Complete ? Ya, jika b terbatas
• Time ? 1 + b + b2 + b3 + … + bd = O(bd)
d+1
• Space ? O(b ) A

• Optimal ? Ya, jika semua aksi bernilai sama

B C

D E F G

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Breadth-first Search
a G
b c
e
d f
S h
p q r

d e p
Search
b c e h r q
Tiers
a a h r p q f

p q f q c G

q c G
a
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley

[Link]/informatika a Konsep Kecerdasan Artifisial EK234201

 Breadth-first Search: 8-puzzles
1 2
Input:
4 5 3
7 8 6

1 2 1 2 3
4 5 3 4 5
7 8 6 7 8 6
b=3 b=3

1, L 2, R 5, U 3, D 5, R 6, U

Goal

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Depth-limited Search

• Sama dengan DFS dengan deep limit l

• Implementasi dengan Rekursif
Function Depth-Limited-Search(problem,limit) return a solution or a failure/cutoff
return Recursive-DLS(Make-Node(Initial-State[problem]),problem,limit)
Function Recursive-DLS(node,problem,limit) return a solution or failure/cutoff
cutoff_occured?  false
if Goal-Test[problem](State[node]) then return solution
else if Depth[node] = limit then return cutoff
else for each successor in Expand(node,problem) do
result  recursive-DLS(successor,problem,limit)
if result  cutoff then cutoff_occured?  true
else if result <> failure then return result
if cutoff_occured? Then return cutoff
else return failure

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Iterative Deepening Search

• Merupakan DFS yang diiterasi berdasarkan kedalamannya

• Mengkombinasi DFS dan BFS
• Pencarian pada level 1 terlebih dahulu jika tidak menemukan goal
pencarian berikutnya digenerate level 2, 3, dan seterusnya
• Run a DFS with depth limit 1. If no solution…
• Run a DFS with depth limit 2. If no solution…
• Run a DFS with depth limit 3. …..
Function Iterative-Deepening-Search(problem) return a solution or a failure
input problem // a problem
for depth  0 to  do
result  Depth-Limited-Search(problem,depth)
if result <> cutoff then return result

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Iterative Deepening Search
• Complete ? Ya
• Time ? (d+1)b0 + (d)b + (d-1)b2+…+bd=
Limit = 3
0
1
2 A O(bd)
• BFS menggenerate node sampai d + 1 sementara
IDS hanya d → IDS lebih cepat dari BFS
B C • Space ? O(bd)
• Optimal ? Ya, jika memiliki cost yang
sama untuk setiap aksi
D E F G
• Perbandingan IDS vs BFS:
➔ b = 10 dan d = 5
H I J K L M • N(IDS) : 50 + 400 + 3.000 + 20.000 + 100.000 =
123.450
• N(BFS) : 10 + 100 + 1.000 + 10.000 + 100.000 +
999.990 = 1.111.100

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Uniform-cost Search
• Expand node dengan cost terkecil
• Fringe ➔ priority queue (priority: cumulative cost)
• Jika masing-masing node memiliki cost yang sama = BFS
• Complete ? Ya jika step cost >= Є (positif)
• Time ? O(b C*/ Є) ; C* = Optimal solution
• Jumlah node dengan g <= cost optimal solution
• Space ? O(b C*/ Є)
• Jumlah node dengan g <= cost optimal solution
• Optimal ? Ya, node diekspand → urutan
penambahan g(n)

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Uniform-cost Search
a G
b c
1 8 2
2 e
3 d f
9 2
S h 8
1
1 p q r

S 0

d 3 e 9 p 1

b 4 c e 5 h 17 r 11 q 16
11
Cost a 6 a h 13 r 7 p q f
contours
p q f 8 q c G

q 11 c G 10
a
Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley
a
[Link]/informatika Konsep Kecerdasan Artifisial EK234201
 Bidirectional Search
• Mencari dari 2 arah secara simultan
• Motivasi → bd/2 + bd/2 jauh lebih kecil dari bd
• Misal d = 6, masing2 menggunakan BFS → depth=3, b=10; dengan
bidirectional hanya 22.200 node sedangkan BFS standar mencapai
11.111.000 node

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Perbandingan: Uninformed search
strategies

Evaluation of search algorithms. b is the branching factor; m is the maximum depth of the search tree; d is the depth of the
shallowest solution, or m is when there is no solution; ℓ is the depth limit.
Superscript caveats are as follows: 1complete if b is finite, and the state space either has a solution or is finite.
2
complete if all action costs are ≥ ε > 0; 3cost-optimal if action costs are all identical; 4if both directions are breadth-first or
uniform-cost.

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Video of Demo Maze with Deep/Shallow Water --- DFS, BFS, or UCS?

Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley

[Link]/informatika Kecerdasan Buatan (IF184403)

 Video of Demo Maze with Deep/Shallow Water --- DFS, BFS, or UCS?

Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Video of Demo Maze with Deep/Shallow Water --- DFS, BFS, or UCS?

Sumber: Sergey Levine & Stuart Russell, University of California, Berkeley

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

 Tugas Individu
Batas waktu pengumpulan: 11 September 2025

Pada permainan 8-puzzles dengan informasi state awal dan goal sebagai
berikut:

1. Selesaikan permainan 8-puzzles diatas menggunakan metode BFS

2. Selesaikan permainan 8-puzzles diatas menggunakan metode
Iterative deepening search

[Link]/informatika Konsep Kecerdasan Artifisial EK234201

- TERIMA KASIH -