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  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

 Kaynakça 

Kategori:Çizge algoritmaları
Kategori:Arama algoritmaları