[알고리즘]TSP(Travelling Salesman Problem) 프로그램

소개글

TSP 프로그램 + 분석 노트(hwp)

목차

없음

본문내용

1. 목적
1.1 Travelling Salesman Problem에 대한 개념 이해 및 NP-Complete 문제에 대한 해결 방안에 대한 고찰을 통해 각 문제점에 대한 가장 적합하고 효율적인 알고리즘을 선택하기 위함에 있다. 나아가 C 프로그래밍에 대한 자신감과 숙련을 통하여 컴퓨터 엔지니어로서의 발전을 도모한다.

2. 사용한 알고리즘의 선정 이유
- 먼저 TSP에 대해서 모든 가는한 경로를 살펴보는 O(n!)의 복잡도를 가지는 알고리즘과 Minimum Spanning Tree를 이용한 알고리즘(prim 알고리즘)을 이용하여 구현하였다.
- TSP 문제에서 모든 가능한 경로의 수는 (n-1)!개나 된다. 그 경로를 모두 확인하여 최적의 경로를 찾는 방법을 통하여 가장 최적화된 루트를 구할 수 있다.
- 그리고, MST 알고리즘을 사용하면, (n-1)!의 경로를 확인하지 않고, 가장 짧은 거리부터 차례로 인식하기 때문에 한번의 검색으로 TSP 문제를 해결할 수 있는 아주 속도면에서 최적화된 결과를 얻을 수 있다.

3. 구현한 알고리즘의 분석 및 예상 결과
- 최초 문제에서 약 1분이내의 시간을 가지는 n의 값을 선택하여 결과를 비교하라고 하여, n이 적을때부터 차례대로 그 차이를 알기위해 2씩 차이를 두어 linear한 결과를 얻고자 했다.
- n이 11이 되었을 때, 약 2분의 시간이 소요 되었으며, 그 이상의 개수에 대해서는 너무 많은 시간이 걸려 측정의 범위를 1~11까지로 하였다.
- 데이터의 입력은 텍스트 파일에서 읽어오도록 하였으며, 텍스트 파일은 주어진 지도에서 임의의 도시들을 선택하여 각 도시에서의 거리를 직접 확인해 샘플링하여 만들어 냈다.
- 출력은 각 알고리즘에 따른 경로를 출력하고, 각 알고리즘의 시간복잡성을 알아보기 위해서 각 프로그램의 실행 시간을 측정하여 비교하였다. QueryPerformanceCounter 함수를 사용하여, 밀리 초 단위로 측정하였으며, 소수점 아래 4자리까지 고려하여 시간을 출력하였다.
- 각 프로그램에서 사용된 알고리즘은 다음과 같다.

3.1. TSP 일반 알고리즘
먼저 임의의 위치에서 현재 경로의 거리 총합을 더한 후, 반복적으로 경로를 바꿔가며 비교하여 이전의 경로보다 짧은 경로를 만나면 그 짧은 경로를 택하는 방법을 사용하였다.

참고 자료

없음

압축파일 내 파일목록

data.txt
tsp analysis.hwp
tsp 그래프 비교.xls
tsp.c
TSP도시표.xls