A* algoritması; ilk olarak 1968 yılında Peter Hart,Nils Nilsson ve Bertram Raphael tarafından teorik olarak geliştirilen A search algoritmasının daha sonra geliştirilmesiyle elde edilmiştir. Bilgisayar ortamında, A* algoritması en iyi ilk sırada olan çözümü bulan,verilen noktalar arası en kısa maliyetli yolu üreten algoritma olarak bilinir. Bu algoritma ağaç yapısı üzerindeki noktaları tanımlarken her bir node için mesafe sezgisel fonksiyon dan oluşan bir f(n) fonksiyonu oluşturur.Bu f(n) fonksiyonu g(n) ve h(n) fonksiyonunun toplamıdır: f(n)=g(n)+h(n).
Noktalar arası gerçek mesafeyi (yol maliyetini) g(n) fonksiyonu, sezgisel tahmin fonksiyonunu h fonksiyonu belirtmektedir. h(n) fonksiyonu sezgisel tahmini fonksiyon olduğundan mutlaka başlangıçtan belirttiğimiz hedefe olan mesafeden küçük bir değer olmalıdır. Bu yüzden yol bulma veya yol planlaması problemlerinde h(n) değeri,noktalar arası fiziksel olarak mevcut olan yoldan daha kısa yol olan kuşbakışı mesafe değeri ölçümüyle elde edilir. A* search algoritması rota üzerindeki bütün noktaları başlangıçtan hedef noktaya varıncaya kadar en kısa mesafeli çözümü elde edinceye kadar araştırır. Bu araştırmayı yaparken OPENLIST ve CLOSELIST yapılarını oluşturur ve hedef nokta oluşunca bu yapılar yardımıyla bir rota belirlenir.
A* algoritmasının adım adım işleyişi aşağıdaki gibidir:
- Başlangıç node unu OPENLIST e al ve maliyet f(n) fonksiyonunu hesapla.
- En küçük f(n) maliyet fonksiyonlu node u seç ve OPENLIST ten kaldırıp CLOSELIST e ekle.
- Hedef noktasına ulaşılıp ulaşımadığını kontrol et,eğer hedefe ulaşılmış ise algoritmayı sonlandır.Aksi halde algoritmaya devam et.
- Hedef noktaya ulaşılıncaya kadar CLOSELIST’e atılmamış bütün successor lar için maliyet fonksiyonlarını hesapla.
- Bunları listelere alınmamış successor maliyetleri ile karşılaştır ve OPENLIST’e al
- OPENLIST’e sonradan tekrar atılabilecek aynı eleman için f(n) değerlerini karşılaştır ve küçük f(n) değeri olanı seç
- Adım 2 ye git
