İçeriğe atla

A* arama algoritması

Vikipedi, özgür ansiklopedi
A* arama algoritması
A* algoritmasının engel bulunan bir uzayda hedefe giden yolu bulması.
SınıfArama 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]

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
  1. ^ Russell, Stuart; Norvig, Peter (2020). Artificial Intelligence: A Modern Approach (4. bas.). Pearson Education. s. 108. ISBN 978-1-292-40113-3. 
  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.