A*(에이스타) 알고리즘

주어진 출발 꼭짓점에서부터, 목표 꼭짓점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 중 하나

• 다익스트라 알고리즘은 시작 노드만을 지정하여 다른 모든 노드에 대한 최단 경로를 파악하지만,
• 에이스타 알고리즘은 시작 노드 & 목적지 노드를 분명하게 지정
• 또한 에이스타 알고리즘은 휴리스틱 추정값을 통해 알고리즘을 개선

---

어떻게 작동할까?

• 1) 시작점 A를 '열린 목록'에 넣음

다음의 과정을 반복

• 2) '열린 목록'에서 가장 낮은 F 비용을 찾아 현재 지역으로 선택
  그리고 선택된 지역은 '열린 목록'->'닫힌 목록'으로 넣음
• 3) 선택한 지역의 인접 지역에 대해 모두 탐색
  • 인접 지역이 '열린 목록'에 있지 않다면
    => '열린 목록'에 추가하고, 해당 지역의 부모를 현재 지역으로 설정함. 또한 해당 지역의 F, G, H 비용을 기록함.
  • 인접 지역이 이미 '열린 목록'에 있다면
    => G 비용을 이용하여 어떤 G 비용이 작은지 즉, 경로가 개선되는지 확인하고, 개선된다면 인접 지역의 부모를 해당 지역으로 설정함. 그리고 인접 지역의 G, F 비용을 다시 계산함.
• 4) 아래의 경우에는 그만둠
  • 목표 지역을 '열린 목록'에 추가함
  • '열린 목록'이 비어있게 됨.
    => 목표 사각형을 찾는 데 실패
    => 길이 없는 경우

---

Pseudo code

// 시작점 ~ 현재 지역까지 위치 경로 반환하는 함수
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은 보통 hash-set보다는, min-heap 또는 priority queue로 많이 구현됩니다.
    // min-heap이나 priority queue로 구현되면, 시간복잡도가 O(Log(N))이 됩니다.
    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 := openSet 내에 존재하고, fSocre[]값이 제일 낮은 노드
        if current = goal
            return reconstruct_path(cameFrom, current)
        openSet.Remove(current)
        
        // 인접 지역들 확인하는 과정
        for each neighbor of current
            // d(current,neighbor): 현재 지역에서 인접 지역까지의 거리
            // tentative_gScore: 시작점에서 현재 지역을 거쳐 인접 거리까지의 거리
            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)

    // Open set is empty but goal was never reached
    return failure

cameFrom: 부모 (직전 지역이 어디인지)

---

참고

• https://itmining.tistory.com/66ttps://youtu.be/pUZhNMAqLbI?si=BkyF9-O_lT7Xz3gt
  어려운 알고리즘인데 예제를 통해 정말 쉽게 설명해 주신다...
• https://en.wikipedia.org/wiki/A*_search_algorithm