A*(A star) 알고리즘 수도 코드(pseudocode)

---

이 글은 PC 버전 TISTORY에 최적화 되어있습니다.

포스팅 순서

1. 개념 및 구현

2. 수도코드(pseudocode)

3. 구현 및 최적화

수도코드

function A*(start, goal)
    // 이미 실행했던 노드들 '닫힌 목록'
    closedSet := {}

    // 아직 실행하지 않았지만 이제 탐색할 노드들 '열린 목록'
    // 초기에는, 시작 노드만 들어있습니다.
    openSet := {start}

    // 각가장 효율적인 경로를(노드들을) 담습니다.
    cameFrom := the empty map

    // 각 노드별 시작 노드로부터의 거리를 담습니다. (기본 비용은 Infinity, 최소비용을 찾는 것이므로)
    gScore := map with default value of Infinity

    // 처음 노드는 시작 노드이므로 gScore는 0입니다.
    gScore[start] := 0 

    // 시작 노드로부터의 비용, 목적 노드까지의 비용 두 가지가 합산된 비용입니다.
    fScore := map with default value of Infinity

    // 첫 번째 노드는 시작 노드로부터의 비용이 0이고, 목적 노드까지는 heuristic한 추정 비용입니다.
    // 그러므로, 첫 노드의 전체 비용은 추정값만 있을 뿐 입니다.
    fScore[start] := heuristic_cost_estimate(start, goal)

    // '열린 목록'이 비어있을 때까지 반복합니다.
    while openSet is not empty
        // '열린 목록'에서 가장 적은 f값을 가지는 노드
        current := the node in openSet having the lowest fScore[] value
        // 목적 노드입니까?
        if current = goal
            // 길 찾기를 완료하였으니 경로를 만듭니다.
            return reconstruct_path(cameFrom, current)

        // 목적노드가 아니라면 '열린 목록'에서 삭제하고 '닫힌 목록'에 넣습니다.
        openSet.Remove(current)
        closedSet.Add(current)

        // 최소 비용으로 선택한 노드의 인접 노드들을 바라봅니다.
        for each neighbor of current
            // 인접 노드가 이미 '닫힌 목록'에 들어있다면 무시하고 넘어갑니다. (이미 실행해 본것이므로)
            if neighbor in closedSet
                continue		

            // '열린 목록'에 들어있지 않다면 추가합니다.
            if neighbor not in openSet	
                openSet.Add(neighbor)
            
            // current 노드까지의 gScore + current 노드로부터 인접 노드까지 거리를 구합니다.
            // 시작 노드로부터 인접 노드까지 gScore가 current 노드를 거쳐 
            // 인접 노드까지 가는 비용보다 싸다면 이 경로는 무시합니다.
            tentative_gScore := gScore[current] + dist_between(current, neighbor)
            if tentative_gScore >= gScore[neighbor]
                continue		

            // current 노드를 거쳐서 가는 것이 더 좋다고 생각되면 기록합니다.
            cameFrom[neighbor] := current
            gScore[neighbor] := tentative_gScore
            fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)

    return failure

function reconstruct_path(cameFrom, current)
    total_path := [current]
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.append(current)
    return total_path

참고

- 위키디피아