[알고리즘] Traveling Salesman Problem

Traveling Salesman Problem은 NP 알고리즘 중 하나로 최적의 경로를 찾기 위해서는 2ⁿ의 시간이 필요합니다 따라서 최적의 해가 아닌 approximate(근사해)를 통해 접근하도록 한다

 

1. Traveling Salesman Problem (TSP)

 

 여행자가 임의의 한 도시에서 출발하여 다른 모든 도시를 1번씩만 방문하고 다시 출발한 도시로 돌아오는 여행 경로의 길이를 최소화하는 문제이다

• A에서 B까지의 경로는 B에서 A까지의 경로가 같다는 대칭성
• A에서 B로 가는 거리는 A에서 C를 경유하여 B로 가는 거리보다 짧다는 삼각 부등식의 특성

 

2. 문제 해결을 위한 아이디어

 

 주어진 여행 장소를 MST(최소 신장 트리)로 나타내어 모든 점을 연결한다

 TSP를 만들기 위해 MST의 경로를 따라 DFS(깊이 우선 탐색)으로 TSP 경로를 만든다

해당 TSP의 경로의 길이를 구한다

 

 

MST를 만들기 위한 아이디어 : 각 정점의 길이를 구해야한다 - 정점의 좌표를 설정해야한다

해당 정점의 좌표로 길이를 구하고 가중치로 설정한다

가중치로 설정한 edge 중 kruskal 알고리즘과 Prim 알고리즘을 이용하여 MST를 만든다

 

 

만들어진 MST의 간선을 따라서 모든 도시를 방문하고 돌아오는 순서를 만든다

해당 순서에서 첫 정점을 제외한 모든 중복 정점을 제거한다

 

 

3. 코드 작성

 

1) 구현환경

 

Window Subsystem Linux 2를 이용하여 Ubuntu 22.04 LTS에서 실행

Code 작성 및 실행은 VS code 와 terminal을 이용하여 실행

코드 구현 환경 및 terminal 사용 예시

 

2) 구현 코드

 

import heapq

coordinates = [(0,3),(7,5),(6,0),(4,3),(1,0),(5,3),(2,2),(4,1)]

visited = [0] * (len(coordinates)) # 노드의 방문 정보 초기화
graph = [[] for _ in range(len(coordinates))]  # 그래프 초기화
edges = []

# 좌표간의 거리 계산 및 간선 추가
for i in range(len(coordinates)):
    for j in range(i + 1, len(coordinates)):
        x1, y1 = coordinates[i]
        x2, y2 = coordinates[j]
        distance = ((x1 - x2) ** 2 + (y1 - y2) ** 2)
        edges.append((distance, i, j))

# 무방향 그래프 생성
for i in edges: # 간성 정보 입력 받기
    weight, u, v = i
    graph[u].append([weight, u, v])
    graph[v].append([weight, v, u])


# 프림 알고리즘
def PrimMST(start):
    visited[start] = 1 # 방문 갱신
    candidate = graph[start] # 인접 간선 추출
    heapq.heapify(candidate) # 우선순위 큐 생성
    mst = [] # mst

    while candidate:
        weight, u, v = heapq.heappop(candidate) # 가중치가 가장 적은 간선 추출
        if visited[v] == 0: # 방문하지 않았다면
            visited[v] = 1 # 방문 갱신
            mst.append((u,v,weight)) # mst 삽입

            for edge in graph[v]: # 다음 인접 간선 탐색
                if visited[edge[2]] == 0: # 방문한 노드가 아니라면, (순환 방지)
                    heapq.heappush(candidate, edge) # 우선순위 큐에 edge 삽입

    return mst

def mst_to_graph(mst_edges):
    graph = {}
    for edge in mst_edges:
        u, v, weight = edge
        if u not in graph:
            graph[u] = []
        if v not in graph:
            graph[v] = []
        graph[u].append(v)
        graph[v].append(u)
    return graph

def dfs(graph, start_node, visited=None):
    if visited is None:
        visited = set()
    visit = []
    stack = [start_node]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            visit.append(node)
            stack.extend(graph[node])

    return visit

def calculate_tsp_distance(graph, tsp_path, coordinates):
    total_distance = 0
    for i in range(len(tsp_path) - 1):
        start_node = tsp_path[i]
        end_node = tsp_path[i + 1]
        x1, y1 = coordinates[start_node]
        x2, y2 = coordinates[end_node]
        distance = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
        total_distance += distance
    return total_distance


def tsp(graph, start_node, coordinates):
    circuit = dfs(graph, start_node)
    unique_circuit = list(dict.fromkeys(circuit))  # 중복 제거
    unique_circuit += [unique_circuit[0]]
    tsp_path = []
    tsp_distance = calculate_tsp_distance(graph, unique_circuit, coordinates)
    for i in unique_circuit:
        if i == 0:
            tsp_path.append('A')
        elif i == 1:
            tsp_path.append('B')
        elif i == 2:
            tsp_path.append('C')
        elif i == 3:
            tsp_path.append('D')
        elif i == 4:
            tsp_path.append('E')
        elif i == 5:
            tsp_path.append('F')
        elif i == 6:
            tsp_path.append('G')
        elif i == 7:
            tsp_path.append('H')
    return tsp_path, tsp_distance

mst_g = mst_to_graph(PrimMST(0))
tsp_path, tsp_distance = tsp(mst_g,0,coordinates)
print(tsp_path)
print(tsp_distance)

 

 

4. 출력 결과

 

['A', 'G', 'E', 'D', 'H', 'C', 'F', 'B', 'A']
26.22165929381374

물론 해당 경로와 이동거리가 최적해는 아니지만 MST를 통해 TSP 문제를 다항시간 내에 근사해를 구할 수 있다