Kecerdasan Buatan KBKRI

State Space Search

Yaya Wihardi, [Link]., [Link].

Department of Computer Science Education

Universitas Pendidikan Indonesia

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 1

 Kecerdasan Buatan KBKRI

Outline

• Problem Solving Agent

• Representasi masalah: state space
• Pencarian solusi: search
• State space search
• Breadth-first
• Uniform-cost
• Depth-first
• Iterative-deepening
• Pengulangan state

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 2

 Kecerdasan Buatan KBKRI

Problem Solving Agent

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 3

 Kecerdasan Buatan KBKRI

Problem Solving Agent

• Di kuliah yang lalu kita melihat contoh reflex agent: tidak

cocok untuk masalah besar!
• Goal-based agent: memiliki tujuan, memungkinkannya
meng-evaluasi tindakan dan memilih yang terbaik.
• Di kuliah ini kita membahas satu kemungkinan jenis
goal-based agent: problem-solving agent
• Problem-solving agent menghasilkan solusi dalam
bentuk serangkaian tindakan yang diambil untuk
mencapai tujuan.
• Apa problem-nya? Apa solution-nya?

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 4

 Kecerdasan Buatan KBKRI

Mekanisme kerja Problem-Solving Agent

• Perumusan tujuan (goal formulation): tentukan tujuan yang

ingin dicapai
• Perumusan masalah (problem formulation): tentukan tindakan
(action) dan keadaan (state) yang dipertimbangkan dalam
mencapai tujuan
• Pencarian solusi masalah (searching): tentukan rangkaian
tindakan yang perlu diambil untuk mencapai tujuan
• Pelaksanaan solusi (execution): laksanakan rangkaian
tindakan yang sudah ditentukan di tahap sebelumnya

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 5

 Kecerdasan Buatan KBKRI

Agent program Problem Solving Agent

function SimpleProblemSolvingAgent (percept) returns action

state  UpdateState(state, percept)

if seq is empty then
goal  FormulateGoal (state, goal)
problem  FormulateProblem (state, goal)
seq  Search (problem)
action  Recommendation (seq, state)
seq  Remainder (seq, state)
return action

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 6

 Kecerdasan Buatan KBKRI

Sifat Problem-Solving Agent

• Biasanya problem solving agent mengasumsikan bahwa

environment-nya:
• fully observable
• Deterministic
• Sequential
• Static
• Discrete
• Setelah mencari solusi, agent ini melaksanakan tindakan
dengan “mata tertutup" → tidak melihat percept!

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 7

 Kecerdasan Buatan KBKRI

Contoh: Turis di Rumania

• Suatu “tourist agent" yang sedang berlibur di Rumania,

kini berada di Arad. Besok, dia harus terbang dari
bandara Bucharest.
• Perumusan tujuan: berada di Bucharest
• Perumusan masalah:
• Tindakan (action): menyetir dari kota ke kota
• Keadaan (state): kota-kota di Rumania
• Pencarian solusi: rangkaian kota yang dituju, mis: Arad,
Sibiu, Fagaras, Bucharest

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 8

 Kecerdasan Buatan KBKRI

Peta Rumania

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 9

 Kecerdasan Buatan KBKRI

Representasi masalah: state space

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 10

 Kecerdasan Buatan KBKRI

Perumusan masalah sebagai state space

• Initial state: keadaan awal di mana si agent mulai, mis:

BeradaDi(Arad)
• Possible actions: tindakan yang dapat dilakukan si agent, mis:
Nyetir(Arad, Zerind).
• Sebuah successor function S menentukan untuk suatu state X,
himpunan tindakan yang mungkin diambil beserta state yang
dihasilkan. Contoh:
X = BeradaDi(Arad)
S(X) = { <Nyetir(Arad, Zerind), BeradaDi(Zerind)>, … }
• Initial state dan successor function mendefinisikan state space:
himpunan semua state yang dapat dicapai dari initial state. Dapat
direpresentasikan sebagai graph. Path dalam state space adalah
serangkaian state (dihubungkan serangkaian action).

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 11

 Kecerdasan Buatan KBKRI

Menelusuri sebuah state space

