이 글에서 소개하는 프로그램은 최근접 이웃(Nearest Neighbour) 알고리즘을 C++로 구현한 예제입니다. 이 알고리즘은 외판원 문제(Traveling Salesman Problem, TSP)를 해결하는 데 활용되며, 그래프의 모든 노드를 방문하면서 각 간선을 한 번씩만 통과할 때 드는 최소 비용을 계산하는 것이 목표입니다.
필요한 함수와 의사 코드
알고리즘
전체 흐름은 다음 의사 코드와 같습니다. 두 값을 맞바꾸는 swap(), 경로의 총비용을 계산하는 cal_sum(), 가능한 모든 순열을 생성하는 permute() 세 가지 함수가 핵심 역할을 합니다.
시작
c = 0, cost = 1000으로 초기화
인접 행렬 g[][] 초기화
swap(): 두 값 x와 y를 서로 교환하는 함수
cal_sum(): 배열 a[]와 배열 크기를 입력받아 비용을 계산하는 함수
sum = 0으로 초기화
for i = 0 to n
s += g[a[i % 3]][a[(i + 1) % 3]] 계산
if (cost > s)
cost = s
permute(): 순열을 수행하는 함수
배열에 요소가 하나뿐이라면
cal_sum() 호출
그렇지 않다면
for j = i to n
(a + i)와 (a + j)를 교환
cal_sum(a + 1, n)
(a + i)와 (a + j)를 원래대로 되돌림
종료
C++ 예제 코드
다음은 위 알고리즘을 실제로 구현한 전체 소스 코드입니다.
#include<iostream>
using namespace std;
int c = 0, cost = 1000;
int g[3][3 ] = { {1,2,3},{4,5,8},{6,7,10}};
void swap(int *x, int *y) {
int t;
t = *x;
*x = *y;
*y = t;
}
void cal_sum(int *a, int n) {
int i, s= 0;
for (i = 0; i <= n; i++) {
s+= g[a[i %3]][a[(i+ 1) %3]];
}
if (cost >s) {
cost = s;
}
}
void permute(int *a,int i,int n) {
int j, k;
if (i == n) {
cal_sum (a,n);
} else {
for (j = i; j <= n; j++) {
swap((a + i), (a + j));
cal_sum(a+1,n);
swap((a + i), (a + j));
}
}
}
int main() {
int i, j;
int a[] = {1,2,3};//배열 요소 지정
permute(a, 0,2);
cout << "minimum cost:" << cost << endl;
}
실행 결과
minimum cost:3
코드 동작 원리
swap() 함수
포인터를 이용해 두 변수의 값을 서로 맞바꾸는 보조 함수입니다. 임시 변수 t를 사용해 안전하게 값을 교환합니다.
cal_sum() 함수
현재 순서로 배치된 노드 배열 a[]를 따라 이동할 때의 총비용을 계산합니다. 인접 행렬 g[][]에서 연속된 두 노드 사이의 가중치를 더하고, 마지막 노드에서 출발 노드로 돌아오는 비용까지 포함합니다. 계산된 비용 s가 기존의 최소 비용 cost보다 작으면 값을 갱신합니다.
permute() 함수
재귀적 교환(swap) 방식으로 노드 방문 순서의 모든 순열을 생성합니다. 각 순열이 만들어질 때마다 cal_sum()을 호출해 해당 경로의 비용을 평가하고, 탐색 후에는 배열을 원래 상태로 되돌려 다음 경우의 수를 확인합니다.
main() 함수
방문할 노드 번호를 담은 배열 {1, 2, 3}을 준비한 뒤 permute()를 호출해 전체 탐색을 시작하고, 최종적으로 구해진 최소 비용을 화면에 출력합니다.
참고 사항
이 예제처럼 모든 순열을 하나씩 검사하는 완전 탐색 방식의 시간 복잡도는 O(n!)입니다. 따라서 노드 수가 늘어나면 실행 시간이 기하급수적으로 증가합니다. 외판원 문제는 대표적인 NP-난해(NP-hard) 문제로, 노드 수가 많은 실제 환경에서는 동적 계획법, 근사 알고리즘, 휴리스틱 기법 등을 함께 활용하는 것이 일반적입니다.