2020년 알고리즘 TSP구현하기 보고서

1. 과제 내용

2020년 알고리즘 TSP 구현하기 보고서의 첫 번째 과제 내용은 여행 판매원 문제(TSP, Traveling Salesman Problem)의 이해 및 구현에 관한 것이다. TSP는 주어진 도시의 집합과 각 도시 간의 거리 정보가 주어졌을 때, 모든 도시를 한 번씩 방문하고 다시 출발 도시로 돌아오는 최단 경로를 찾는 문제이다. 이 문제는 컴퓨터 과학과 최적화 문제에서 중요하며, NP-완전 문제로 알려져 있다. 이는 문제의 크기가 커짐에 따라 해결하기가 어려워진다는 것을 의미한다. TSP의 본질은 경로 최적화에 있다. 자연스럽게 대규모의 데이터를 처리하고 최적의 해결책을 찾는 과정에서 다양한 알고리즘적 접근법이 필요하게 된다. 가장 간단한 접근법은 브루트 포스(brute-force) 방법으로, 모든 가능한 경로를 계산하고 그 중 최단 경로를 선택하는 방식이다. 하지만 이 방법은 도시의 수가 증가할수록 계산량이 기하급수적으로 늘어나기 때문에 실용적이지 않다. 따라서 보다 효율적인 알고리즘이 필요하며, 이를 위해 동적 프로그래밍, 분기 한정(branch and bound), 유전 알고리즘, 근사 알고리즘 등의 다양한 방법론이 개발되었다. 이 과제에서는 TSP 알고리즘의 …