22
suatu
level ditemukan
goal,
maka
pencarian
dihentikan
dan
goal-nya
akan
diberikan
sebagai
goal
yang
sukses.
Jika
semua
node
dalam
suatu
level telah
diperiksa dan
tidak
ditemukan
goal,
maka
algoritma
ini
akan
berpindah
memeriksa
ke
level berikutnya,
demikian seterusnya.
Jika semua
node pada
level yang paling bawah telah diperiksa dan
belum
ditemukan
goal,
maka
pencarian
dihentikan
dan
goalnya
diberikan
sebagai
goal
yang gagal.
Algoritma
Breadth-First
Search
diimplementasikan
dengan
menggunakan
dua
buah
list,
yaitu open dan
close,
Luger dan
Stubblefield (1993, p92).
Open berisi daftar
node-node
yang
telah siap
untuk
diperiksa,
tetapi
children
dari
node-node
tersebut
belum di-generate.
Sedangkan close berisi
daftar
node-node
yang
telah diperiksa
tetapi
bukan
merupakan goal. Open
list dari algoritma Breadth-First
Search
merupakan queue
yang
berpola
First
In
First
Out
(FIFO),
dimana
node
yang
akan
diperiksa
terlebih
dahulu adalah node yang terlebih dahulu masuk ke dalam list.
Menurut
Luger
dan
Stubblefield (1993,
p97-98),
keuntungan
dari
algoritma
Breadth-First
Search
adalah
dijaminnya diperoleh path
terpendek
jika
goal-nya
ditemukan (karena algoritma ini akan selalu
memeriksa semua
node pada
level
n
sebelum berpindah ke
level n+1).
Juga bahwa tidak semua node
harus diperiksa, karena
jika
goal
telah
ditemukan sebelum
seluruh
node
diperiksa,
maka
pencarian
dapat
dihentikan.
Namun
algoritma
Breadth-First
Search
memiliki
kelemahan,
yaitu
semua
nilai
/
biaya
dari
node
harus
sama,
sehingga
tidak
dapat
diterapkan pada
tree
yang
bernilai.
 |