Algoritma A* ( A star )

Salah satu algoritma yang dipelajari untuk menyelesaikan permasalahan adalah algoritma A* (A Star). Algoritma A* menyelesaikan masalah yang menggunakan graf untuk perluasan ruang statusnya. Dengan kata lain digunakan untuk menyelesaikan permasalah yang bisa direpresentasikan dengan graf. Algoritma A* adalah sebuah algoritma yang telah diperkaya. Dengan menerapkan suatu heuristik, algoritma ini membuang langkah-langkah yang tidak perlu dengan pertimbangan bahwa langkah-langkah yang dibuang sudah pasti merupakan langkah yang tidak akan mencapai solusi yang diinginkan.

Algoritma A* membangkitkan simpul yang paling mendekati solusi. Simpul ini kemudian disimpan suksesornya ke dalam list sesuai dengan urutan yang paling mendekati solusi terbaik. Kemudian, simpul pertama pada list diambil, dibangkitkan suksesornya dan kemudian suksesor ini disimpan ke dalam list sesuai dengan urutan yang terbaik untuk solusi. List simpul ini disebut dengan simpul terbuka(open node).

Simpul pada list bisa berasal dari kedalaman berapapun dari graf. Algoritma ini akan mengunjungi secara mendalam (mirip DFS) selama simpul tersebut merupakan simpul yang terbaik. Jika simpul yang sedang dikunjungi ternyata tidak mengarah kepada solusi yang diinginkan, maka akan melakukan runut balik ke arah simpul akar untuk mencari simpul anak lainnya yang lebih menjanjikan dari pada simpul yang terakhir dikunjungi. Bila tidak ada juga, maka akan terus mengulang mencari ke arah simpul akar sampai ditemukan simpul yang lebih baik untuk dibangkitkan suksesornya. Strategi ini berkebalikan dengan algoritma DFS yang mencari sampai kedalaman yang terdalam sampai tidak ada lagi suksesor yang bisa dibangkitkan sebelum melakukan runut balik, dan BFS yang tidak akan melakukan pencarian secara mendalam sebelum pencarian secara melebar selesai. A* baru berhenti ketika mendapatkan solusi yang dianggap solusi terbaik.

Algoritma A* menerapkan teknik heuristik dalam membantu penyelesaian persoalan. 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 solusinya) yang dicari. Dengan kata lain, heuristik adalah fungsi optimasi yang menjadikan algoritma A* lebih baik dari pada algoritma lainnya. Namun heuristik masih merupakan estimasi / perkiraan biasa saja Sama sekali tidak ada rumus khususnya. Artinya, setiap kasus memiliki fungsi heuristik yang berbedabeda. Algoritma A* ini bisa dikatakan mirip dengan algoritma Dijkstra, namun pada algoritma Dijkstra, nilai fungsi heuristiknya selalu 0 (nol) sehingga tidak ada fungsi yang mempermudah pencarian solusinya.

Algoritma  A* dapat dijelaskan dengan pseudocode dibawah ini

1. Masukan node awal ke openlist
2. Loop Langkah – langkah di bawah ini :
   • Cari node (n) dengan nilai f(n) yang paling rendah dalam open list. Node ini sekarang menjadi current  node.
   • Keluarkan current node dari openlist dan masukan ke close list
   • Untuk setiap tetangga dari current node lakukan berikut :
   1. Jika tidak dapat dilalui atau sudah ada dalam close list, abaikan.
   2. Jika belum ada di open list . Buat current node parent dari node tetangga ini. Simpan nilai f,g dan h dari node ini.
   3. Jika sudah ada di open list, cek bila node tetangga ini lebih baik, menggunakan nilai g sebagai ukuran. Jika lebih baik ganti parent dari node ini di openlist menjadi current node, lalu kalkulasi ulang nilai g dan f dari node ini.
   • Hentikan loop jika : 
   1. Node tujuan telah ditambahkan ke openlist, yang berate rute telah ditemukan.
   2. Belum menemukan node goal sementara open list kosong atau berarti tidak ada rute.
3. Simpan rute. Secara ‘backward’, urut mulai darinode goal ke parent-nya terus sampai mencapai node awal sambil menyimpan node ke dalam sebuah array.