9.11 예제 : 여행하는 외판원 문제(Python)_정수 이외의 입력에 대한 메모이제이션

문제 출처 : algospot.com :: TSP2

algospot.com :: TSP2

---

1. 함수의 정의 바꾸기

• 6.7 단원(6.7 예제 : 최적화 문제 - 여행하는 외판원 문제(Python) (tistory.com))에서 완전 탐색 알고리즘을 통해 이 문제를 해결한 전력이 있다.
• 전에는 n개의 도시들에 대해 n!개의 경로를 모두 생성하는 방법을 사용했는데, n이 15만 되더라도 계산이 불가능할 지경이다.
• 또한, shortestPath( )함수에서 인수로 들어가는 path가 같은 경우가 없어(두 번이상 같은 인수로 호출되는 경우가 없어) 메모이제이션이 불가능했다.

 

• 메모이제이션을 위해 지금까지 한 선택들에 대한 정보를 최소한만 받도록 함수의 정의를 고쳐야 한다.
• 기존 6.7 단원의 shortestPath( )의 매개변수가 (경로를 저장하는 리스트, 방문여부를 저장하는 리스트, 현재 위치)였다면, 다음과 같이 필요한 매개변수를 바꾸어 shortestPath2( )를 정의 한다.

 

• 1. 방문한 경로의 길이 계산 : 기존에는 전체 경로의 길이를 반환했다면 이제는 남은 경로의 최소 길이만을 반환하도록 한다. 어떤 순서대로 도시들을 방문했는지는 중요하지 않다. 그러나 현재 위치(만들어진 경로의 마지막 위치 = here)은 알 필요가 있다.
• 2. 어떤 도시의 방문 여부 확인 : 특정 도시를 방문했는지 여부는 확인해야 한다.(=visited) 그러나 1의 경우와 마찬가지로 어떤 순서대로 방문했는지는 중요하지 않다.

 

• shortestPath2(here, visited) = 현재 위치가 here이고 각 도시들을 방문한 적이 있는지 저장된 boolean 값의 배열 visited가 주어질 때, here에서 시작해 나머지 도시를 방문하는 부분 경로의 최소 길이를 반환한다.

 

• 이 함수 정의를 통해 입력으로 주어질 수 있는 부분 문제의 수는 n * 2^n개 이다.(n = 도시의 수, 2^n = 도시의 방문 여부)
• 지수 시간이 소요되므로 비교적 오래 걸릴 것으로 생각할 수 있지만 n!와 비교하면 상대적으로 매우 빠른 속도를 자랑한다.

---

2. 메모이제이션

• 메모이제이션을 하기 위해 저장 공간(cache)을 2차원 리스트로 만들어 현재 도시의 위치와 도시의 방문 여부를 토대로 계산 결과를 저장한다.
• 그런데 도시의 방문 여부를 boolean 값의 배열을 저장했기 때문에 메모이제이션을 위한 cache를 만들 때 약간의 난항을 겪는다.
• 이 문제에서 2차원 리스트 cache에 접근할 때 cache[here][visited] 형식으로 접근해야 하는데, visited가 앞서 설명한대로 boolean 값의 리스트이기 때문에 이를 일대일 대응으로 표현할 수 있는 숫자를 찾아야 한다.(만일, visited의 값이 [True, Ture, False, False]인 경우 이에 대응되는 어떤 값 i를 찾아야 한다.)
• 이를 해결하기 위해 visited의 값을 boolean 값이 아닌 비트 형식으로 치환하여 사용하면 일대일로 대응되는 숫자로 사용할 수 있다.
• 예를 들어, [True, True, False, False]인 경우 True = 1, False = 0로 정의하여 1100으로 생각할 수 있다.

 

• 비트 마스크를 활용하면 위 생각을 적용할 수 있다.
• 그러나 주의해야 할 점이 하나 있는데, 일반적으로 길이가 n인 리스트의 인덱스가 0번 부터 n-1까지 표현된다면, 비스 마스크를 활용하면 n-1번 부터 0번까지의 역순으로 표현된다.
• 예를 들어, [True, True, False, False]인 경우 1100이 아니라 0011이 맞다.
• 이 비트로 표현된 값으로 현재 도시의 방문 여부를 특정 정수와 일대일로 대응시켜 cache에 접근할 수 있게 된다.
• 차례로 0번, 1번 도시에 방문 -> [True, True, False, False] -> 0011 -> cache[1][0011] 과 같은 식으로 접근

