[알고리즘] A* (A-Star) 알고리즘과 Greedy (탐욕) 알고리즘

A* (A-Star) 알고리즘 (vs. 다익스트라)

• A* 알고리즘은 다익스트라(Dijkstra) 알고리즘을 기반으로 하지만, **휴리스틱(heuristic, 추정치)**을 사용하여 훨씬 효율적으로 최단 경로를 탐색하는 알고리즘
• 두 알고리즘 모두 우선순위 큐(Priority Queue)를 사용하여 다음으로 탐색할 노드를 결정한다는 공통점이 있지만, 우선순위를 결정하는 방식에서 결정적인 차이가 있음

---

1. 다익스트라 알고리즘 (Dijkstra's Algorithm)

 

• 우선순위: Priority = g(n)
• g(n): 시작 노드(s)에서 현재 노드(n)까지의 실제 비용(cost)

- 다익스트라 알고리즘은 오직 "지금까지 온 비용" 만을 고려하여 경로를 탐색

- 이 때문에 목표 지점의 방향과 상관없이, 마치 원이 퍼져나가듯 모든 방향으로 균일하게 탐색을 진행

 

2. A* 알고리즘 (A* Algorithm)

• 우선순위: Priority = g(n) + h(n)
• g(n): 다익스트라와 동일 (시작 노드에서 현재 노드까지의 실제 비용)
• h(n): 현재 노드(n)에서 목표 노드(t)까지의 추정 비용 (Heuristic)

- A*는 "지금까지 온 비용"(g(n))에 더해 "앞으로 갈 비용"(h(n))을 추정하여 더한 값을 우선순위로 사용

- 이 휴리스틱(추정치) 덕분에 A*는 목표 지점을 향해 "방향성"을 가지고 탐색을 진행하며, 다익스트라처럼 엉뚱한 방향으로 탐색하는 것을 방지

 

3. A*의 핵심: 허용 가능한 휴리스틱 (Admissible Heuristic)

• A*가 다익스트라처럼 최단 경로를 보장하기 위해서는 휴리스틱 함수 h(n)이 허용 가능(admissible)해야 함
• 허용 가능 (Admissible): 추정 비용(h(n))이 절대 실제 비용보다 크지 않아야 함
• 즉, 항상 실제 비용보다 같거나 적게(underestimate) 추정해야 함
• 예를 들어, 지도에서 맨해튼 거리(Manhattan distance, 가로 블록 + 세로 블록)는 실제 도로 거리보다 항상 짧거나 같으므로 허용 가능한 휴리스틱

---

💡 Greedy (탐욕) 알고리즘

- 탐욕 알고리즘은 매 순간(local) 가장 좋아 보이는 선택을 반복함으로써, 전체적으로도 최적의 해(global optimum)를 찾으려는 접근 방식

- 이 방식은 모든 문제에서 최적해를 보장하지는 않지만, 특정 문제들에서는 동적 계획법보다 훨씬 빠르고 간단하게 최적해를 제공

 

1. 활동 선택 문제 (Activity-Selection Problem)

• 문제: 하나의 회의실을 사용하려는 여러 활동(시작 시간, 종료 시간) 중, 서로 겹치지 않게 최대한 많은 수의 활동을 선택하는 문제
• 탐욕적 선택: 활동들을 '종료 시간'이 빠른 순으로 정렬
• 알고리즘:
  1. 가장 빨리 끝나는 첫 번째 활동(a1)을 무조건 선택
  2. 선택한 활동과 겹치지 않는(즉, 시작 시간이 '선택된 활동의 종료 시간' 이후인) 활동 중에서 가장 빨리 끝나는 다음 활동(a4)을 선택
  3. 이 과정을 계속 반복 (a8, a11...)
• 정당성: 가장 빨리 끝나는 활동을 선택하는 것이 항상 최적해의 일부가 됨이 증명(Theorem 15.1).

2. 배낭 문제 (Knapsack Problem)

• 문제: 무게 제한이 있는 배낭에 여러 물건(무게, 가치)을 담아 가치의 총합을 최대로 만드는 문제
• Fractional Knapsack (부분 배낭 문제): 물건을 쪼갤 수 있음
• 탐욕적 선택: **무게 대비 가치(가치/무게)**가 가장 높은 물건을 우선적으로 선택합니다. (c) 그림에서 이 전략으로 최적해($240)를 찾음
• (참고) 0-1 Knapsack: 물건을 쪼갤 수 없습니다. 이 문제에 탐욕 알고리즘을 사용하면 최적해를 보장할 수 없음

3. 허프만 코드 (Huffman Codes)

• 문제: 데이터 압축을 위해, 각 문자의 빈도수에 따라 최적의(가장 짧은) 접두어 없는 코드를 생성하는 것
• 탐욕적 선택: '빈도수가 가장 낮은' 두 개의 문자를 찾아 하나의 노드로 합치는(merge) 과정을 반복
• 알고리즘 (Bottom-up):
  
  1. 모든 문자를 우선순위 큐(Min-Heap)에 넣음. (빈도수가 우선순위)
  2. 큐에서 **빈도수가 가장 낮은 두 노드(x, y)**를 꺼냄(EXTRACT-MIN).
  3. 두 노드를 자식으로 하는 새 부모 노드(z)를 만들고, 이 부모 노드의 빈도수를 x.freq + y.freq로 설정
  4. 이 새 부모 노드(z)를 다시 큐에 넣습니다(INSERT).
  5. 큐에 노드가 하나(최종 Root)만 남을 때까지 반복

이 과정을 통해 빈도수가 높은 문자는 트리의 루트에 가까워져 짧은 코드를, 빈도수가 낮은 문자는 트리의 깊은 곳에 위치하여 긴 코드를 갖게 됨