휴리스틱 (Heuristics)

정의

휴리스틱 (Heuristics) 은 NP-hard 문제나 지나치게 큰 탐색 공간에서 최적해 대신 실용적으로 충분히 좋은 해를 빠르게 찾는 방법의 총칭. 크게 근사 알고리즘 (Approximation Algorithm, 최적해와의 비율 보장), Local Search (국소적 개선 반복), Greedy Heuristic (탐욕적 선택) 으로 나눈다.

문제 상황과 동기

P != NP 가정 하에 최적해를 다항 시간에 구할 수 없는 문제 (TSP, Knapsack, Vertex Cover, Max Clique 등) 가 존재. 현실에서는 “최적에 가까운” 해로도 충분한 경우가 많음.

• naive (exact): 지수 시간 (2^N). N=50 이상에서 불가능.
• heuristics: O(N log N) ~ O(N^2) 로 최적 대비 90~99% 품질의 해.

핵심 통찰: 최적을 포기하는 대신, 실용적 시간 내에 “충분히 좋은” 해를 얻는다.

시각화

핵심 아이디어

1. 근사 알고리즘 (Approximation Algorithm)

최적해 OPT 에 대해 항상 C <= alpha * OPT (minimization) 를 보장. alpha 를 근사 비율 (Approximation Ratio) 이라 함.

2. Local Search

현재 해의 “이웃 (neighborhood)” 을 정의하고, 더 나은 이웃이 없을 때까지 이동. 지역 최적 (local optimum) 에 빠질 위험.

3. Greedy Heuristic

매 선택에서 당장 가장 좋아 보이는 선택. matroid 구조에서는 최적 보장, 일반적으로는 보장 없음.

알고리즘

# Local Search (Max-Cut 예시)
1. 임의 분할 (S, V\S) 로 초기화
2. repeat:
3.   모든 정점 v 에 대해:
4.     v 를 반대편으로 옮기면 cut 증가? -> 이동
5. until 더 이상 개선 없음
6. return S

# Greedy (Vertex Cover 예시)
1. C = empty
2. while 남은 간선 있음:
3.   임의 간선 (u,v) 선택, C 에 u,v 추가
4.   u,v 에 부속된 모든 간선 제거
5. return C

구현

// Greedy Vertex Cover (2-approximation)
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m; cin >> n >> m;
  vector<pair<int,int>> edges(m);
  for (int i = 0; i < m; i++) {
      int u, v; cin >> u >> v;
      edges[i] = {u, v};
  }
  vector<bool> covered(m, false);
  vector<int> cover;
  for (int i = 0; i < m; i++) {
      auto [u, v] = edges[i];
      if (covered[i]) continue;
      cover.push_back(u);
      cover.push_back(v);
      for (int j = i; j < m; j++) {
          auto [a, b] = edges[j];
          if (a == u || a == v || b == u || b == v)
              covered[j] = true;
      }
  }
  cout << "Cover size: " << cover.size() << "\n";
  for (int v : cover) cout << v << " ";
  cout << "\n";
}

# Greedy Vertex Cover (2-approximation)
def vertex_cover(n, edges):
  covered = [False] * len(edges)
  cover = []
  for i, (u, v) in enumerate(edges):
      if covered[i]:
          continue
      cover.extend([u, v])
      for j in range(i, len(edges)):
          a, b = edges[j]
          if a in (u, v) or b in (u, v):
              covered[j] = True
  return cover
​
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
cover = vertex_cover(n, edges)
print(f"Cover size: {len(cover)}")
print(*cover)

4 4
0 1
1 2
2 3
3 0

Cover size: 4
0 1 2 3

복잡도

변형 / 활용

함정

1. Local Optimum

Local Search 가 전역 최적 대신 지역 최적에 갇힘. restart / perturbation 으로 완화.

2. Greedy 의 오판

당장의 이득이 장기적으로 손해. 예: 0-1 Knapsack 에서 Greedy 는 최적 보장 없음.

3. 근사 비율 오해

근사 알고리즘은 guaranteed ratio 를 가짐. Heuristic 은 보통 ratio guarantee 가 없음. 구분 필요.

BOJ 연습 문제

참고

• 담금질 기법
• 경사 하강법
• 탐욕법