Fungsi MBDA* pada Heuristik

Heuristic berasal dari bahasa Yunani, heuriskein, yang berarti ‘mencari’ atau ‘menemukan’. 

Dalam dunia pemrograman, heuristik adalah lawan kata dari algoritmik.

Heuristik ? fungsi yang memberikan suatu nilai berupa biaya perkiraan (estimasi) dari suatu solusi.

A*

Gabungan Uniform Cost Search dan Greedy Best-First Search. 

Biaya yang diperhitungkan didapat dari biaya sebenarnya ditambah dengan biaya perkiraan. 

f(n) = g(n) + h(n)

Complete dan Optimal

Suatu fungsi dapat diterima sebagai fungsi heuristik jika biaya perkiraan yang dihasilkan tidak melebihi dari biaya sebenarnya. 

Jika fungsi heuristik overestimate, maka proses pencarian bisa tersesat dan tidak optimal.

Suatu fungsi heuristik dikatakan baik jika bisa memberikan biaya perkiraan yang mendekati biaya sebenarnya. 

Semakin mendekati biaya sebenarnya, fungsi heuristik tersebut semakin baik.

Modified Bi-directional A* (MBDA*)

Merupaka fungsi heuristik yang menggunakan 2 pencarian sekaligus

- Fungsi heuristik untuk simpul n pada pencarian maju (dari S ke G): 

        - Fungsi heuristik untuk simpul n pada pencarian mundur (dari G ke S):

Symbol-simbol di MBDA*

S : simpul asal atau initial state 

G : simpul tujuan atau goal state 

g(S,n) : biaya sebenarnya dari S ke n 

g(G,n) : biaya sebenarnya dari G ke n 

hs(n) : biaya perkiraan dari n ke G 

hg(n) : biaya perkiraan dari n ke S 

untuk lebih jelas , ini contoh heuristic dengan fungsi MBDA*

Pada contoh diatas, 2 pencarian dilakukan dari S ke G dan sebaliknya. Pada table tersebut telah diperkirakan biayanya. Selanjutnya

Kalkulasikan biaya dengan cabang-cabang tersebut dan ambil yang  nilainya lebih kecil baik dari jarak atau dari perkiraan biaya.

Selanjutnya lakukan pencarian kembali dan yang S maju ke G, begitu juga sebaliknya

Bandingkan kembali dengan perkiraan sebelumnya ternyata lewat A kemungkinannya  lebih dekat

Di langkah ini titk G & S menemukan titik