[알고리즘]외판원 알고리즘의 구현

소개글

- 외판원 알고리즘의 구현

문제 : 가중치포함 방향그래프에서 최적 일주여행경로를 결정하라. 가중치는 음이 아닌 정수다.
입력 : 가중치포함 방향그래프, N(그래프에서 정점의 개수), 그래프는 행과 열의 인덱스의 범위가 모두 1부터 N까지인 2차원 배열 W로 표현한다. 여기서 W[i][j]는 I번째 정점에서 j번째 정점을 연결하는 이음선의 가중치이다.
출력 : 변수 minlength(이 변수의 값이 최적 일주여행경로의 길이가 된다.), 2차원 배열 P(이 배열을 가지고 최적 일주여행경로의 경로를 구축할 수 있다.)

목차

1. 제목
2. 문제에 대한 정의
3. 알고리즘
4. 실행결과
5. 첨부(소스코드)
6. 참고자료

본문내용

외판원이 20개 도시로 판매출장을 계획하고 있다고 가정해 보자. 각 도시는 다른 도시 중 몇 개와 도로로 연결 되어 있다. 출장시간을 최소화기 위하여, 외판원이 거주하고 있는 도시에서 출발하여, 각 도시를 한 번씩 방문하고, 다시 출발한 도시로 돌아오는 가장 짧은 경로를 찾고 싶다. 이러한 최단경로를 구하는 문제를 외판원 문제라고 한다.
이 문제의 사례는 각 정점을 도시를 나타내도록 하여 가중치포함 그래프로 표현할 수 있다. 한 방향으로 가는 가중치가 그 반대방향으로 가는 가중치와 다른 경우도 포함하도록 문제를 일반화 한다. 여기서도 가중치는 음이 아닌 정수로 가정한다. 방향그래프에서 일주여행경로는 한 정점에서 출발하여 다른 모든 정점을 한번씩만 거치고 출발한 정점으로 돌아오는 경로이다. 가중치포함 방향그래프에서 최적일주여행경로는 그러한 경로 중에서 최소 길이를 가진 경로이다. 외판원 문제는 최소한 하나의 일주여행경로가 존재하는 경우 가중치포함 방향그래프에서 최적 일주여행경로는 찾는 문제이다.

참고 자료

알고리즘 (사이텍미디어, 도경구)