39
2.
Algoritma
Informed
Search
Adalah
algoritma
yang
memiliki
keterangan
tentang
jarak
atau
biaya dari
path
dan
memiliki
pertimbangan
berdasarkan
pengetahuan
akan
path
mana
yang
lebih
baik,
yang tennasuk algoritma ini
antara lain
algoritma Dijkstra dan
A*.
2.4.1.
Algoritma
A*
Algoritma
A*
pertama
kali
dikemukakan
oleh
P.
E. Hart,
N. J. Nilson,
dan
B.Raphael
(1986)
dalam
karya
ilmiah
mereka
beljudul
"A Formal
Basis for
the
Heuristic
Deterministic of
minimum Cost
Paths".
Menurut Luger dan
Stubblefield (1993b,
pl27-133),
Algoritma A*
yang
memiliki fungsi
dimana h(h)
:S biaya
minimum suatu rote dari
n
ke
titik tujuan.
Sedangkan algoritma A*
ada!ah algoritma yang
menerapkan heuristic untuk
melakukan
pencarian dan memiliki fungsi f(n)
=
g(n)
+
h(n)
dimana:
"
n
adalah titik
(node) yang terdapat pada saat
pencarian.
" f(n)
adalah
fungsi untuk
menentukan arah yang dipilih saat
melakukan
pencarian rote.
"
g(n)
adalah fungsi untuk
memperkirakan biaya
yang diperlukan dari
titik
yang
sekarang ke
titik tujuan.
"
H(n)
adalah
heuristic untuk
memperkirakan biaya yang
diperlukan dari
Titik yang sekarang ke
titik tujuan.
Kelebihan algoritma A*
adalah karena algoritma
ini
menggunakan heuristic
dalam
memperkirakan seberapajauh
suatu titik dengan tujuan. Dengan teknik
ini
dapat
 |