6.7 예제 : 최적화 문제 - 여행하는 외판원 문제(Python)

1. 최적화 문제

(1) 최적화 문제란?

• 문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아내는 문제를 통칭한다.
• 최적화 문제를 해결하는 방법 중 가장 기초적이고 기초적인 방법으로 '완전 탐색'을 사용한다.

 

2. 여행하는 외판원 문제(Traveling Sales-man Problem, TSP)

(1) 문제 설명

• 어떤 나라에 n개(2 <= n <= 10)의 큰 도시가 있다고 한다.
• 한 영업 사원이 한 도시에서 출발해 다른 도시들을 전부 한 번씩 방문한 뒤 시작 도시로 돌아오려고 한다.
• 문제를 간단하게 하기 위해, 각 도시들은 모두 직선 도로로 연결되어 있다고 가정한다.
• 이때 가능한 모든 경로 중 가장 짧은 경로를 어떻게 찾아낼 것인가?

 

(2) 완전 탐색을 통해 제한 시간 안에 문제 해결이 가능할까?

• 일반적으로 1초당 반복문 수행횟수가 1억을 넘어가면 시간 제한을 통과할 가능성이 있다고 한다.(4.6 수행 시간 어림짐작하기)
• 도시의 수가 최대 10개이기 때문에 시작 도시를 제외한 9개의 도시를 어떤 순서로 나열할지 최대 9!개의 방법이 존재한다.
• 9! = 362,880 이므로 완전 탐색을 통해 문제를 해결할 수 있음을 알 수 있다.

 

(3) 코드

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

# 두 도시 간의 거리를 저장하는 2차원 리스트
# dist[i][j] : i번째 도시에서 j번째 도시까지의 거리를 의미
dist = []
for i in range(n):
    dist.append(list(map(int, input().split())))

path = [0] # 여행 정보를 담고 있는 리스트
visited = [False] * n # 각 도시에 대해 방문 여부를 담고 있는 리스트
visited[0] = True # 시작 도시를 0번 도시로 가정

def shortestPath(path, visited, current):
    # 기저 사례 : 모든 도시를 방문했을 경우, 시작 도시로 돌아가 종료함
    if len(path) == n:
        return current + dist[path[0]][path[len(path)-1]]

    result = INF

    for next in range(n):
        # 이미 방문했다면 다음 반복으로
        if visited[next]:
            continue

        here = path[len(path)-1]
        path.append(next)

        visited[next] = True
        
        candid = shortestPath(path, visited, current + dist[here][next])

        result = min(result, candid)
        visited[next] = False
        path.pop(len(path)-1)

    return result

print(shortestPath(path, visited, 0))

• 변수 here : 마지막으로 방문한 도시 번호
• 변수 candid : 다음 방문할 도시까지의 거리를 재귀적으로 계산하여 저장 후 result와 비교하여 가장 짧은 거리를 찾기 위해 사용된다.

 

---

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

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies