ALGORITMA A*(A STAR): PENGERTIAN, CARA KERJA, DAN KEGUNAANNYA

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

Oleh Trivusi Diperbarui: 20 Januari 2023 Posting Komentar

Algoritma pencarian merupakan algoritma yang dirancang untuk mencari atau mengambil elemen dari struktur data, tempat data tersebut disimpan.

Aspek vital dari algoritma pencarian adalah path finding, yang digunakan untuk menemukan jalur yang dapat diambil untuk melintasi dari satu titik ke titik lainnya, dengan mencari rute yang paling optimal.

Salah satu algoritma pencarian yang digunakan sebagai path finding adalah algoritma A* atau A Star.

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.