A* arama algoritması
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ığı | |
Alan karmaşıklığı |
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.[1] Tüm düğümleri belleğinde tuttuğundan olan alan karmaşıklığı dezavantajıdır.
İlk olarak 1968'de Stanford Araştırma Enstitüsü'nden Peter Hart, Nils Nilsson ve Bertram Raphael tarafından yayınlanmıştır.[2]
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
- ^ Russell, Stuart; Norvig, Peter (2020). Artificial Intelligence: A Modern Approach (4. bas.). Pearson Education. s. 108. ISBN 978-1-292-40113-3.
- ^ 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.