12.2 완전 경로 - 해밀턴 경로

해밀턴 경로

해밀턴 경로(Hamiltonian path) 는 그래프의 모든 노드를 정확히 한 번씩만 방문하는 경로이다. 이 경로의 시작 노드와 마지막 노드가 같은 경우는 해밀턴 회로(Hamiltonian circuit) 라고 부른다. 예를 들어 그림 13에 해밀턴 경로와 해밀턴 회로가 모두 있는 그래프가 나와 있다.

• 그림 13. 그래프, 해밀턴 경로, 해밀턴 회로
  • 

해밀턴 경로와 관련된 문제는 NP-하드이다. 그래프에 해밀턴 경로나 해밀턴 회로가 있는지를 효율적으로 찾는 일반적인 방법은 알려지지 않았다. 물론 몇몇 특별한 경우에는 그래프에 항상 해밀턴 경로가 있음을 보장할 수 있다. 예를 들어 완전 그래프, 즉 모든 노드 간에 간선이 있는 그래프에는 당연히 해밀턴 경로가 존재한다.

해밀턴 경로를 찾는 간단한 방법은 퇴각 검색 알고리즘을 이용하여 경로를 구성하는 모든 가능한 경우를 탐색하는 것이다. 이때 노드 $n$개를 방문하는 순서가 $n!$가지 존재하므로, 알고리즘의 시간 복잡도는 최소 $O(n!)$이 된다.

동적 계획법을 이용하면 좀 더 효율적인 $O(2^n{n}^2)$ 시간에 해를 찾을 수 있다(Held–Karp algorithm - Wikipedia). 노드의 모든 부분집합 $S$와 $x\in S$인 모든 노드 $x$에 대해, $S$의 모든 노드를 정확히 한 번씩만 방문하고 노드 $x$에서 끝나는 경로가 있는지를 확인해 보는 것이다.

연습문제

• 해밀턴 순환회로 - JUNGOL

• 해밀턴 순환회로2 - JUNGOL | TSP

• 시간 복잡도

  • $O(N^2\times 2^N)$
  • $N$ 16 ~ 18 일때 가능
    • 현재 도시 cur의 경우의 수: $N$
    • 방문 상태 mask의 경우의 수: $2^N$
    • 다음 도시 next 탐색: $N$

• dp[mask][u]

  • 그 상태에 도달하는 여러 경우 중, u 가 마지막 도시인 경우의 최소 값
  • dp[01101][2]
    • 다음 경우들을 포함한 상태
    • 0 → 3 → 2
    • 3 → 0 → 2

연습 코드

cpp

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO \
ios::sync_with_stdio(false); \
cin.tie(nullptr);
 
int main() {
    FAST_IO;
 
    int n;
    cin >> n;
 
    vector<vector<int>> w(n, vector<int>(n));
 
    // TODO 1. 비용 행렬 입력받기
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> __________;
        }
    }
 
    const int INF = 1e9;
 
    // full은 전체 방문 상태의 개수
    // n개의 도시가 있으면 가능한 방문 상태는 2^n개
    int full = __________;
 
    // dp[mask][u]
    // mask 상태로 도시들을 방문했고, 현재 u번 도시에 있을 때의 최소 비용
    vector<vector<int>> dp(full, vector<int>(n, INF));
 
    // 출발 도시는 0번 도시
    // 0번 도시만 방문한 상태는 mask = 1
    dp[__________][__________] = 0;
 
    // TODO 2. 모든 방문 상태를 순회한다
    for (int mask = 1; mask < full; ++mask) {
 
        // TODO 3. 현재 마지막 도시 u를 순회한다
        for (int u = 0; u < n; ++u) {
 
            // 아직 도달할 수 없는 상태라면 건너뛴다
            if (dp[mask][u] == __________) {
                continue;
            }
 
            // TODO 4. 다음에 방문할 도시 v를 고른다
            for (int v = 0; v < n; ++v) {
 
                // 이미 방문한 도시이거나, u -> v 길이 없으면 건너뛴다
                if ((mask & (__________)) || w[u][v] == 0) {
                    continue;
                }
 
                // TODO 5. v를 방문한 새로운 상태를 만든다
                int nxt = mask | __________;
 
                // TODO 6. dp 갱신
                dp[nxt][v] = min(
                    dp[nxt][v],
                    ________________________________
                );
            }
        }
    }
 
    int ans = INF;
 
    // 모든 도시를 방문한 상태
    int all_visited = full - 1;
 
    // TODO 7. 마지막 도시 u에서 다시 0번 도시로 돌아오는 비용을 더한다
    for (int u = 1; u < n; ++u) {
        if (w[u][0] != 0) {
            ans = min(
                ans,
                ________________________________
            );
        }
    }
 
    cout << ans << '\n';
 
    return 0;
}

python

import sys
input = sys.stdin.readline
 
n = int(input())
 
w = [[0] * n for _ in range(n)]
 
# TODO 1. 비용 행렬 입력받기
for i in range(n):
    row = list(map(int, input().split()))
    for j in range(n):
        w[i][j] = __________
 
INF = 10 ** 9
 
# full은 전체 방문 상태의 개수
# n개의 도시가 있으면 가능한 방문 상태는 2^n개
full = __________
 
# dp[mask][u]
# mask 상태로 도시들을 방문했고, 현재 u번 도시에 있을 때의 최소 비용
dp = [[INF] * n for _ in range(full)]
 
# 출발 도시는 0번 도시
# 0번 도시만 방문한 상태는 mask = 1
dp[__________][__________] = 0
 
# TODO 2. 모든 방문 상태를 순회한다
for mask in range(1, full):
 
    # TODO 3. 현재 마지막 도시 u를 순회한다
    for u in range(n):
 
        # 아직 도달할 수 없는 상태라면 건너뛴다
        if dp[mask][u] == __________:
            continue
 
        # TODO 4. 다음에 방문할 도시 v를 고른다
        for v in range(n):
 
            # 이미 방문한 도시이거나, u -> v 길이 없으면 건너뛴다
            if (mask & (__________)) or w[u][v] == 0:
                continue
 
            # TODO 5. v를 방문한 새로운 상태를 만든다
            nxt = mask | __________
 
            # TODO 6. dp 갱신
            dp[nxt][v] = min(
                dp[nxt][v],
                ________________________________
            )
 
ans = INF
 
# 모든 도시를 방문한 상태
all_visited = full - 1
 
# TODO 7. 마지막 도시 u에서 다시 0번 도시로 돌아오는 비용을 더한다
for u in range(1, n):
    if w[u][0] != 0:
        ans = min(
            ans,
            ________________________________
        )
 
print(ans)