여행하는 세일즈 맨 문제1

 

지난번에 암호문 해독하는 방법에 대해서 썼는데요 이게 여행하는 세일즈맨 문제 푸는 것이랑 매우 흡사합니다. 그래서 쓴 김에 여행하는 세일즈 맨 문제를 MCMC로 어떻게 푸는지 이야기 하겠습니다.

 

정확하게 푸는 방법은 다음에 적고 이번에는 간단하게 암호문 해독과 어떻게 비슷한지만 이야기하겠습니다.

 

여향하는 세일즈 맨 문제는 다음과 같습니다. 어떤 세일즈 맨인 유럽 50개 도시를 돌아 다녀야 합니다. 그래서 문제는 어떤 경로를 택하여야 가장 거리가 짧은지 가장 짧은 경로를 찾는 것이 문제입니다.

 

앞에서도 여러번 이야기했지만 인간의 논리로는 매우 간단합니다.

 

1) 모든 가능한 여행 경로를 쓴다.

 

2) 각 경로의 거리를 잰다

 

3) 각 경로의 거리에서 가장 짧은 경로를 찾는다.

 

이렇게 세 줄이면 간단하게 풀리는 문제입니다.

 

 

그러나 50개 도시를 돌아다니는 경로는 무지하게 많습니다. 더구나 이 경로가 100개 도시, 1000개 도시, 10000개 도시 이렇게 커지면 최근의 가장 좋은 컴퓨터로도 계산하기 그리 쉽지 않습니다.

 

      

이런 문제는 지난번 암호 해독 문제에서 암호 해독 하는 디코딩 함수가 무지하게 많다는 사실과 매우 흡사한 경우입니다.

 

그래서 암호 해독하는 문제를 풀는 것과 똑같이 하면 됩니다.

 

1) 먼저 특정 여행 경로 f1을 생각합니다. 그 다음 이 여행 경로 f1과 매우 유사한 주변(Neighborhood) N(f1)를 생각합니다. 이 주변에서 다른 경로 g1을 뽑아 f1과 거리를 비교합니다.

 

2) 새로 뽑은 경로 g1의 거리가 f1보다 짧으면 이젠 g1을 선택하고 또 이 g1의 주변 N(g1)에서 다시 새로운 경로 h1을 뽑아 다시 거리를 비교합니다.

 

 

3) 새로 뽑은 경로 g1이 f1보다 길어도 일정 확률 p를 가지고 g1을 선택합니다. 따라서 f1이 g1보다 거리가 짧아도 항상 f1을 유지하는 것이 아니라 오로지 (1-p)의 확률로 f1을 유지합니다. f1이 계속 유지되면 다시 N(f1)에서 새로운 경로 g2을 뽑아 f1과 g2의 거리를 비교하여 위의 방식을 계속 합니다.

 

 

그래서 암호 푸는 문제가 똑같은데 문제는 어떤 경로 f1의 주변 N(f1)어떻게 정의하는가가 문제가 됩니다. 이것도 암호 푸는 문제랑 똑같습니다. 여행 경로의 두 도시만 바꾸는 경로만을 생각하시면 됩니다.

 

 

예를 들어 도시가 6개만 있다고 하죠. 도시를 A, B, C, D, E, F라 하죠. 세일즈 맨인 출발 도시가 A라고 하면 경로의 마지막도 A 도시가 되어야 합니다.

 

그럼 다음과 같은 여행 경로를 생각해보죠

 

f1: (A==>C==>D==>B==>F==>E==>A)

 

이 여행경로의 주변은 다음과 같은 경로들이 됩니다.

 

g1: (A==>D==>C==>B==>F==>E==>A)

g2: (A==>B==>D==>C==>F==>E==>A)

g3: (A==>C==>B==>D==>F==>E==>A)

...

 

등 f1의 주변 경로도 상당히 많습니다. 하여간 f1의 주변

 

N(f1)={g1, g2, g3,.....}

 

라도 하면 여기서 랜덤하게 하나의 경로를 뽑아 f1과 비교해서 위의 알고리즘에 따라 문제를 풀어가면 됩니다.

 

 

자세한 내용은 앞의 글에서 소개한

 

Aarts & Korst의 “Simulated Annealing and Boltzmann Machines"

 

이 두 사람은 유명한 네덜란드 회사인 필립스 연구소 연구원입니다. 이 책의 원고가 1988년에 써진 것이네요. 일개 기업 연구소에서 이런 수준 높은 연구 책이 오랜 적부터 나왔다는 것이 놀랍죠.

 

 

요새 많이 쓰는 R 이라는 프로그램도 아주 옛날에 Bell 연구소에서 공짜로 만든 프로그램입니다. 제가 공부하러 갔을 때 Unix workstation에 공짜로 다 깔려 있었습니다.

 

 

한국도 이젠 대학이나 기업 둘 다 정치꾼들 제발 좀 몰아내었으면 합니다.