20
Jika
perhitungan
algoritma A
Star
dilakukan
pada
grid,
maka
fungsi
heuristic
yang tepat adalah
menggunakan manhattan distance. Sedangkan untuk algoritma A Star
pada
graph,
fungsi
heuristic
yang
tepat
adalah
straight
line
distance
dimana
hasil
yang
didapat
akan
mempunyai cost
yang
lebih
kecil
daripada
fungsi
heuristic
manhattan
distance dan diagonal
distance.
Apabila pada grid nilai g untuk vertikal, horizontal dan diagonalnya dianggap
sama, fungsi heuristic yang tepat adalah dengan menggunakan heuristic diagonal
distance. (Mario, Irawan, Aryo, 2004, p150)
2.8
Algoritma Pathfinding
Tujuan
dari
algoritma
pathfinding
adalah
untuk
menemukan jalur
terbaik
dari
vertex awal
ke
vertex akhir.
Secara
umum
algoritma
pathfinding
digolongkan
menjadi
dua jenis (Russel, Stuart dan Peter Norvig, 1995, 73), yaitu :
1.
Algoritma Uniformed
Search
Algoritma
uniformed
search
adalah algoritma yang tidak memiliki keterangan
tentang jarak atau biaya dari path dan tidak
memiliki pertimbangan akan
path
mana
yang
lebih
baik.
Yang
termasuk
dalam
algoritma
ini
adalah
algoritma
Breadth-First
Search.
2.
Algoritma Informed Search
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
termasuk
algoritma
ini
adalah algoritma Dijkstra dan algoritma A*.
 |