TSP 문제 (외판원 순회 문제)

이번 글에서는 TSP 문제를 다뤄보려합니다.

생명과학 과제로 '블롭'이라 불리는 '황색망사점균'에 대해서 조사했었는데  이 생명체가 굉장히 흥미로웠습니다. 현재 5계 분류군 어디에도 속하지 않으며 특정 기관 등이 없음에도 불구하고 학습하고, 소화하며, 이동합니다. 가장 신기했던 것은 미최단경로를 찾아 먹이를 향해 이동하는 능력을 갖고 있다는 것이었습니다. 미로탐색과 TSP를 풀도록 한 실험이 있었는데 정확하게 그 문제를 풀어내었다고 합니다. 이후 TSP에 대해서 찾아보았고 이를 동적계획법으로 풀어보려고 합니다.

 

컴퓨터 공학에서 가장 오래되고 유명한 문제인 TSP(외판원 순회 문제)는 다른 도시들과 도로로 연결되어있는 도시를 한 번씩만 방문하고 출발한 도시로 돌아오는 가장 최소 비용의 경로를 찾는 문제입니다.

동적계획법은 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 사용하여 효율적으로 값을 구하는 알고리즘 설계 기법입니다. 간단히 말하면 이전에 구했던 답을 사용하는 것입니다.

---

백준 2098번 문제인 외판원 순회를 풀어보겠습니다.

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.
항상 순회할 수 있는 경우만 입력으로 주어진다.

출력
첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

 

1. 문제 분석

이 문제는 현재의 노드에서 가는 가중치 뿐만 아니라 이후 경로의 가중치까지 고려해야 합니다.

동적계획법으로  알고리즘를 찾아보았는데 비트마스크를 사용해 경로를 구한다는 것을 알게 되었습니다.

우선 코드를 짜기 전에 비트마스크에 대해 알아보고 오겠습니다.

---

- 비트마스크

비트(bit)는 이진숫자를 뜻하며, 0과 1로 True/false, on/off 를 나타낼 수 있고 컴퓨터에서 데이터의 가장 작은 단위입니다.

비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말합니다.

 

노드가 1, 2, 3, 4 가 있다고 가정하고 예를 들어보겠습니다.

1, 2, 3, 4 를 모두 지나면 1111

1, 3을 지나면 0101

1을 지나면 0001

이 되는 것입니다.

 

비트 연산을 알아보겠습니다.

shift는 비트를 미는 것이라고 생각하면되는 '<<' 는 오른쪽에서 왼쪽으로 '>>'는 왼쪽에서 오른쪽으로 미는 것입니다. 그 빈자리는 0 으로 채우게 됩니다.

a = 0101로 예를 들자면

a << 1 : 1010

a << 2 : 0100

a >> 1 : 0010

a >> 2 : 0001

이 됩니다.

 

n이 0 이상의 정수일 때, ’(1 << n)은 n번째 비트를 켠다’는 의미를 갖고 있습니다. 

0001을 왼쪽으로 n번 옮기는 것이 되는 것이죠.

'(1 << n) - 1은 n개의 비트를 모두 켠다'는 의미를 갖고 있습니다.

0001이 왼쪽으로 n번 옮겨진 후 -1을 하면 0이 1, 1이 0이 될것입니다.

확인해볼까요

3을 입력하니 첫번째 출력에서는 오른쪽부터 0번째이고 3번째 값이 1이 되었습니다.

두번째 출력에서는 3개의 비트가 1이 되었습니다.

 

AND 연산은 &, OR 연산은 |, XOR 연산은 ^, NOT연산은 ~ 기호를 사용합니다.

AND: 모두 1일 때 1, 아니면 0

OR: 모두 0일 때 0, 아니면 1

XOR: 다르면 1, 같으면 0

NOT: 0이면 1, 1이면 0

---

2. 순서도

순서도를 그려보고 코드를 짜보겠습니다.

3. 코드

n = int(input()) #노드 수
city = [list(map(int, input().split())) for i in range(n)] #비용
visit = [[-1 for i in range(1 << n)] for j in range(n)] #비트마스크

#TSP 알고리즘
def tsp(cur, visited): # (현재 노드, 방문한 노드)
    if visited == (1<<n)-1 : #모든 노드를 방문했을 때(bit n개가 모두 1일때)
        if city[cur][0] != 0: #0으로 가는 길이 있을 때
            return city[cur][0] # 현재 노드에서 0으로 가는 비용 반환
        else: #아니면
            return float('inf') # 무한대 반환

    if visit[cur][visited] != -1: # 현재 노드에서 visit노드를 방문하는 길이 있을 때
        return visit[cur][visited] # cur -> visited 비용 반환

    cnt = float('inf')
    for i in range(n):
        if visited & (1 << i) != 0: # 노드를 방문했다면
            continue
        if city[cur][i] == 0: # 경로가 없으면
            continue
        cnt = min(cnt, tsp(i, visited | (1 << i)) + city[cur][i]) # 기존 비용과 (i번째 노드, (i번째 노드에서 방문하지 않은 노드 + 비용))을 전달했을시 더 작은 값
    visit[cur][visited] = cnt # 비트마스크에 비용 넣기
    return cnt


print(tsp(0, 1)) # 시작노드는 0, 방문함으로 표시

예 당연히 처음부터 되진 않았구요..

inf를 처음쓰다보니 안 익숙했습니다. 그냥 inf 써놓고 왜 안되지 보고 있었는데 float()을 씌워주어야 했습니다.

비트연산자 부분에서도 헷갈렸던거 같고 조건을 정하는 부분도 그랬던 것 같습니다.

다른 때보다 이해하고 작성하는데 오래걸렸어요.

코드를 짠 후에 주석으로 코드 설명을 추가해보았습니다.

사실 헷갈려서 꼭 넣어야 했던거 같아요..ㅎㅎ....

 

---

비트연산자를 잘 사용하지 않다보니 코드를 짜면서 어색했고 어려웠습니다. 그래서 다른 코드를 참고해서 이해한 후 코드를 짜게 되었습니다. 파이썬으로는 비트연산자와 inf를 처음 써보는 것 같은데 알고리즘 문제들을 풀면서 코드를 짜는 방법을 다양하게 배우고 있는 거 같습니다.

 

참고:

https://hongcoding.tistory.com/83 https://ji-gwang.tistory.com/448 https://campkim.tistory.com/21