• Goal test: penentuan apakah suatu state adalah tujuan yang
ingin dicapai atau bukan.
• Eksplisit: himpunan goal state, mis: {BeradaDi(Bucharest)}.
• Implisit: deskripsi tujuan, mis: dalam catur → skak mat.
• Path cost function: sebuah fungsi yang memberikan nilai
numerik terhadap setiap path. Fungsi ini merefleksikan
performance measure si agent.
• Asumsi path cost function = σ step cost: cost action a dari
state x ke y: c(x, a, y).
• Sebuah solusi adalah path dari initial state ke goal state.
• Sebuah solusi optimal adalah solusi dengan path cost
function minimal.

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 12

 Kecerdasan Buatan KBKRI

Memilih state space

• Dunia nyata luar biasa kompleks dan rumit! State space harus
merupakan abstraksi masalah supaya bisa dipecahkan.
• State = himpunan “keadaan nyata". Mis: BeradaDi(Arad) -
dengan siapa? kondisi cuaca?
• Action = kombinasi berbagai “tindakan nyata". Mis:
Nyetir(Arad, Sibiu) - jalan tikus, isi bensin, istirahat, dll.
• Solution = representasi berbagai “path nyata" yang
mencapai
tujuan
• Abstraksi ini membuat masalah yang nyata lebih mudah
dipecahkan.

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 13

 Kecerdasan Buatan KBKRI

Contoh: VacuumCleanerWorld
• State: lokasi agent, status debu
• Possible action: DoKeKiri(L), DoKeKanan(R),
DoSedot(S)
• Goal test: apakah semua ruangan bebas debu?
• Path cost: jumlah langkah dalam path.
• Successor function mendefinisikan state space sbb:

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 14

 Kecerdasan Buatan KBKRI

Contoh: Puzzle-8

• State: lokasi 8 buah angka dalam matriks 3x3

• Possible action: Kiri (Left), Kanan (Right), Atas (Up), Bawah (Down)
• Goal test: apakah konfigurasi angka seperti goal state di atas
• Path cost: jumlah langkah dalam path.

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 15

 Kecerdasan Buatan KBKRI

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 16

 Kecerdasan Buatan KBKRI

Contoh: 8-Queens Problem

• Letakkan 8 bidak menteri (queen) sedemikian sehingga tidak

ada yang saling “makan" (queen bisa makan dalam satu
baris, kolom, diagonal).
• State: Papan catur dengan n buah queen, 0 ≤ n ≤ 8.
• Initial state: Papan catur yang kosong.
• Possible action: Letakkan sebuah queen di posisi kosong.
• Goal test: 8 queen di papan, tidak ada yang saling makan

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 17

 Kecerdasan Buatan KBKRI

Masalah state space... combinatorial explosion!

• Dengan definisi masalah demikian, ada

64 × 63 × … × 57 ≈ 1.8 × 1014 path!
• Mustahil kita selesaikan dengan komputer tercanggih apapun.
Definisi masalah bisa diperjelas:
• State: Papan catur dengan n queen, 0 ≤ n ≤ 8, satu per
kolom di n kolom paling kiri.
• Possible action: Letakkan sebuah queen di posisi kosong
di kolom paling kiri yang belum ada queen-nya sehingga
tidak ada yang saling makan.
• State space sekarang ukurannya tinggal 2057, dan mudah
dipecahkan.
• Perumusan masalah yang tepat bisa berakibat drastis!
• Meskipun demikian, untuk n = 100: 10400 vs. 1052...

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 18

 Kecerdasan Buatan KBKRI

Pencarian solusi: search

State Space Search

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 19

 Kecerdasan Buatan KBKRI

Mencari solusi melalui search tree

• Setelah merumuskan masalah → cari solusinya

menggunakan sebuah search algorithm
• Search tree merepresentasikan state space.
• Search tree terdiri dari kumpulan node: struktur data yang
merepresentasikan suatu state pada suatu path, dan memiliki
parent, children, depth, dan path cost.
• Root node merepresentasikan initial state.
• Node expansion → Penerapan successor function terhadap
(state yang diwakili) node menghasilkan children baru.
• Kumpulan semua node yang belum di-expand disebut fringe
(pinggir) sebuah search tree.

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 20

 Kecerdasan Buatan KBKRI

Contoh penelusuran search tree

