30
sama. Input
sering disebut argumen fungsi, sedangkan output
disebut nilai
fungsi.
Fungsi heuristic
digunakan untuk mengevaluasi keadaan-keadaan
problema individual dan menentukan seberapa jauh hal tersebut dapat
digunakan untuk mendapatkan solusi yang diinginkan.
Menurut Amit. J. Patel (2003, p1), heuristic merupakan aturan-aturan
untuk memilih cabang-cabang yang memiliki kemungkinan mengarah pada
pemecahan masalah. Heuristic dapat membantu menunjukkan arah yang tepat
bagi suatu algoritma, tetapi mungkin juga gagal dalam
memberikan petunjuk
kepada algoritma tersebut.
h(x) bagian dari f(x) fungsi harus menjadi heuristik diterima, yaitu
tidak harus melebih-lebihkan jarak ke tujuan. Jadi, untuk aplikasi seperti
fisik yang mungkin jarak terkecil antara dua titik atau node.
Jika heuristik h memenuhi kondisi tambahan
untuk setiap sisi ( x,
y
) dari grafik (di mana d menunjukkan panjang tepi itu), maka h disebut
monoton, atau konsisten . Dalam kasus seperti itu, A* dapat dilaksanakan
dengan lebih efisien-berbicara kasar, tidak ada node perlu diproses lebih dari
sekali (lihat ditutup ditetapkan di bawah) dan A* setara dengan menjalankan
algoritma Dijkstra dengan mengurangi biaya d '(x, y): = d (x, y) -
h (x) + h
(y).
Seperti pencarian breadth-first , A * adalah lengkap dan akan selalu
menemukan solusi jika ada. Jika heuristik fungsi h adalah diterima , artinya tidak
pernah overestimates biaya minimal sebenarnya mencapai tujuan, maka A * itu
sendiri diterima (atau optimal ) jika kita tidak menggunakan satu set tertutup. Jika
 |