N사이즈의 완전 그래프에서 1번 정점에서 출발한 뒤 모든 정점을 한번만 방문한 뒤 다시 1번 정점으로 돌아오는 경로 중, 가장 비용이 적게드는 경로를 탐색하는 알고리즘을 작성해보자. 단 그래프는 방향 그래프이다.
모든 정점을 방문한 최소값을 찾아야하므로 모든 경로를 완전탐색해야한다.
일반적으로 떠올릴 수 있는 완전탐색 알고리즘을 작성하면 모든 경로를 탐색하기 되므로
1 x (n - 1) x (n - 2) ... 1 x 1의 알고리즘이 완성된다. 즉 알고리즘 복잡도가 n!이 되는 것이다.
10!이 대략 363만 정도니까 정점 10개 넘어가면 거진 못푼다고 봐야한다.
이런 종류의 특별한 해법이 없고 완전 탐색을 해야하는데 주어진 시간 내에 탐색이 불가능한 문제들을 푸는 방법이다.
Local Search::
로컬 서치는 시간적으로 봤을 때 더이상 최적화가 불가능한 문제의 근삿값을 찾아내는 기법을 말한다.
위의 완전탐색 문제를 지역 탐색으로 풀면 다음과 같다.
srand(time(0));
min = 0;
dt[1] = 1;
for(i=2;i<=n;i++) {
min += arr[i-1][i];
dt[i] = i;
}
min += arr[n][1];//기본값 저장
for(i=1;i<=1000000;i++) {//1000000은 프로그램 실행시켜보고 제한 시간에 맞도록 변경
int rn1 = rand() % (n-1) + 2; // 2 ~ n까지 난수 생성
int rn2 = rand() % (n-1) + 2;
if(rn1 == rn2) continue;
int t = dt[rn1];
dt[rn1] = dt[rn2];
dt[rn2] = t;//무작위로 데이터 순서 변경 후
imin = 0;
for(j=2;j<=n;j++) {
imin += arr[dt[j-1]][dt[j]];
}
imin += arr[dt[n]][1];
if(imin < min) {//현재 경로 비용합을 구하여 최적값 갱신
min = imin;
continue;
}
t = dt[rn1];//최적값이 아닐 경우 원상복구
dt[rn1] = dt[rn2];
dt[rn2] = t;
}그냥 단순하게 무작위로 순서를 바꾸고 최적값을 갱신하는 작업이다.
이제 이 방법의 맹점을 생각해보자
이런 식으로 진행 된다고 했을 때 각각 2번 바꾼 경우, 4번 바꾼 경우에 최소값이 발생하고
4번바꾼 최소값이 2번 바꾼 최소값보다 더 나은 값이라고 가정해보자.
지역 탐색으로 문제를 해결하는 것이 가능할까?
2번째 최소값이 min변수에 들어간 이후로는 어떠한 갱신도 이루어지지 않을 것이다.
이러한 경우, 2번째 최소값을 지역 최적점이라고 부르는데 여기에서 나오기 위한 대안을 생각해야한다.
Simulated Annealing::담금질 기법
담금질 기법은 지역탐색과 비슷하지만 최적값이 아닌 경우에도 그 값을 버리지 않고 저장한다. (물론 저장된 최적값은 따로 보관한다)
srand(time(0));
min = 0;
dt[1] = 1;
for(i=2;i<=n;i++) {
min += arr[i-1][i];
dt[i] = i;
}
min += arr[n][1];//기본값 저장
best = min;
for(i=1;i<=1000000;i++) {//1000000은 프로그램 실행시켜보고 제한 시간에 맞도록 변경
int rn1 = rand() % (n-1) + 2; // 2 ~ n까지 난수 생성
int rn2 = rand() % (n-1) + 2;
if(rn1 == rn2) continue;
int t = dt[rn1];
dt[rn1] = dt[rn2];
dt[rn2] = t;//무작위로 데이터 순서 변경 후
imin = 0;
for(j=2;j<=n;j++) {
imin += arr[dt[j-1]][dt[j]];
}
imin += arr[dt[n]][1];
min = imin;//항상 갱신
if(imin < best) {
best = imin;//best변수에는 최적값 저장
}
}
이런 방법으로 지역 최적점을 벗어 날 수 있다. 물론 이 방법은 지역 최저점을 찾는데에도 사이클을 많이 소모하므로
실제 코딩에선 일정 확률로 벗어날 수 있도록 하는것이 좋다.
srand(time(0));
min = 0;
dt[1] = 1;
for(i=2;i<=n;i++) {
min += arr[i-1][i];
dt[i] = i;
}
min += arr[n][1];//기본값 저장
for(i=1;i<=1000000;i++) {//1000000은 프로그램 실행시켜보고 제한 시간에 맞도록 변경
int rn1 = rand() % (n-1) + 2; // 2 ~ n까지 난수 생성
int rn2 = rand() % (n-1) + 2;
if(rn1 == rn2) continue;
int t = dt[rn1];
dt[rn1] = dt[rn2];
dt[rn2] = t;//무작위로 데이터 순서 변경 후
imin = 0;
for(j=2;j<=n;j++) {
imin += arr[dt[j-1]][dt[j]];
}
imin += arr[dt[n]][1];
if(imin < min) {//현재 경로 비용합을 구하여 최적값 갱신
min = imin;
continue;
}
else {
int rn3 = rand % 100;
if(rn3 < 7) {
min = imin;
continue;
}//7퍼센트 확률로 현재값이 최적값이 아니어도 저장
}
t = dt[rn1];//최적값이 아닐 경우 원상복구
dt[rn1] = dt[rn2];
dt[rn2] = t;
}후... 어쩌면... 인생에서 현재에 만족하지말고 더 나은 것을 누리기 위해서는 현재 누리는 것을 포기해야한다는 깊은 교훈이 들어있는 인생같은 알고리즘이 아닐까...