휴리스틱 (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% 품질의 해.

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

시각화

핵심 아이디어

방법론 비교

flowchart TD
    Problem["최적화 문제"] --> Check{"NP-hard?"}
    Check -->|No| Exact["정확 알고리즘: 최적해 보장"]
    Check -->|Yes| Scale{"입력 규모?"}
    Scale -->|소규모| Brute["완전 탐색 / DP"]
    Scale -->|중규모| Approx["근사 알고리즘: 비율 보장"]
    Scale -->|대규모| Heur["휴리스틱: 빠른 실용해"]
    Heur --> LS["Local Search: 이웃 개선 반복"]
    Heur --> Meta["Metaheuristic: SA / GA 등"]
    Approx --> VC["Vertex Cover 2-근사"]
    Approx --> TSP["TSP Christofides 1.5-근사"]

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

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

• Vertex Cover: 2-approximation (인접 간선 양 끝점 선택)
• TSP (metric): 1.5-approximation (Christofides algorithm)
• Max-Cut: 2-approximation (Local Search 기반)

2. Local Search

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

Local Search 일반 흐름:

1. 임의 초기 해 x0 생성
2. repeat:
   a. x0 의 이웃 N(x0) 탐색
   b. f(x') < f(x0) 인 x' in N(x0) 있으면 x0 = x'
3. until 더 이상 개선 없음
4. return x0  (local optimum)

이웃 정의 예시:

• TSP 2-OPT: 두 간선을 제거하고 다시 연결하는 모든 경우
• Max-Cut: 정점 하나를 반대편 집합으로 이동
• Job Scheduling: 두 작업의 순서를 교환

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

복잡도

변형 / 활용

Metaheuristic: 지역 최적 탈출

Local Search 는 지역 최적에 갇힘. Metaheuristic 은 확률적으로 더 나쁜 해를 수용하여 탈출:

• Simulated Annealing: 온도(T) 에 따라 더 나쁜 해를 exp(-dE/T) 확률로 수용. T 를 서서히 낮춤.
• Genetic Algorithm: 여러 해를 “교배” + “돌연변이” 로 발전시킴.
• Tabu Search: 최근 방문한 이웃을 금지(tabu) 리스트에 올려 순환 방지.

이 기법들은 이론적 근사 비율 보장이 없지만, 실전에서 우수한 성능을 보임.

방법론 선택 가이드

함정

1. Local Optimum

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

2. Greedy 의 오판

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

3. 근사 비율 오해

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

4. Local Search 수렴 시간

최악의 경우 Local Search 가 다항 시간에 수렴하지 않을 수 있음. 실전에서는 iteration 횟수나 시간 제한으로 강제 종료.

BOJ 연습 문제

참고

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