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

목차

1. 과제 내용
2. 구현 하기
3. 구현 결과

본문내용

* 과제내용
동적 계획법 알고리즘으로 구현하고 다음지도에 대해 해를 구하도록 한다.
해를 구하면 일주 경로를 출력하고 총 경로의 길이를 출력하도록 한다.
- 출발지를 대구로 한 경우 최단 일주 경로
- 출발지를 서울로 한 경우 최단 일주 경로

* 구현하기
TSP를 구현하기 위해서 동적계획법에서 배운 floyd2알고리즘을 이용하여 풀어보았다.
D배열에서 집합을 어떻게 표현할지에 대해서 생각해본 결과 비트로 도시의 방문 여부를 체크 할 수 있는 비트마스킹 방법을 이용하였다. 우선 과제로 나온 도시의 숫자는 NUM=12개이고 가중치의 무한대 역할을 할MAX를 선언 해주었다. 그리고 2차원 배열을 생성하여 12개의 도시가 가지고 있는 각각 도시의 가중치를 입력하였다. TSP구현을 위해 사용한 함수는 5개이다.
우선 get_citypos()는 경유 가능한 도시의 집합을 인자로 받은 뒤 집합 맨 앞의 도시의 위치를 반환한다.

참고 자료

없음