A*알고리즘

A*알고리즘이란?

휴리스틱 알고리즘은 복잡한 문제를 빠르게 해결하기 위한 근사적 방법 중 하나로, 특히 경로 탐색 분야에서 자주 사용됩니다. 대표적인 알고리즘이 바로 A* (A-Star) 알고리즘입니다.

 

gCost	Given Cost	시작점부터 현재까지 실제 비용
hCost	Heuristic Cost	현재부터 목적지까지 예상 비용
fCost	Final Cost / Total Cost	총 예상 비용 (g + h)

 

---

1. A* 알고리즘이란?

A* 알고리즘은 경로를 탐색할 때 단순히 가까운 곳부터 탐색하는 것이 아니라,
현재 위치에서 목적지까지 얼마나 효율적으로 갈 수 있을지를 예측하며 움직이는 알고리즘입니다.
이 과정에서 사용하는 추정값이 바로 휴리스틱(Heuristic) 입니다.

---

2. 핵심 용어 정리

• gCost: 출발지에서 현재 노드까지 실제 이동한 거리 (누적 비용)
• hCost: 현재 노드에서 목적지까지의 예상 거리 (휴리스틱 값)
• fCost = gCost + hCost: 해당 노드를 통해 목적지까지 도달할 때의 예상 총 비용

fCost가 낮을수록 우선적으로 탐색

---

3. 탐색 과정 요약

1. openList에 출발 노드를 추가한다.
   • openList: 아직 탐색하지 않은 후보 노드들.
2. openList에서 가장 fCost가 낮은 노드를 꺼낸다.
3. 꺼낸 노드를 closedList에 넣는다.
   • closedList: 이미 탐색이 완료된 노드들.
4. 현재 노드의 **이웃 노드들(갈 수 있는 방향)**을 확인한다.
5. 이웃 노드가 closedList에 있다면 무시한다.
6. 그렇지 않다면, 해당 이웃 노드의 gCost를 계산한다.
7. 이미 openList에 있는데,
   • 기존 gCost가 더 크거나 같다면 👉 현재 경로는 비효율적이므로 무시한다.
   • 새로운 gCost가 더 작다면 👉 더 좋은 경로이므로 다음을 수행:
   • 이웃 노드의 gCost, hCost, fCost를 업데이트하고,
   • **어느 노드에서 왔는지(parent)**를 현재 노드로 설정한다.
8. 이웃 노드가 openList에 없다면 새로 추가한다.
9. 이 과정을 반복하여 목적지 노드에 도착하면, parent 노드를 따라 역추적하여 최단 경로를 완성한다.

---

4. 핵심 개념 그림으로 정리 (텍스트 버전)

 

[출발지] → A → B → C → [목적지] 각 노드는 gCost, hCost를 가지고 있고, fcost = gCost + hCost 로 계산된다.

ex) A의 fCost = 3(g) + 5(h) = 8 B의 fCost = 2(g) + 3(h) = 5 → 우선 탐색 대상

---

5. 이해가 어려운 부분 풀이

"openList에 있는 노드들을 fCost가 낮은 순으로 탐색하고,
이웃 노드들의 gCost를 새로 계산해서
기존 값보다 크면 무시하고, 작으면 parent를 설정한다."

• 어떤 노드(A)를 꺼냈을 때, 주변 노드들(B, C 등)을 검사
• 그 노드들로 가는 **새로운 경로(gCost)**를 계산해봅니다.
• 그 경로가 예전보다 비효율적이면 무시하고,
• 더 짧다면 “이게 더 좋은 길이네?” 하고 경로를 업데이트합니다.
  • gCost를 바꾸고,
  • 어디서 왔는지 (parent = A)로 기록합니다.
• 이렇게 하면 나중에 목적지에 도달했을 때, parent를 따라가며 경로를 복원

 

금일은 이해까지만 하고 예제는 다음에 진행하기로 하자.