Algoritma A* adalah algoritma yang mana penyelesaikan masalah menggunakan graf
untuk perluasan ruang statusnya. 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.
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* menggabungkan jarak estimasi/heuristik [h(n)]
dan jarak sesungguhnya/cost [g(n)] dalam membantu penyelesaian persoalan.
Heuristik adalah nilai yang memberi harga pada tiap simpul yang memandu A*
mendapatkan solusi yang diinginkan. Dengan heuristik, maka A* pasti akan
mendapatkan solusi (jika memang ada solusinya). 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 berbeda-beda.
wah saya baru tau kalau ada algoritma A*, bedanya apa ya gan dari pada algoritma yang lain, kan sama sama menyelesaikan persoalan ? ^^
BalasHapus