---

3. 코드 구현 - 문제풀이 해설 방법

n = int(input())
INF = int(1e9)

dist = []
for i in range(n):
    dist.append(list(map(int, input().split())))
    
# cache[here][visited] 형태로 저장
# visited는 마을의 통과 여부를 결정한다.
# bool 자료형을 메모이제이션하지 않고 비트 형태로 치환하여 사용
# 예를 들어 [True, False, True, False]인 경우 0b1010(-> 0b0101) 같이 표현 가능
# 1<<4의 경우 0b10000 와 같이 1 뒤에 0이 4개 붙는 형식

# 유의해야 될 점은 일반적인 경우와 달리 n번 부터 역순으로 차례로 저장되는 형태로 구현되었다.
# 예를 들어 4개 마을(0~3번 마을) 중 0번 마을을 방문했으면 1000이 아닌 0001이다.
# 3번 마을을 방문했으면 0001이 아닌 1000이다.
cache = [[-1] * int(1<<n) for _ in range(n)]

def shortestPath2(here, visited):
    # 기저 사례 : 모든 도시를 모두 방문했으면 출발 도시로 돌아가고 종료한다.
    # 출발 도시는 항상 0번 도시라고 가정!
    # n == 4 일 때, (1<<4)-1을 하면 0b01111 이므로 모든 4개 도시에 대해 [True, True, True, True]와 같은 의미가 된다.(제일 큰 비트는 제외)
    # 이를 응용하여 모든 도시를 방문했는지 검사가 가능하다.
    if visited == (1<<n)-1:
        return dist[here][0] # 마지막 도시에서 출발지로 돌아가는 거리를 추가하기 위함

    # 메모이제이션
    if cache[here][visited] >= 0:
        return cache[here][visited]

    cache[here][visited] = INF

    # 다음 방문할 도시를 검사
    for next in range(n):
        # 이미 방문한 도시인 경우 건너뜀
        if visited & (1<<next):
            continue

        # 아직 방문하지 않은 도시들에 대해 최단 거리를 계산
        # 재귀적인 호출로 각 경로에 대해 모든 도시를 방문하는 거리를 계산한다.
        # visited + (1 << next)는 이 반복문을 통해 해당 도시를 방문했음을 의미한다.
        candid = dist[here][next] + shortestPath2(next, visited + (1<<next))

        # 모든 재귀 호출에 대해 최단 거리를 결정
        cache[here][visited] = min(cache[here][visited], candid)

    return cache[here][visited]

print(shortestPath2(0, 0))

---

4. 후기

  정수 이외의 입력에 대한 메모이제이션에 대한 예제 문제이다. 개념적인 설명부분은 블로그에서는 따로 설명하지 않고 넘어갈 예정이다. 뒤에서 이런 비트 마스크 방법으로 메모이제이션을 사용한 문제들이 몇 가지 있기 때문에 마찬가지로 비트마스크를 사용하는 예제를 포스팅한다.

  이 예제를 풀면서 가장 애먹었던 부분이 바로 비트로 치환하면 일반적인 리스트의 인덱스 순서와 역순으로 표시되는 점이 이해를 어렵게 했다. 지금은 이해했으니까 너무 당연한 이야기기는 한데, 책 자체가 비트 마스크 이야기가 '16장 예습해오세요~' 이런 느낌이라 시간상(사실 예습하기 귀찮아서) 경험적으로 이해하게 되었다. 그래도 이해하기 전에는 왜이렇게 복잡하게 적용해야 되나 싶었는데 막상 이해하고 나니까 굉장히 획기적인 방법이라고 생각이 든다. 특히, 방문 여부를 검사할 때 혹은 모든 도시를 방문했는지 확인하는 과정이 그렇다. 그렇게 오늘도 나에게만 좋은 참고자료 하나를 새로 만들게 되었다.

---

 

github : Algorithmic_Problem_Soving_Strategies/example9_11.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies