Algoritma A* merupakan algoritma pencarian rute terpendek yang merupakan hasil pengembangan dari algoritma BFS dengan memodifikasi fungsi heuristik guna meningkatkan hasil yang optimal. Algoritma ini pertama kali ditemukan oleh Peter Hart, Nils Nilsson, dan Bertram Raphael pada tahun 1968.
Algoritma A* menjadi salah satu contoh algoritma yang paling dikenal di dunia. Algoritma ini dapat melakukan pemeriksaan pada node dengan menggabungkan g(n), yang merupakan cost yang diperlukan untuk mencapai sebuah node dan h(n), yang merupakan cost yang didapat dari node ke tujuan.
Section Artikel
Pengertian Algoritma A* (A-Star)
Algoritma A* (A-Star) adalah algoritma pencarian yang digunakan dalam pemrograman komputer dan kecerdasan buatan untuk mencari jalur terpendek atau solusi optimal antara dua titik dalam graf atau ruang pencarian.
Algoritma ini memadukan teknik pencarian breadth-first (pencarian melebar) dan heuristic (pemilihan berdasarkan perkiraan) untuk mencapai keseimbangan antara kecepatan dan optimalitas.
Algoritma A* bekerja dengan mengeksplorasi simpul-simpul (node) dalam graf secara berurutan, dimulai dari simpul awal dan bergerak ke simpul-simpul tetangga. Pada setiap langkah, algoritma memilih simpul berikutnya yang diharapkan memberikan jalur terpendek menuju tujuan berdasarkan estimasi heuristik.
Algoritma A* memiliki kelebihan dalam efisiensi dan kemampuan untuk menemukan jalur terpendek secara optimal jika heuristik yang digunakan adil dan konsisten. Oleh karena itu, algoritma ini sering digunakan dalam berbagai aplikasi, seperti perencanaan lintasan, permainan video, sistem navigasi, dan bidang lain yang membutuhkan pencarian jalur efisien.
Fungsi Algoritma A* (A- Star)
Fungsi utama dari algoritma A* adalah mencari jalur terpendek atau solusi optimal antara dua titik dalam graf atau ruang pencarian. Algoritma ini menggunakan kombinasi antara teknik pencarian breadth-first (pencarian melebar) dan heuristic (pemilihan berdasarkan perkiraan) untuk mencapai keseimbangan antara kecepatan dan optimalitas.
Adapun langkah-langkah umum dalam fungsi algoritma A*:
1. Inisialisasi
- Tentukan simpul awal dan simpul tujuan.
- Inisialisasi himpunan simpul terbuka (open set) yang berisi simpul yang akan diperiksa dan himpunan simpul tertutup (closed set) yang berisi simpul-simpul yang telah diperiksa.
2. Hitung biaya awal
Tentukan biaya awal untuk mencapai simpul awal (biasanya 0).
3. Evaluasi simpul awal
- Hitung perkiraan biaya sisa (estimated-cost-to-go) dari simpul awal ke simpul tujuan menggunakan fungsi heuristik.
- Hitung perkiraan biaya total (estimated-total-cost) dari simpul awal ke simpul tujuan dengan menambahkan biaya sejauh ini dan perkiraan biaya sisa.
4. Loop hingga menemukan solusi
- Pilih simpul dengan perkiraan biaya total terendah dari himpunan simpul terbuka.
- Pindahkan simpul terpilih dari himpunan simpul terbuka ke himpunan simpul tertutup.
- Periksa apakah simpul terpilih adalah simpul tujuan. Jika iya, maka telah ditemukan solusi optimal.
- Apabila bukan simpul tujuan, ekspansi simpul terpilih dan evaluasi simpul-simpul tetangga:
- Hitung biaya sejauh ini untuk mencapai simpul tetangga.
- Hitung perkiraan biaya sisa (estimated-cost-to-go) dari simpul tetangga ke simpul tujuan menggunakan fungsi heuristik.
- Hitung perkiraan biaya total (estimated-total-cost) dari simpul tetangga dengan menambahkan biaya sejauh ini dan perkiraan biaya sisa.
5. Apabila himpunan simpul terbuka kosong
Tidak ada solusi yang ditemukan. Jalur antara dua titik tidak dapat ditemukan.
6. Jika ditemukan solusi
Lakukan pencarian mundur dari simpul tujuan hingga simpul awal untuk mendapatkan jalur terpendek.
Fungsi utama dari algoritma A* adalah mengevaluasi dan memilih simpul-simpul dengan biaya terendah secara efisien berdasarkan perkiraan biaya sisa menggunakan fungsi heuristik.
Hal tersebut memungkinkan algoritma A* untuk mencari jalur terpendek atau solusi optimal dengan waktu eksekusi yang lebih cepat dibandingkan dengan metode pencarian yang hanya mengandalkan pencarian melebar seperti algoritma Dijkstra.
Cara Menghitung Algoritma A*
Berikut adalah cara menghitung algoritma A* secara sederhana:
1. Tentukan simpul awal (Start) dan simpul tujuan (Goal).
2. Inisialisasi himpunan simpul terbuka (Open Set) dan himpunan simpul tertutup (Closed Set).
3. Set biaya awal (G) simpul awal menjadi 0.
4. Hitung perkiraan biaya sisa (H) dari simpul awal ke simpul tujuan menggunakan fungsi heuristik.
5. Hitung perkiraan biaya total (F) dari simpul awal dengan menambahkan biaya sejauh ini (G) dan perkiraan biaya sisa (H).
6. Tambahkan simpul awal ke himpunan simpul terbuka.
7. Loop hingga himpunan simpul terbuka kosong
- Pilih simpul dengan biaya total (F) terendah dari himpunan simpul terbuka.
- Pindahkan simpul terpilih dari himpunan simpul terbuka ke himpunan simpul tertutup.
- Periksa apakah simpul terpilih adalah simpul tujuan. Jika iya, maka telah ditemukan solusi optimal.
- Jika bukan simpul tujuan, ekspansi simpul terpilih dan evaluasi simpul-simpul tetangga:
- Hitung biaya sejauh ini (G) untuk mencapai simpul tetangga.
- Hitung perkiraan biaya sisa (H) dari simpul tetangga ke simpul tujuan menggunakan fungsi heuristik.
- Hitung perkiraan biaya total (F) dari simpul tetangga dengan menambahkan biaya sejauh ini (G) dan perkiraan biaya sisa (H).
- Periksa apakah simpul tetangga sudah ada di himpunan simpul terbuka atau simpul tertutup. Jika iya, periksa apakah biaya sejauh ini (G) lebih baik daripada yang sebelumnya. Jika iya, perbarui biaya sejauh ini (G) dan penghubungnya.
- Jika simpul tetangga belum ada di himpunan simpul terbuka, tambahkan simpul tetangga ke himpunan simpul terbuka.
8. Apabila himpunan simpul terbuka kosong
Tidak ada solusi yang ditemukan. Jalur antara dua titik tidak dapat ditemukan.
9. Jika ditemukan solusi
Lakukan pencarian mundur dari simpul tujuan hingga simpul awal untuk mendapatkan jalur terpendek.
Dalam penghitungan algoritma A*, penting untuk memperhatikan fungsi heuristik yang digunakan untuk perkiraan biaya sisa (H). Fungsi heuristik harus adil (admissible) dan konsisten (consistent) agar algoritma A* dapat memberikan solusi optimal.
Contoh Algoritma A*
Untuk mendalami pemahaman mengenai algoritma A*, berikut contoh soal algoritma A*.
1 Indeks berjarak 150 Meter
- A = Rumah Sakit Soedarso
- B = Perempatan Jl. Mayor Alianyang
- C = Bundaran Jl. Arteri Supadio
- D = Pertigaan Jl. Parit Bugis dan Jl. Adisucipto
- E = Pertigaan Jl. Parit Bugis dan Jl. Arteri Supadio
- F = Pertigaan Jl. Wonodadi dan Jl. Adisucipto
- G = Pertigaan Jl. Wonodadi dan Jl. Arteri Supadio
- H = Bandara Supadio
Nilai Heuristik
- A ke B (0,8) (6,9) = 6,08
- A ke C (0,8),(7,5) = 7,62
- B ke D (6,9),(25,11) = 19,10
- B ke C (6,9),(7,5) = 4,12
- C ke B (7,5),(6,9) = 4,12
- C ke E (7,5),(22,6) = 15,03
- D ke F (25,11),(28,10) = 3,16
- D ke E (25,11),(22,6) = 5,83
- E ke D (22,6),(25,11) = 5,83
- E ke G (22,6),(27,5) = 5,10
- F ke G (28,10),(27,5) = 5,10
- F ke H (28,10),(36,2) = 11,31
- G ke F (27,5),(28,10) = 5,10
- G ke H (27,5),(36,2) = 9,49
Nilai f(n)
- A ke B = 6+6,08 = 12,08
- A ke C = 9+7,62 = 16,62
- B ke D = 23+19,10 = 42,10
- B ke C = 5+4,12 = 9,12
- C ke B = 5+4,12 = 9,12
- C ke E = 16+15,03 = 31,03
- D ke F = 4+3,16 = 7,16
- D ke E = 8+5,83 = 13,83
- E ke D = 8+5,83 = 13,83
- E ke G = 6+5,10 = 11,10
- F ke G = 6+5,10 = 11,10
- F ke H = 16+ 11,31 = 27,31
- G ke F = 6+5,10 = 11,10
- G ke H = 12+9,49 = 21,49
Jalur yang dilalui adalah A-B-C-E-G-F-H
Total f(n) = 12,08+9,12+31,03+11,10+11,10+27,31 = 101,74
