알고리즘 - TSP(Traveling Salesman Problem) ver BF

 

https://xkcd.com/399/

최근 며칠간 작성한 파이썬과 자료 구조 글은 전부 이 글을 위한 빌드업이었다.

유명한 여러 문제를 도전하다가, TSP에 도달했고, 결과는 실패였다.

내가 도전한 방법은 백트래킹을 이용한 brute force였고, 알고리즘상 동작은 하지만 TLE가 뜬다.

내가 생각한 과정과, 깔끔하게 정리를 잘해주신 한 분의 알고리즘을 살펴보려고 한다. 

이베이처럼 어디 한번 따라가보자.

 

# ---------- Function ----------
def TSP(current: int, total: int):
    global min_cost
    
    if all(visited):
        min_cost = min(min_cost, total)
        return
    
    for idx, next in enumerate(graph[current]):
        if idx == start and sum(visited) != cities-1:
            continue
        
        if not visited[idx] and next:
            visited[idx] = True
            TSP(idx, total + next)
            visited[idx] = False

# ---------- Main ----------
cities = int(input())
graph = [list(map(int, input().split())) for _ in range(cities)]

min_cost = 1e9
visited = [False] * cities

for start in range(cities):
    TSP(start, 0)
    
print(min_cost)

처음 작성한 코드다. 방문 여부를 나타내는 visited를 선언하고, 백트래킹으로 문제를 접근했다.

부분부분 쪼개서 살펴보자. 입력과 초기화 같은 간단한 부분들은 설명을 생략한다.

 

for start in range(cities):
    TSP(start, 0)

다양한 조건의 TSP 문제가 있지만, 백준 10971번을 기준으로 작성했다.

"어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로"를 찾는다.

즉 어디에서 출발할지 모르기에, 모든 도시를 출발지로 설정해서 확인을 해줘야 한다.

그 시작점을 설정해주는 brute force 부분이다.

 

 

global min_cost

if all(visited):
    min_cost = min(min_cost, total)
    return

TSP 내부에서 동작하는 코드다.

TSP 함수 내부가 아닌 global 위치에 있는 min_cost 변수를 사용하려 한다. global로 변수를 선언한다.

all() 함수를 이용해 visited를 모두 방문했는지 확인한다.

모든 도시를 방문했다면, min_cost와, 현재 경로를 계산한 total 중 더 작은 값을 저장한다.

그리고 backtracking으로 진행 중이기에 return으로 돌아가 다른 경로를 탐색한다. 

 

for idx, next in enumerate(graph[current]):

TSP 매개변수로 받은 '현재 도시'를 나타내는 currnet 변수다.

graph에는 각 도시들이 어떤 도시와 이어져있는지, 그 여부를 알려주는 값이 들어가있다.

즉, graph[current]는 current 도시에서 어느 도시로 갈 수 있는지의 list이다.

다음 도시로 갈 수 있다고 할 떄, 도시를 idx로 이동 비용을 next로 받아온다. 

 

if idx == start and sum(visited) != cities-1:
    continue

처음 작성했을 때, 이 코드가 없어서 엉뚱한 값을 출력했다.

문제 조건에도 있지만 '외판원은 원래의 도시로 돌아와야 한다.'  이를 간과했다.

다른 코드들을 보면 출발한 도시를 방문했다치고, 마지막에 돌아갈 수 있는지 확인한다.

나는 이와 반대로 아예 시작한 도시의 방문 여부를 확인하지 않고, 마지막에 도착해서 확인하기로 했다.

그래서 중간에 처음으로 빠지지 않게 해주는 코드가 필요하다. 이 코드가 그 부분이다.

 

다음으로 갈 도시(idx)가 시작 도시(start)면서, 그곳을 빼고 전부 방문했다면 출발지로 되돌아간다.

visited의 합은 도시의 수(cities)와 같아야 한다. 즉 cities - 1이 방문 도시의 합과 같다면, 출발지만 남은 것이다.

그래서 같지 않다면 continue로 넘어갔다.

 

if not visited[idx] and next:
    visited[idx] = True
    TSP(idx, total + next)
    visited[idx] = False

만약 다음 도시를 방문하지 않았고, 도시를 방문할 수 있다면(거리; next가 있다면) 수행한다.

방문을 True하고, backtracking을 진행, 다시 방문을 False로 만들어 계속 반복한다.

 

문제 예제와 직접 작성한 예외 가능성이 있는 예제들, 그리고 인터넷 예제들.

단순 예제 대입이 아니라 알고리즘의 동작 과정들을 생각해보며 정답을 비교해보았다.

동작은 맞지만 brute force이기에, 이 문제는 O(n!)을 가져 TLE가 발생한다.

 