• Mulai dari root node (Arad) sebagai current node

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 21

 Kecerdasan Buatan KBKRI

Contoh penelusuran search tree

• Mulai dari root node (Arad) sebagai current node

• Lakukan node expansion terhadapnya.

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 22

 Kecerdasan Buatan KBKRI

Contoh penelusuran search tree

• Mulai dari root node (Arad) sebagai current node

• Lakukan node expansion terhadapnya.
• Pilih salah satu node yang di-expand sebagai current
node yang baru. Ulangi langkah sebelumnya.

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 23

 Kecerdasan Buatan KBKRI

Algoritma penelusuran search tree

1. Pada awalnya, fringe = himpunan node yang mewakili initial state.
2. Pilih satu node dari fringe sebagai current node (Kalau fringe
kosong, selesai dengan gagal).
3. Jika node tsb. lolos goal test, selesai dengan sukses!
4. Jika tidak, lakukan node expansion terhadap current node tsb.
Tambahkan semua node yang dihasilkan ke fringe.
5. Ulangi langkah 2.
function TreeSearch (problem, fringe) returns solution or failure

fringe  Insert(MakeNode(InitialState(problem)), fringe)

loop do
if Empty?(fringe) then return failure
node  RemoveFirst(fringe)
if GoalTest(problem) applied to State(node) succeeds
then return Solution(node)
fringe  InsertAll(Expand(node,problem), fringe)

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 24

 Kecerdasan Buatan KBKRI

State vs. Node

• Sebuah state merepresentasikan abstraksi keadaan

nyata dari masalah.
• Sebuah node adalah struktur data yang menjadi bagian
dari search tree.
• State tidak memiliki parent, children, depth, path cost!
• Node = state pada path tertentu. Dua node berbeda bisa
mewakili state yang sama!

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 25

 Kecerdasan Buatan KBKRI

Strategi pencarian
• Terdapat berbagai jenis strategi untuk melakukan search.
• Semua strategi ini berbeda dalam satu hal: urutan dari node
expansion.
• Search strategy di-evaluasi berdasarkan:
• completeness: apakah solusi (jika ada) pasti ditemukan?
• time complexity: jumlah node yang di-expand.
• space complexity: jumlah maksimum node di dalam
memory.
• optimality: apakah solusi dengan minimum cost pasti
ditemukan?
• Time & space complexity diukur berdasarkan
• b - branching factor dari search tree
• d - depth (kedalaman) dari solusi optimal
• m - kedalaman maksimum dari search tree (bisa infinite!)

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 26

 Kecerdasan Buatan KBKRI

Uninformed search strategies

• Uninformed strategy hanya menggunakan informasi dari

definisi masalah.
• Bisa diterapkan secara generik terhadap semua jenis
masalah yang bisa direpresentasikan dalam sebuah
state space.
• Ada beberapa jenis:
• Breadth-first search
• Uniform-cost search
• Depth-first search
• Depth-limited search
• Iterative-deepening search

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 27

 Kecerdasan Buatan KBKRI

Pencarian solusi: search

Breadth First Search (BFS)

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 28

 Kecerdasan Buatan KBKRI

BFS
Prinsip algoritma breadth-first search
Lakukan node expansion terhadap node di fringe yang paling
dekat ke root.

• Implementasi: fringe adalah sebuah queue, data struktur FIFO (First

In First Out)
• Hasil node expansion (successor function) ditaruh di belakang

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 29

 Kecerdasan Buatan KBKRI

BFS
Prinsip algoritma breadth-first search
Lakukan node expansion terhadap node di fringe yang paling
dekat ke root.

• Implementasi: fringe adalah sebuah queue, data struktur FIFO (First

In First Out)
• Hasil node expansion (successor function) ditaruh di belakang

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 30

 Kecerdasan Buatan KBKRI

BFS
Prinsip algoritma breadth-first search
Lakukan node expansion terhadap node di fringe yang paling
dekat ke root.

• Implementasi: fringe adalah sebuah queue, data struktur FIFO (First

In First Out)
• Hasil node expansion (successor function) ditaruh di belakang

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 31

 Kecerdasan Buatan KBKRI

BFS
Prinsip algoritma breadth-first search
Lakukan node expansion terhadap node di fringe yang paling
dekat ke root.

