21
Dalam
algoritma pathfinding
seringkali
terjadi
backtrack
bila
tidak
menemukan
solusi.
Backtrack
merupakan suatu
algoritma
pelacakan
yang
mencoba
mencari
penyelesaian
masalah
yang
menyeluruh
dengan
membangun
solusi
partial. Masalah
yang
akan
diselesaikan dengan
fungsi
backtrack
harus
memenuhi suatu
set
kendala
(constraint).
Dalam
prosesnya,
backtrack
akan
mundur
ke
solusi
partial
sebelumnya,
jika terdapat solusi yang cocok dengan tuntutan masalah.
2.8.1
Algoritma Depth-First Search
Menurut
Stuart
Russel
dan
Peter
Norvig
(1995,77), depth-first
search
selalu
memperluas (expand) salah satu node-nya pada level yang paling dalam dari sebuah tree.
Hanya
ketika
pencarian
bertemu
dengan
jalan
buntu,
maka
pencarian kembali
ke
node
semula dan memperluas (expand) node pada tingkat yang lebih dangkal.
Algoritma
depth-first
search
memiliki
kompleksitas
waktu
O(b
m
).
Untuk
masalah
yang
memiliki banyak
solusi,
depth-first
search
dapat
lebih
cepat
dibanding
dengan
breadth-first
search,
karena
depth-first
search
memiliki
suatu
kemungkinan
yang
bagus
ketika
menemukan sebuah
solusi,
dimana
hanya
menjelajah
sebagian
kecil
dari keseluruhan bagian.
Kekurangan
dari
depth-first
search
yaitu
dapat
terjebak
menjelajahi
path
/
jalur
yang
salah.
Maka
depth-first
search
tidak
akan
pernah
bisa
untuk
mnemukan
kembali
jalur semula, ketika ia memilih jalur yang salah.
2.8.2
Algoritma Breadth-First Search
Menurut
Luger
dan
Stubblefield
(1993,
p92),
algoritma
Breadth-First
Search
adalah
algoritma
yang
memeriksa
node
dalam
tree
secara
level per
level.
Jika
dalam
 |