헬드-카프 알고리즘 편집하기

'''헬드-카프 알고리즘'''(Held-Karp Algorithm)은 동적 계획법(Dynamic Programming, DP)을 활용하여 '''여행하는 외판원 문제(TSP, Traveling Salesman Problem)'''를 해결하는 최적화 기법이다. 일반적으로 TSP 문제는 지수적 시간 복잡도를 가지지만, 헬드-카프 알고리즘을 사용하면 '''O(2ⁿ * n²)'''의 시간 복잡도로 해결할 수 있다.
==개요==
*TSP 문제는 주어진 도시들을 한 번씩 방문하고 다시 출발점으로 돌아오는 최소 비용의 경로를 찾는 문제이다.
*헬드-카프 알고리즘은 '''비트마스크 DP(Bitmask DP)''' 기법을 활용하여 중복되는 하위 문제를 저장하고 최적해를 찾는다.
*기존의 완전 탐색(Brute Force)은 '''O(n!)'''이지만, 헬드-카프 알고리즘을 적용하면 '''O(2ⁿ * n²)'''로 줄일 수 있다.
==동작 원리==
헬드-카프 알고리즘은 다음과 같이 동작한다.
*'''비트마스크를 사용하여 방문 상태를 저장'''
**예를 들어, 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를 제외한 방문 도시)
==예제==
주어진 도시가 4개(A, B, C, D)이고, 비용 행렬이 다음과 같다고 가정하자.
{| class="wikitable"
|-
! !!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를 사용하면 다음과 같이 계산된다.
#초기 상태: 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
#최종 경로 비용 계산:
#*dp[1111][A] = dp[1111][D] + cost[D][A] = 75 + 20 = 95
최소 비용은 '''95'''이다.
==코드 예제==
<syntaxhighlight lang="python">
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
</syntaxhighlight>
 출력 결과 예시:
 95
==시간 복잡도==
*헬드-카프 알고리즘을 적용한 TSP의 시간 복잡도는 '''O(2ⁿ * n²)'''이다.
*기존의 완전 탐색 '''O(n!)'''과 비교하면 훨씬 효율적이다.
==응용==
헬드-카프 알고리즘은 다음과 같은 문제 해결에 활용될 수 있다.
*'''경로 최적화'''
**물류 및 배달 경로 최적화.
*'''로봇 경로 계획'''
**로봇이 여러 지점을 방문할 때 최적 경로 찾기.
*'''네트워크 라우팅'''
**데이터 패킷의 최적 전송 경로 탐색.
==같이 보기==
*[[여행하는 외판원 문제]]
*[[비트마스크 DP]]
*[[다이나믹 프로그래밍]]
*[[NP-완전 문제]]
==참고 문헌==
*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.
[[분류:알고리즘]]