Algoritma A* (A star) Search

• Sejarah

Pada tahun 1964 Nils Nilsson menemukan heuristik berdasarkan pendekatan untuk menambah kecepatan pada Algoritma Dijkstra. Algoritma ini disebut dengan A1. Pada tahun 1967 Bertram Raphael membuat perbaikan-perbaikan dramatis atas algoritma ini, tapi gagal menunjukkan keoptimasiannya. Ia menyebut algoritma ini A2. Kemudian pada tahun 1968 Peter E. Hart memperkenalkan sebuah argumen yang membuktikan A2 optimal ketika menggunakan heuristik konsisten hanya dengan perubahan kecil. Pembuktiannya atas algoritma tersebut juga termasuk bagian yang menunjukkan bahwa algoritma A2 yang baru adalah algoritma terbaik. 

Maka dari itu, ia menamai algoritma baru ini dalam sintaksis Kleene star untuk menjadi algoritma yang berawal dari A dan memasukkan semua nomor-nomor yang mungkin dari A*.

Dalam sains komputer, A* (dibaca “A star”) adalah algoritma komputer yang digunakan secara luas dalam mencari jalur (pathfinding) dan grafik melintang (graph traversal), proses plotting sebuah jalur melintang secara efisian antara titik-titik, disebut node. Terkenal karena penampilan dan akurasinya, algoritma ini diperluas untuk berbagai bidang. A* mencapai penampilan yang lebih baik dengan menggunakan heuristik.

• Deskripsi

  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 di pohon (tree).

untuk lebih jelasnya, silahkan download link di bawah ini 

http://web.unair.ac.id/admin/file/f_22581_Algoritma_A_star_search.pptx