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.

Algoritma yang optimal akan menemukan hasil yang paling murah dalam hal biaya untuk suatu masalah, sedangkan algoritma yang lengkap menemukan semua hasil yang mungkin dari suatu masalah.

Aspek lain yang membuat A* begitu powerful adalah penggunaan graph berbobot dalam penerapannya. Graph berbobot menggunakan angka untuk mewakili biaya pengambilan setiap jalur atau tindakan.

Ini berarti bahwa algoritma dapat mengambil jalur dengan biaya paling sedikit, dan menemukan rute terbaik dari segi jarak dan waktu.

Adapun kelemahan utama dari algoritma ini adalah kompleksitas ruang dan waktunya. Algoritma A* membutuhkan banyak ruang untuk menyimpan semua kemungkinan jalur dan banyak waktu untuk menemukannya

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 akhir

Contoh cara kerja algoritma A*

Adapun 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* biasanya digunakan dalam peta dan game berbasis web untuk menemukan jalur terpendek dengan efisiensi setinggi mungkin.

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

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

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

Komentar

Posting Komentar

Postingan populer dari blog ini

Operator dan Ekspresi Logika

  OPERATOR DAN EKSPRESI LOGIKA Setiap jenis-jenis operator logika memiliki karakteristik dan fungsi yang berbeda-beda. Kamu akan menemukannya saat belajar pemrograman jenis-jenis PHP. Operator merupakan dasar dari sebuah bahasa pemrograman jenis apa pun. Saat membuat suatu program, akan ada banyak data yang diolah sehingga menghasilkan output. Nantinya, operator dibutuhkan saat mengolah data yang memiliki peran sebagai simbol dari tanda baca. Secara umum, tujuan operator yaitu untuk membantu para programmer dalam mengoperasikan operand. Sedangkan operator logika berfungsi untuk memeriksa kesamaan nilai dari dua data atau lebih. Operator logika juga difungsikan sebagai ekspresi yang dapat mengembalikan nilai bertipe Boolean. Operator logika memiliki berbagai macam jenis dengan masing-masing simbolnya. Berikut ini adalah jenis jenis operator logika dasar secara lengkap. Jenis-Jenis Operator Logika dalam PHP Mengutip buku Buku Sakti Pemrograman Web Seri PHP karya Mundzir MF, bahwa operato
Baca selengkapnya

Permainan yang Disediakan di Blockly Games, Informatika Kelas 8 SMP

  8 Permainan dalam Blockly Games 1. Puzzle Pemain harus menyusun blok-blok yang berisi keterangan dan foto hewan ke blok hewan yang sesuai. Melalui permainan ini, kalian juga dapat belajar tentang kosakata dalam bahasa Inggris dan informasi tentang beberapa hewan. 2. Maze Permainan menggerakkan sprite agar berjalan sampai tujuan. Permainan ini mampu mengasah kemampuan logika berpikir. 3. Bird Permainan mengasah logika menggerakkan bird agar dapat mengambil cacing dan sampai ke sarangnya. 4. Turtle Permainan mengenal pola dengan karakter turtle yang digunakan. 5. Movie Belajar animasi dengan media sprite sederhana dan menggerakkannya sesuai animasi. 6. Music Permainan membuat musik dengan instruksi yang sudah disediakan. 7. Pond Tutor Permainan Pond Tutor ini mengajak pengguna belajar tentang Javascript. 8. Pond Permainan yang menggunakan blok kode dalam bentuk Javascript
Baca selengkapnya

Berlangsung Secara Hybrid, "Code The Ocean" Mengajak Anak Menjaga Laut Melalui Pemrograman

  Berlangsung Secara Hybrid, "Code The Ocean" Mengajak Anak Menjaga Laut Melalui Pemrograman koding merupakan salah satu tindakan dari langkah-langkah pemrograman dengan menuliskan kode dalam bahasa pemrograman. Berkaitan dengan hal ini, Koding Next Indonesia sebagai sekolah pemrograman terbesar di Asia Tenggara mengadakan Kompetisi Koding Anak Nasional yang kedua melalui program CSR.  Acara tersebut berjudul "Code The Ocean". Acara ini menantang siswa-siswa SD-SMP di Indonesia untuk mempelajari teknologi masa depan melalui lomba membuat permainan sederhana menggunakan coding, Kids. Selain itu, coding juga bisa mengasah keterampilan lunak, seperti pemecahan masalah dan berpikir logis untuk menghasilkan karya digital. Acara kompetisi "Code The Ocean" berlangsung secara hybrid di beberapa lokasi, seperti Jakarta, Tangerang Selatan, Bandung, Surabaya, Medan, Denpasar, Samarinda, dan online. Terdapat dua kategori dipertandingkan dalam acara tersebut, yakni: 1.
Baca selengkapnya