헬드-카프 알고리즘

헬드-카프 알고리즘(Held-Karp Algorithm)은 동적 계획법(Dynamic Programming, DP)을 활용하여 여행하는 외판원 문제(TSP, Traveling Salesman Problem)를 해결하는 최적화 기법이다. 일반적으로 TSP 문제는 지수적 시간 복잡도를 가지지만, 헬드-카프 알고리즘을 사용하면 O(2ⁿ * n²)의 시간 복잡도로 해결할 수 있다.

1 개요

• TSP 문제는 주어진 도시들을 한 번씩 방문하고 다시 출발점으로 돌아오는 최소 비용의 경로를 찾는 문제이다.
• 헬드-카프 알고리즘은 비트마스크 DP(Bitmask DP) 기법을 활용하여 중복되는 하위 문제를 저장하고 최적해를 찾는다.
• 기존의 완전 탐색(Brute Force)은 O(n!)이지만, 헬드-카프 알고리즘을 적용하면 O(2ⁿ * n²)로 줄일 수 있다.

2 동작 원리

헬드-카프 알고리즘은 다음과 같이 동작한다.

• 비트마스크를 사용하여 방문 상태를 저장
  • 예를 들어, n = 4일 때 0101 (2진수)는 1번과 3번 도시를 방문했음을 의미.
• DP 테이블을 이용하여 최소 비용을 저장
  • dp[mask][i]: 현재 방문한 도시들이 mask일 때, 마지막으로 방문한 도시가 i일 때의 최소 비용.
• 점화식 정의
  • dp[mask][i] = min(dp[mask ^ (1 << i)][j] + cost[j][i]) (단, j는 i를 제외한 방문 도시)

3 예제

주어진 도시가 4개(A, B, C, D)이고, 비용 행렬이 다음과 같다고 가정하자.

	A	B	C	D
A	0	10	15	20
B	10	0	35	25
C	15	35	0	30
D	20	25	30	0

비트마스크 DP를 사용하면 다음과 같이 계산된다.

1. 초기 상태: dp[0001][A] = 0 (A에서 시작)
   • 첫 번째 이동: dp[0011][B] = dp[0001][A] + cost[A][B] = 10
   • 두 번째 이동: dp[0111][C] = dp[0011][B] + cost[B][C] = 10 + 35 = 45
   • 세 번째 이동: dp[1111][D] = dp[0111][C] + cost[C][D] = 45 + 30 = 75
2. 최종 경로 비용 계산:
   • dp[1111][A] = dp[1111][D] + cost[D][A] = 75 + 20 = 95

최소 비용은 95이다.

4 코드 예제

import sys

def tsp(mask, pos, dp, dist, n):
    if mask == (1 << n) - 1:
        return dist[pos][0]  # 모든 도시 방문 후 출발점으로 돌아가기

    if dp[mask][pos] != -1:
        return dp[mask][pos]

    min_cost = sys.maxsize
    for next_pos in range(n):
        if (mask & (1 << next_pos)) == 0:  # 방문하지 않은 도시라면
            new_cost = dist[pos][next_pos] + tsp(mask | (1 << next_pos), next_pos, dp, dist, n)
            min_cost = min(min_cost, new_cost)

    dp[mask][pos] = min_cost
    return min_cost

# 예제 실행
n = 4
dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

dp = [[-1] * n for _ in range(1 << n)]
print(tsp(1, 0, dp, dist, n))  # 출력: 95

출력 결과 예시:
95

5 시간 복잡도

• 헬드-카프 알고리즘을 적용한 TSP의 시간 복잡도는 O(2ⁿ * n²)이다.
• 기존의 완전 탐색 O(n!)과 비교하면 훨씬 효율적이다.

6 응용

헬드-카프 알고리즘은 다음과 같은 문제 해결에 활용될 수 있다.

• 경로 최적화
  • 물류 및 배달 경로 최적화.
• 로봇 경로 계획
  • 로봇이 여러 지점을 방문할 때 최적 경로 찾기.
• 네트워크 라우팅
  • 데이터 패킷의 최적 전송 경로 탐색.

7 같이 보기

• 여행하는 외판원 문제
• 비트마스크 DP
• 다이나믹 프로그래밍
• NP-완전 문제

8 참고 문헌

• Held, M., and Karp, R. M. "A dynamic programming approach to sequencing problems." Journal of the Society for Industrial and Applied Mathematics, 1962.
• Papadimitriou, Christos H., and Kenneth Steiglitz. "Combinatorial Optimization: Algorithms and Complexity." Dover Publications, 1998.