A* arama algoritması

A* arama algoritması, sezgisel bir çizge dolaşma ve yol bulma algoritmasıdır. Tamlığı, optimalliği ve optimal verimliliği ile bilgisayar biliminin birçok alanında kullanılmaktadır. Tüm düğümleri belleğinde tuttuğundan ${\displaystyle O(b^{d})}$ olan alan karmaşıklığı dezavantajıdır.

A* arama algoritması
A* algoritmasının engel bulunan bir uzayda hedefe giden yolu bulması.
Sınıf	Arama algoritması
Veri yapısı	Çizge
Zaman karmaşıklığı	${\displaystyle O(|E|)=O(b^{d})}$
Alan karmaşıklığı	${\displaystyle O(|V|)=O(b^{d})}$

İlk olarak 1968'de Stanford Araştırma Enstitüsü'nden Peter Hart, Nils Nilsson ve Bertram Raphael tarafından yayınlanmıştır.

Sözde kod

function reconstruct_path(cameFrom, current)  total_path := {current}  while current in cameFrom.Keys:  current := cameFrom[current]  total_path.prepend(current)  return total_path function A_Star(start, goal, h)  openSet := {start}  cameFrom := an empty map  gScore := map with default value of Infinity  gScore[start] := 0  fScore := map with default value of Infinity  fScore[start] := h(start)  while openSet is not empty  current := the node in openSet having the lowest fScore[] value  if current = goal  return reconstruct_path(cameFrom, current)  openSet.Remove(current)  for each neighbor of current  tentative_gScore := gScore[current] + d(current, neighbor)  if tentative_gScore < gScore[neighbor]  cameFrom[neighbor] := current  gScore[neighbor] := tentative_gScore  fScore[neighbor] := tentative_gScore + h(neighbor)  if neighbor not in openSet  openSet.add(neighbor)  return failure 

Kaynakça

1. ^ Russell, Stuart; Norvig, Peter (2020). Artificial Intelligence: A Modern Approach (4. bas.). Pearson Education. s. 108. ISBN . 
2. ^ Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics. 4 (2): 100-107. doi:10.1109/TSSC.1968.300136.