• Implementasi: fringe adalah sebuah queue, data struktur FIFO (First

In First Out)
• Hasil node expansion (successor function) ditaruh di belakang

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 32

 Kecerdasan Buatan KBKRI

Sifat BFS

• Complete?
Ya, jika b terbatas
• Time complexity?
1 + b + b2 + b3 + … + bd = O(bd) !
eksponensial dlm. d.
• Space complexity?
O(bd), karena semua node dengan kedalaman d harus
disimpan.
• Optimal?
Ya, jika semua step cost sama, tapi pada umumnya
tidak optimal.

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 33

 Kecerdasan Buatan KBKRI

Sifat BFS

Masalah utama breadth-first search adalah space

Mis: 1 node memakan 1000 byte, dan b = 10
Jika d = 6, ada 106 node ≈ 1 gigabyte.
Jika d = 12, ada 1012 node ≈ 1 petabyte!

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 34

 Kecerdasan Buatan KBKRI

Pencarian solusi: search

Uniform-cost search

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 35

 Kecerdasan Buatan KBKRI

Uniform-cost search

Prinsip algoritma uniform-cost search

Lakukan node expansion terhadap node di fringe yang path
cost-nya paling kecil.

• Implementasi: fringe adalah sebuah priority queue di

mana node disortir berdasarkan path cost function g(n).
• Jika semua step cost sama, uniform-cost sama dengan
breadth-first.
• Bandingkan dengan shortest-path algorithm-nya Dijkstra!

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 36

 Kecerdasan Buatan KBKRI

Sifat Uniform-cost search

• Complete?
Ya, jika step cost ≥ a dimana a > 0
• Time complexity?
Jumlah node dengan
g(n) ≤ C* = O(b⌈C*/a⌉) di mana C* adalah cost dari optimal
solution
• Space complexity?
Jumlah node pada “fringe terakhir",
g(n) ≤ C* ≈ O(b⌈C*/a⌉)
• Optimal?
Ya, karena urutan node expansion dilakukan urut g(n).

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 37

 Kecerdasan Buatan KBKRI

Contoh uniform-cost search

• Coba cari optimal solution dari Arad ke Bucharest!

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 38

 Kecerdasan Buatan KBKRI

Pencarian solusi: search

Depth First Search (DFS)

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 39

 Kecerdasan Buatan KBKRI

DFS
Prinsip algoritma depth-first search
Lakukan node expansion terhadap node di fringe yang paling jauh
dari root.

• Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last

In First Out)
• Hasil node expansion (successor function) ditaruh di depan
• Depth-first search cocok diimplementasikan secara rekursif

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 40

 Kecerdasan Buatan KBKRI

DFS
Prinsip algoritma depth-first search
Lakukan node expansion terhadap node di fringe yang paling jauh
dari root.

• Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last

In First Out)
• Hasil node expansion (successor function) ditaruh di depan
• Depth-first search cocok diimplementasikan secara rekursif

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 41

 Kecerdasan Buatan KBKRI

DFS
Prinsip algoritma depth-first search
Lakukan node expansion terhadap node di fringe yang paling jauh
dari root.

• Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last

In First Out)
• Hasil node expansion (successor function) ditaruh di depan
• Depth-first search cocok diimplementasikan secara rekursif

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 42

 Kecerdasan Buatan KBKRI

DFS
Prinsip algoritma depth-first search
Lakukan node expansion terhadap node di fringe yang paling jauh
dari root.

• Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last

In First Out)
• Hasil node expansion (successor function) ditaruh di depan
• Depth-first search cocok diimplementasikan secara rekursif

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 43

 Kecerdasan Buatan KBKRI

DFS
Prinsip algoritma depth-first search
Lakukan node expansion terhadap node di fringe yang paling jauh
dari root.

• Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last

In First Out)
• Hasil node expansion (successor function) ditaruh di depan
• Depth-first search cocok diimplementasikan secara rekursif

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 44

 Kecerdasan Buatan KBKRI

DFS
Prinsip algoritma depth-first search
Lakukan node expansion terhadap node di fringe yang paling jauh
dari root.

• Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last

