BAB 2
LANDASAN TEORI
Bab
ini
berisikan
definisi serta
teori-teori
dari
algoritma
yang
digunakan
dalam
pembuatan
program aplikasi.
Definisi
serta
teori-teori
pendukung
yang
dipakai
dalam
pembuatan program aplikasi ini juga diuraikan dalam bab ini.
2.1. Algoritma A*
A* merupakan bentuk yang paling dikenal dari Best First Search. A*
mengevaluasi node dengan
menggabungkan g(n), yaitu cost
untuk
mencapai node, dan
h(n), yaitu cost yang diperlukan dari node untuk mencapai tujuan, sehingga:
f(n) = g(n) + h(n)
g(n) merupakan cost suatu path dari node awal ke node n, dan h(n) adalah
perkiraan
cost
terendah
dari
node
n
ke
tujuan. f(n) adalah
perkiraan
solusi
dengan
cost
termurah melalui n.
Dengan demikian, untuk menemukan solusi termurah, hal yang pertama yang
dicoba adalah node dengan
nilai g(n)+h(n) terendah. Strategi
ini jelas
lebih baik dengan
disediakannya
fungsi
heuristik h(n) yang dapat
memenuhi kondisi
tertentu sehingga
A*
menjadi optimal. (Russel dan Norvig, 2010, p93)
Perlu
disadari
bahwa
algoritma
Dijkstra
adalah subset
dari
algoritma
A*.
Dalam
A*, akan dihitung perkiraan total
cost
dari node
dengan
menambahkan
nilai
heuristik
pada
cost
sejauh
ini.
A*
kemudian
memilih
sebuah
node
untuk
diproses
berdasarkan
nilai tersebut.
8
 |