def TSP(cost: list, length: int) -> int:
    INF = float('inf')
    answer = INF
    VISITED_ALL = (1 << length) - 1
    
    def find_path(start, last, visited, distance):
        nonlocal answer
        
        if visited == VISITED_ALL:
            return_to_start = cost[last][start] or INF
            answer = min(answer, distance + return_to_start)
            return
        
        for city in range(length):
            if visited & (1 << city) == 0 and cost[last][city]:
                find_path(start, city, visited | (1 << city), distance + cost[last][city])
        
    for start in range(length):
        find_path(start, start, 1 << start, 0)
        
    return answer

그리고 이게 인터넷을 돌아다니다 찾은 코드이다.

이 글을 작성하신 분의 블로그에는 영어로만 작성한 글도 있을 정도로, 진심임을 알 수 있다.

한번 해석해보자.

 

def TSP(cost: list, length: int) -> int:

TSP라는 함수를 선언하고, cost와 length를 매개변수로 받는다.

cost는 누가봐도 '비용'이 담긴 list이고, length는 길이이니 도시의 개수임을 알 수 있다.

확실히 잘 짜여진 코드는 변수명부터 다르다. 직관적이지만 간결하다.

 

INF = float('inf')
answer = INF
VISITED_ALL = (1 << length) - 1

INF를 무한 값이 담긴 상수로 선언한다. 그리고 answer는 최솟값을 위한 변수이니 우선 INF로 초기화한다.

비트마스킹을 이용하여 VISITED_ALL을 선언한다. length 길이가 4라면 VISITED_ALL은 15(1111)가 된다.

 

def find_path(start, last, visited, distance):
    nonlocal answer

중첩 함수로 find_path()를 TSP 내부에 선언한다.

전해주는 매개변수는 출발지(start), 현재 도시(last), 방문 여부(visited), 이동 거리(distance)다.

이때 answer는 find_path 밖에 있는 비지역 변수로 nonlocal로 선언하여 사용한다.

 

if visited == VISITED_ALL:
    return_to_start = cost[last][start] or INF
    answer = min(answer, distance + return_to_start)
    return

만약 현재 방문 여부(visited)가 전부 방문한 것(VISITED_ALL)이라면 실행하는 조건문이다.

return_to_start 변수에 마지막 도시에서 출발지로 돌아가는 값을 저장한다.

cost or INF를 함으로써, 돌아갈 수 있다면 cost를, 돌아갈 수 없다면 INF를 저장한다.

돌아갈 수 있다면, cost는 True(값이 있는 상태)이다. 즉 or 연산에서 뒤를 볼 필요없이 cost를 저장한다.

돌아갈 수 없을 때 INF를 저장하면, 무한 값이 들어가 최솟값 비교에서 반드시 물러나게 된다.

그리고 backtracking을 위해 return하여 되돌아간다.

 

for city in range(length):
    if visited & (1 << city) == 0 and cost[last][city]:
        find_path(start, city, visited | (1 << city), distance + cost[last][city])

모든 도시들을 하나하나 확인하는 brute force 부분이다.

도시의 수(length)만큼 반복문을 돌면서 index를 city로 받아들여 사용한다.

아직 도시를 방문하지 않았으면서(visited & (1 << city)), 값이 있다면 실행하는 조건문에 들어간다.

만약 도시를 미방문했으면, find_path에 각각의 인자를 전해주어 호출한다.

visited에는 비트마스킹을 이용해, 현재 도시를 방문 처리(visited | (1 << city))한 뒤 전해준다.

distance에는 현재까지 거리(distance)에 다음 도시까지 이동 비용(cost[last][city])을 더해준다.

 

for start in range(length):
    find_path(start, start, 1 << start, 0)

어떤 도시에서 출발하는 것이 가장 최단 거리일지 외판원은 모른다.

그렇기에 모든 도시에서 출발해봐야 최단 거리를 알 수 있다.

각 도시들을 하나하나 출발지(start)로 설정하여 돌아가는 모습이다.

이때 visited는 출발지(start)만을 방문 여부를 켠 뒤(1 << start) 전해준다. 

 

return answer

그리고 마지막으로 정답을 return하면서 코드는 끝이 난다.

inf, bitmasking, nested function, namespace, logical operator까지 그야말로 모든 정수를 응축해놓았다.

내가 방법을 생각하여 정답에 도달할 수 있다면, 물론 그게 최고긴 하다.

하지만 내 힘으로는 부족할 때, 적극적으로 도움을 찾아보는 것도 중요하다.

 

 

고민을 시작한 문제 출처 : https://www.acmicpc.net/problem/10971

참고한 문서 자료 : https://en.wikipedia.org/wiki/Travelling_salesman_problem

참고한 웹 사이트 : https://shoark7.github.io/programming/algorithm/introduction-to-tsp-and-solve-with-exhasutive-search

참고한 웹 사이트 : https://hackmd.io/@arthurzllu/SkZBc7GoI

참고한 웹 사이트 : https://velog.io/@dltmdrl1244/알고리즘-외판원-순회TSP-알고리즘