[알고리즘] 그래프 : A*(asterisk) 알고리즘

 

 

A* 알고리즘은 최단 경로 탐색 알고리즘으로,

다익스트라(Dijkstra) 알고리즘의 장점에 휴리스틱(Heuristic) 개념을 결합한 형태이다.

 

A* 이름의 뜻은

A  :  탐색 알고리즘,
*  : 최적(Optimal), 최선(Best) 버전

즉, A*는 “최적의 탐색 알고리즘(Optimal Graph Search Algorithm)” 이라는 의미를 담고 있다.

 

 

 

 

00. 다익스트라 알고리즘

다익스트라는 현재까지의 누적 거리(비용)를 기준으로 비용이 가장 작은 노드부터 탐색해 나간다. 

 

1. 각 노드의 누적 거리 + 다음 노드로의 이동 비용을 계산해 비용이 가장 작은 노드를 우선적으로 방문
2. 우선순위 큐(Priority Queue)에 저장하고,
3. 목적지에 도달하면 즉시 탐색을 종료할 수 있다.

이 방식은 최적의 해를 찾지만,

목표가 멀리 있거나 불필요한 방향으로 탐색이 확장될 때 비효율적일 수 있다.

 

 

 

 

01. A*(asterisk) 알고리즘

A* 알고리즘은 다익스트라의 탐색 방식에 “목표까지의 예상 거리”
즉, 휴리스틱(Heuristic)을 추가로 고려한다. 

 

• 각 노드는 위과 같은 총 비용으로 평가 된다. 

기호	의미
g(n)	시작점에서 현재 노드까지의 실제 누적 비용
h(n)	현재 노드에서 목표까지의 예상(추정) 비용 (휴리스틱)
f(n)	전체 예상 비용 (탐색 우선순위 기준)

 

A*는 f(n) 값이 가장 작은 노드부터 탐색하므로, 불필요한 경로를 줄이고 목표 방향으로 효율적으로 이동할 수 있다.

 

 

 

 

02. 휴리스틱 이란? 

휴리스틱은 완벽한 계산 대신 경험적, 직관적인 예측 방법.
즉, “정확하진 않지만 그럴듯한 추정”을 하는 방식이다.

 

예를 들어:

• 미로에서 “출구는 아마 동쪽일 것이다”라고 판단하는 것
• 수학 문제를 근사값으로 접근하는 것

이 모두가 휴리스틱적 접근.

• A* 알고리즘에서의 휴리스틱 함수 h(n)는 “목표까지 남은 거리나 비용을 대략적으로 예측” 하는 역할을 합니다.

 

 

 

03. 휴리스틱 설계의 핵심 

좋은 휴리스틱을 만드는 핵심은 수학보다 문제의 세계관 이해력 이다.

즉, “이 문제에서 ‘가까워진다’는 게 무슨 뜻인가?”를 정의하는 것이 중요

 

문제 유형	노드 의미	이동 비용	휴리스틱 설계 방식
네비게이션(지도)	도시, 교차로	거리(km)	직선거리 (Euclidean Distance)
8퍼즐 / 루빅스 큐브	블록의 배열 상태	블록 이동 횟수	맨해튼 거리 / 제자리 벗어난 타일 수
게임 AI (NavMesh)	폴리곤 또는 웨이포인트	경로 길이	중심점 간 거리

 

즉, “거리”가 아니라 “시간” , “비용” , “리스크” 등... 일 수도 있으므로

• 문제의 특성에 맞게 가중치의 의미를 정의 해야 한다. 

 

 

 

04. 격자 그래프에서의 거리

4-1. 맨해튼 거리 (Manhattan Distance)

• 상, 하, 좌, 우로만 이동할 수 있을 때 사용
• 대각선 이동 불가 (4방향 이동)
• 격자형 도로(예: 뉴욕 맨해튼)에서 유래

예: (2,3) → (5,6)
     → dx = 3, dy = 3
     → h(n) = 6

 

 

4-2. 유클리드 거리 (Euclidean Distance)

피타고라스 정의

• 실제 물리적 직선 거리 (피타고라스 거리)
• 대각선 이동이 가능한 경우(8방향 이동)에 적합

예: (2,3) → (5,6)
     → dx = 3, dy = 3
     → h(n) ≈ 4.24

 

 

4-3. 체비쇼프 거리 (Chebyshev Distance)

• “대각선 이동도 한 칸으로 친다”는 개념
• 가로, 세로 중 더 큰 이동 횟수가 거리

