Algoritme A-Star (A*)

Algoritme A-Star (A*)

 Algoritme A-Star (A*),(ditemukan pertama kali oleh Peter Hart, Nils Nilsson, dan Bertram Raphael pada tahun 1968) adalah algoritme pencarian rute terpendek (shortest path) yang merupakan perbaikan dari Algoritme BFS[1] dengan memodifikasi fungsi heuristiknya untuk memberikan hasil yang optimal. Dimana menggabungkan fungsi heuristik [h(n)] dan jarak sesungguhnya/cost [g(n)].

Notasi Algoritme
f(n) = g(n) + h(n)

Keterangan:

  1. f(n) adalah jumlah dari g(n) dan h(n). ini adalah perkiraan jalur terpendek sementara. maka f(n) adalah jalur terpendek yang sebenarnya yang tidak ditelusuri sampai Algoritme A-Star (A*) diselesaikan.
  2. g(n)/Geographical Cost adalah total jarak yang didapat dari verteks awal ke verteks sekarang (halangan).
  3. h(n)/Heuristic Cost adalah perkiran jarak dari vertek sekarang (yang sedang dikunjungi) ke vertek tujuan. sebuah fungsi heuristic digunakan untuk membuat perkiraan seberapa jauh lintasan yang akan diambil ke vertek tujuan.

Comments

Post a Comment

Popular posts from this blog

Algoritma pencarian

  Algoritma pencarian Dalam  ilmu komputer , sebuah  algoritme pencarian  dijelaskan secara luas adalah sebuah algoritme yang menerima  masukan  berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Sebagian besar algoritme yang dipelajari oleh ilmuwan komputer adalah algoritme pencarian. Himpunan semua kemungkinan solusi dari sebuah masalah disebut  ruang pencarian . Algoritme  pencarian brute-force  atau pencarian naif/ uninformed  menggunakan metode yang sederhana dan sangat  intuitif  pada ruang pencarian, sedangkan algoritme pencarian  informed  menggunakan  heuristik  untuk menerapkan pengetahuan tentang struktur dari ruang pencarian untuk berusaha mengurangi banyaknya waktu yang dipakai dalam pencarian.
Read more