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ığı	$O(|E|)=O(b^{d})$
Alan karmaşıklığı	$O(|V|)=O(b^{d})$

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 $O(b^{d})$ 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.

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