예: (2,3) → (6,5)
     → dx = 4, dy = 2
     → h(n) = 4

 

 

 

 

05. 휴리스틱 함수 설계 원칙 

5-1. 허용적 (Admissible)

( 휴리스틱 함수가 추정한 비용 ≤ 실제 최단 경로(목표까지의 진짜 비용) )

 

• 즉, 실제보다 과대평가하지 않는 낙관적인 추정.
  • 탐색 알고리즘이 “더 짧은 길이 있을 수도 있다”는 가능성을 열어둔다.
• 과대평가하면 잘못된 노드를 먼저 탐색할 수 있어 최단 경로 보장이 깨집니다.
• A* 알고리즘이 최적해(Optimal Solution)를 보장하는 핵심 조건

 

5-2. 일관적 (Consistent)

( 현재 노드의 추정값 ≤ n에서 n'으로 이동하는 실제 비용 + n'에서 목표까지의 추정 비용 )

 

즉, "현재 상태의 휴리스틱 값 ≤ 한 단계 이동 비용 + 다음 상태의 휴리스틱 값" 이어야 한다는 것. 

 

• “목표로 갈수록 비용이 최소한 누적된다”는 일종의 삼각 부등식(triangle inequality)을 만족하는 조건
• 일관적(Consistent) 휴리스틱은 항상 허용적(Admissible) 이다. ( 반대로 허용적이라고 해서 반드시 일관적인 것은 아님. )
• 탐색 중 재방문이 필요 없어 효율적이다. 
  • 오픈리스트(Open list) 관리가 단순해지고
  • 알고리즘의 효율이 높아진다.

 

구분	허용적 (Admissible)	일관적 (Consistent)
정의	추정값 ≤ 실제값	h(n) ≤ c(n, n′) + h(n′)
의미	실제보다 과대평가하지 않음	삼각 부등식 만족
관계	최적해 보장	항상 허용적 + 탐색 효율 증가
예시	잘못 놓인 타일 수	맨해튼 거리
A* 영향	최적해를 보장	최적해 + 불필요한 재방문 없음

 

 

요약 

허용적: “실제보다 낙관적이어야 한다.”
일관적: “삼각 부등식을 만족해야 한다.”
A* 탐색에서는 “일관적”이면 자동으로 “허용적”이 되고, 두 조건을 만족하면 최적해를 효율적으로 찾을 수 있다.

 

 

 

 

06. Open / Closed 관리

리스트	의미
Open 리스트	방문 후보 노드 목록 (우선순위 큐)
Closed 리스트	방문이 확정된 노드 (visited : 이미 탐색 완료)

 

A*는 Open 리스트에서 f(n)이 가장 작은 노드를 꺼내 탐색하고, 해당 노드를 Closed 리스트에 추가한다.
이 과정을 반복하며 목표 노드에 도달하면 탐색을 종료.

 

 

6-1. 의사 코드 (pseudocode) 예시 

open.push({start, 0, h(start)});
g[start] = 0;  // 누적 비용

while (!open.empty()) 
{
    // f=g+h 가 가장 작은 노드
    Node cur = open.top(); open.pop();  

    if (cur == goal) break;

    // 탐색 완료(확정)
    closed.insert(cur);  // 다익스트라의 visited=true 와 동일

    for (auto& neighbor : cur.neighbors) 
    {
        // 1. 이미 확정된 노드(이미 방문한 인접 노드)는 무시 
        if (closed.contains(neighbor))
            continue;      

        // 2. 현재 경로를 통한 g(n) 계산
        float tentative_g = g[cur] + cost(cur, neighbor);

       // 3. 이웃이 아직 open에 없거나, 더 짧은 경로를 찾았을 경우
        if (neighbor not in open || tentative_g < g[neighbor]) 
        {
            g[neighbor] = tentative_g;
            f[neighbor] = g[neighbor] + h(neighbor);
            parent[neighbor] = cur;
            open.push(neighbor);   // 인접 노드를 추가
        }
    }
}

 

 

 

07. 정리

• A = 다익스트라 (Dijkstra) + 휴리스틱 (Heuristic)
• f(n) = g(n) + h(n)
• 휴리스틱 h(n) 은 “문제의 세계관”에 맞게 설계해야 함
• 허용적 (Admissible) → 실제보다 과대평가하지 않음 (최적해 보장)
• 일관적 (Consistent) → 삼각 부등식 만족 (효율적 탐색)
• 좋은 휴리스틱은 빠르고 정확한 탐색의 핵심이다.