Algoritme A-star (A*)

Metode A-Star dikembangkan oleh Peter Hart, Nils Nilsson, dan Bertram Raphael. A* (disebut “A-star”) adalah sebuah graph atau metode pohon pencarian yang digunakan untuk mencari jalan dari sebuah node awal ke node tujuan yang telah ditentukan (Hart et al., 1968). Metode ini menggunakan “estimasi heuristic” dimana heuristik adalah penilai yang memberi harga pada tiap simpul yang memandu A* mendapatkan solusi yang diinginkan. Dengan heuristik yang benar, maka A* pasti akan mendapatkan solusi jika memang ada solusi yang dicari (Tilawah, 2010). Nilai Heuristik h(x) pada setiap node untuk mengurutkan setiap node x berdasarkan estimasi rute terbaik yang melalui node tersebut. Algoritme A* mencari jalur dengan cost terkecil dari node awal ke node berikutnya sampai mencapai node tujuan. Dalam penentuan rute terbaik, A* memiliki suatu fungsi yang dinotasikan dengan f(x) untuk menetapkan estimasi cost yang terkecil dari jalur yang dilalui node x. Adapun fungsi f(x) dapat dirumuskan sebagai berikut .(Irsyad dan Rasila, 2015).

f(x) = h(x) + g(x)

dimana,

f (x) : Biaya yang dibutuhkan

g(x) : Biaya yang ditempuh dari node asal

h(x) : Nilai perkiraan dari node saat ini hingga ke tujuan

Sebagai contoh berikut adalah sebuah diagram sederhana untuk menggambarkan

g(x):

Gambar 2.7 Contoh diagram (Hart et al., 1968)

        Pada gambar 2.7 dapat dilihat node awal adalah titik s, dan tiga titik lainya yaitu n1, n2 dan n3. Dimulai dari titk S menuju n1 dan n2. Dianggap nilai g(n1) dan g(n2) adalah 3 dan 7. Misalkan A* menghubungkan n1 dengan n3 dan n2, maka g(n3)=3+2=5 lebih rendah dibanding g(n2)=3+3=6. Fungsi h(x) adalah hyphotesis cost atau heuristic cost atau estimasi cost terkecil dari node x ke tujuan, yang disebut juga sebagai future pathcost. h(x) mewakili garis lurus jarak ke titik tujuan. Jarak diantara dua titik yang dapat dihitung dengan menggunakan Metode Harversine dan Metode Euclidean