In First Out)
• Hasil node expansion (successor function) ditaruh di depan
• Depth-first search cocok diimplementasikan secara rekursif

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 45

 Kecerdasan Buatan KBKRI

DFS
Prinsip algoritma depth-first search
Lakukan node expansion terhadap node di fringe yang paling jauh
dari root.

• Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last

In First Out)
• Hasil node expansion (successor function) ditaruh di depan
• Depth-first search cocok diimplementasikan secara rekursif

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 46

 Kecerdasan Buatan KBKRI

DFS
Prinsip algoritma depth-first search
Lakukan node expansion terhadap node di fringe yang paling jauh
dari root.

• Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last

In First Out)
• Hasil node expansion (successor function) ditaruh di depan
• Depth-first search cocok diimplementasikan secara rekursif

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 47

 Kecerdasan Buatan KBKRI

DFS
Prinsip algoritma depth-first search
Lakukan node expansion terhadap node di fringe yang paling jauh
dari root.

• Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last

In First Out)
• Hasil node expansion (successor function) ditaruh di depan
• Depth-first search cocok diimplementasikan secara rekursif

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 48

 Kecerdasan Buatan KBKRI

DFS
Prinsip algoritma depth-first search
Lakukan node expansion terhadap node di fringe yang paling jauh
dari root.

• Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last

In First Out)
• Hasil node expansion (successor function) ditaruh di depan
• Depth-first search cocok diimplementasikan secara rekursif

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 49

 Kecerdasan Buatan KBKRI

DFS
Prinsip algoritma depth-first search
Lakukan node expansion terhadap node di fringe yang paling jauh
dari root.

• Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last

In First Out)
• Hasil node expansion (successor function) ditaruh di depan
• Depth-first search cocok diimplementasikan secara rekursif

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 50

 Kecerdasan Buatan KBKRI

DFS
Prinsip algoritma depth-first search
Lakukan node expansion terhadap node di fringe yang paling jauh
dari root.

• Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last

In First Out)
• Hasil node expansion (successor function) ditaruh di depan
• Depth-first search cocok diimplementasikan secara rekursif

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 51

 Kecerdasan Buatan KBKRI

Sifat DFS

• Complete?
Tidak, bisa gagal jika m tak terbatas, atau state
space dengan loop.
• Time complexity?
O(bm) → jika m > d, parah!
• Space complexity?
O(bm) → linear space!
• Optimal?
Tidak.

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 52

 Kecerdasan Buatan KBKRI

Sifat DFS

Depth-first search mengatasi masalah space

Mis: 1 node memakan 1000 byte, dan b = 10
Jika d = 12, space yang dibutuhkan hanya 118 kilobyte …
bandingkan dengan 1 petabyte!

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 53

 Kecerdasan Buatan KBKRI

Variasi DFS

• Backtracking search: lakukan node expansion satu-per-

satu. Jika gagal backtrack dan coba nilai successor
function yang lain.
• Depth-limited search: Batasi kedalaman maksimal yang
dilihat adalah l.
• Mengatasi masalah untuk state space tak terbatas.
• Sayangnya, ada unsur incompleteness baru, jika l < d.
• Biasanya d tidak diketahui (tapi bisa ada estimasi, mis.
diameter suatu graph).

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 54

 Kecerdasan Buatan KBKRI

Implementasi rekursif depth-limited search

function RecursiveDLS (node, problem, limit) returns solution or failure/cutoff

cutoff_occurred?  false
if GoalTest[problem](State[node]) then return Solution(node)
else if Depth[node] = limit then return cutoff
else for each successor in Expand(node,problem) do
result  RecursiveDLS(successor,problem,limit)
if result = cutoff then cutoff_occurred?  true
else if result ≠ failure then return result
if cutoff_occurred? then return cutoff else return failure

function DepthLimitedSearch (problem, limit) returns solution or failure/cutoff

return RecursiveDLS(MakeNode(InitialState[problem]), problem, limit)

Perhatikan perbedaan antara cutoff dan failure

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 55

 Kecerdasan Buatan KBKRI

Pencarian solusi: search

Iterative Deepening Search (IDS)

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 56

 Kecerdasan Buatan KBKRI

IDS
Prinsip algoritma depth-first search

Lakukan depth-limited search secara bertahap dengan nilai l yang

incremental.

