Algoritma A* (A Star): Pengertian, Cara Kerja, dan Kegunaannya

Algoritma A* (A Star): Pengertian, Cara Kerja, dan Kegunaannya

Pengertian Algoritma A* (A star)

Algoritma A* (A Star) adalah algoritma pencarian yang digunakan untuk menemukan jalur terpendek antara titik awal dan akhir.

Algoritma ini sering digunakan untuk penjelajahan peta guna menemukan jalur terpendek yang akan diambil. 

A* awalnya dirancang sebagai masalah penjelajahan graph (graph traversal), untuk membantu robot agar dapat menemukan arahnya sendiri. A* saat ini masih tetap menjadi algoritma yang sangat populer untuk graph traversal.

Algoritma A* mencari jalur yang lebih pendek terlebih dahulu, sehingga menjadikannya algoritma yang optimal dan lengkap.Cara Kerja Algoritma A*

A* menggunakan Best First Search (BFS) dan menemukan jalur dengan biaya terkecil (least-cost path) dari node awal (initial node) yang diberikan ke node tujuan (goal node).

Algoritma ini menggunakan fungsi heuristik jarak ditambah biaya (biasa dinotasikan dengan f(x)) untuk menentukan urutan di mana search-nya melalui node-node yang ada pada tree.

Notasi yang dipakai oleh algoritma A* adalah sebagai berikut:

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

dimana

f(n) = biaya estimasi terendah

g(n) = biaya dari node awal ke node n

h(n) = perkiraan biaya dari node n ke node akhirAdapun langkah-langkah yang dilakukan oleh algoritma A* adalah sebagai berikut:

Inisialisasi OPEN LIST

Letakkan simpul awal pada OPEN LIST

Inisialisasi CLOSE LIST

Ikuti langkah-langkah berikut sampai OPEN LIST tidak kosong:

Temukan simpul dengan f terkecil pada OPEN LIST dan beri nama "Q".

Hapus Q dari OPEN LIST.

Generate delapan turunan Q dan tetapkan Q sebagai induknya.

Untuk setiap keturunan:

Jika menemukan penerus adalah tujuannya, pencarian dihentikan

Jika tidak, hitung g dan h untuk penerusnya.

penerus.g = q.g + jarak yang dihitung antara penerus dan q.

suksesor.h = jarak terhitung antara suksesor dan tujuan.

penerus.f = penerus.g ditambah penerus.h

Lewati penerus ini jika node dalam daftar OPEN dengan lokasi yang sama tetapi nilai f lebih rendah dari penggantinya.

Lewati penerusnya jika ada simpul dalam CLOSE LIST dengan posisi yang sama dengan penerusnya tetapi nilai f lebih rendah; jika tidak, tambahkan simpul ke ujung OPEN LIST (untuk loop).

Push Q ke dalam CLOSE LIST dan akhiri loop sementara.

Kegunaan Algoritma A*

Algoritma A* menemukan jalur terpendek antara dua node dalam sebuah graph. Algoritma ini mirip dengan algoritma Dijkstra, tetapi lebih canggih karena mempertimbangkan biaya setiap sisi (edge) dalam graph. Biaya tepi (edge cost) biasanya ditentukan oleh panjangnya atau ukuran jarak lainnya, seperti waktu atau uang.

Berikut ini adalah beberapa aplikasi dan kegunaan dari algoritma A*:

Algoritma A* biasanya digunakan dalam peta dan game berbasis web untuk menemukan jalur terpendek dengan efisiensi setinggi mungkin.

A* digunakan di banyak aplikasi kecerdasan buatan, seperti mesin pencari.

Digunakan dalam algoritma lain seperti algoritma Bellman-Ford untuk menyelesaikan masalah jalur terpendek.

Algoritme A* digunakan dalam protokol routing jaringan, seperti RIP, OSPF, dan BGP, untuk menghitung rute terbaik antara dua node.