알고리즘 - TSP 문제

import math


n = 5
dist = [
    [0, 2, 5, 3, 7],
    [2, 0, 10, 6, 6],
    [5, 10, 0, 4, 8],
    [3, 6, 4, 0, 12],
    [7, 6, 8, 12, 0]
]

### Brtue Force Search (완전탐색)
path = []
visited = [False for _ in range(n)]

# shortest_path1(path, visited, d) -> length
# 이미 거쳐 온 경로 path, 방문한 도시를 나타내는 visited, 지금까지의 길이 d가 주어질 때 최단 경로의 길이
def shortest_path1(path, visited, d):
    # base case
    # all(visited) == True
    # sumation of edges

    # 모든 도시를 방문했다면, 지금까지 왔던 거리에 마지막 방문한 도시에서 처음 출발한 도시로 가는 거리를 더하여 반환한다.
    if all(visited):
        return d+dist[path[-1]][path[0]]

    # 마지막 방문하여 현재 자신이 위치해있는 도시를 cur 변수가 참조하게 한다. 
    cur = path[-1]

    # 충분히 큰 숫자를 ret 변수가 참조하게 한다.
    # 아래 for문 안에서 path.pop(), visited[_next]=False에 의해 도시 간 이동하는 모든 경우에서의 ret 값의 최소를 찾게 된다.
    ret = math.inf
    for _next in range(n):
        if not visited[_next]:
            path.append(_next)
            visited[_next] = True
            ret = min(ret, shortest_path1(path, visited, d+dist[cur][_next]))
            path.pop()
            visited[_next] = False

    return ret


path.append(0)
visited[0] = True

if __name__ == "__main__":
    print(shortest_path1(path, visited, 0))

import math


n = 5
dist = [
    [0, 2, 5, 3, 7],
    [2, 0, 10, 6, 6],
    [5, 10, 0, 4, 8],
    [3, 6, 4, 0, 12],
    [7, 6, 8, 12, 0]
]

### Dynamic Programming
# DP에 cache를 사용하기 위해서는 `bit operation` 필요 
# path, visited가 배열 형태이므로 cache[path[-1]][visited]가 사용될 수 없다.
# ex. visited = [T, F, T, F] --> 0101(2) (2^0 : T(1), 2^1 : F(0), 2^2 : T(1), 2^3 : F(0))--> 5
# ex. 3번 도시를 방문한 경우, 0101(2) + (1<<3) --> 1101(2) --> [T, F, T, T]

cache = [[None for _ in range(1<<n)] for _ in range(n)]
# 여기서 나올 수 없는 최대한의 큰 값으로 설정
INF = 99999

# 0부터 시작한다고 가정
# shortest_path2(cur, visited) -> length
# 현재 위치 cur 방문한 도시들 visited일 때 남은 도시를 방문하는 최소 경로의 길이
def shortest_path2(cur, visited):
    # base case
    # 모두 방문했다면 처음과 끝의 경로의 길이
    if visited == (1<<n)-1:
        return dist[cur][0]

    if cache[cur][visited] != None:
        return cache[cur][visited]

    cache[cur][visited] = INF
    for _next in range(n):
        # 아직 _next를 방문하지 않았다면
        if not (visited & (1<<_next)):
            cache[cur][visited] = \
            min(cache[cur][visited], dist[cur][_next]+shortest_path2(_next, visited+(1<<_next)))

    return cache[cur][visited]


if __name__ == "__main__":
    print(shortest_path2(0, 1))