• Strategi ini menggabungkan manfaat depth dan breadth first:

space complexity linier dan completeness terjamin!
• Lakukan depth-limited search dengan l = 0, 1, 2, … sampai tidak
cutoff .

function IterativeDeepeningSearch (problem) returns solution or failure

for depth  0 to ∞ do
result  DepthLimitedSearch(problem, depth)
if result ≠ cutoff then return result

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 57

 Kecerdasan Buatan KBKRI

Contoh iterative-deepening search

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 58

 Kecerdasan Buatan KBKRI

Contoh iterative-deepening search

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 59

 Kecerdasan Buatan KBKRI

Contoh iterative-deepening search

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 60

 Kecerdasan Buatan KBKRI

Contoh iterative-deepening search

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 61

 Kecerdasan Buatan KBKRI

Sifat IDS

• Complete?
Ya.
• Time complexity?
(d + 1)b0 + db1 + (d − 1)b2 + … + bd = O(bd)
• Space complexity?
O(bd)
• Optimal?
Ya, jika semua step cost sama. Bisa dimodifikasi spt.
uniform-cost tree, namanya iterative lengthening search

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 62

 Kecerdasan Buatan KBKRI

Kinerja iterative-deepening search

• Secara sekilas, strategi ini kelihatan tidak efisien, atau

boros: banyak usaha terulang!
Keborosan pada Iterative-deepening search secara umum tidaklah terlalu
parah. Iterative-deepening search adalah complete dan feasible dalam memory!

N(IDS) = db + (d − 1)b2 + … + (1)bd

N(BFS) = b + b2 + … + bd
Untuk b = 10 dan d = 5:
N(IDS) = 50 + 400 + 3.000 + 20.000 + 100.000 = 123.450
N(BFS) = 10 + 100 + 1.000 + 10.000 + 100.000 = 111.110

• Pada umumnya, iterative deepening search adalah

uninformed search strategy yang terbaik jika state space
besar dan kedalaman solusi (d) tidak diketahui.

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 63

 Kecerdasan Buatan KBKRI

Perbandingan strategi pencarian

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 64

 Kecerdasan Buatan KBKRI

Masalah Pengulangan State

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 65

 Kecerdasan Buatan KBKRI

Masalah: state yang mengulang di dalam search tree

• Kegagalan menangani state yang mengulang dapat

membuat masalah linier menjadi eksponensial!

• Ingat dua variasi definisi masalah 8-queens problem.

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 66

 Kecerdasan Buatan KBKRI

Solusi: belajar dari sejarah

• Algorithms that forget their history are doomed to repeat

it...
• Solusinya adalah untuk mencatat state mana yang
sudah pernah dicoba. Catatan ini disebut closed list
(fringe = open list).
• Modifikasi algoritma TreeSearch dengan closed list
menjadi GraphSearch. → Sudah kita lakukan pada
praktikum

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 67

 Kecerdasan Buatan KBKRI

Algoritma GraphSearch

function GraphSearch (problem, fringe) returns solution or failure

closed  { }
fringe  Insert(MakeNode(InitialState(problem)), fringe)
loop do
if Empty?(fringe) then return failure
node  RemoveFirst(fringe)
if GoalTest(problem) applied to State(node) succeeds
then return Solution(node)
if State[node] ∉ closed then
add State[node] to closed
fringe  InsertAll(Expand(node,problem), fringe)

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 68

 Kecerdasan Buatan KBKRI

Sifat GraphSearch

• Time complexity: sama, jika kita asumsi operasi State[node]

∉ closed = O(1) (implementasi dengan hashtable?)
• Space complexity: DFS dan IDS tidak lagi linier!
• GraphSearch tidak mencatat path menuju suatu state. Ini
mempengaruhi sifat optimality suatu strategi:
• Uniform-cost dan breadth-first search dengan step cost
konstanta masih optimal (kenapa?).
• Untuk variasi Depth-first dan iterative-deepening search,
jika state mengulang ditemukan, periksa apakah path cost-
nya lebih kecil → update info node dan anak-anaknya!

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 69

 Kecerdasan Buatan KBKRI

Thank You

KBK Kecerdasan Buatan, Kontrol, Robotika, IoT Artificial Intelligence 70