Travelling Salesman Problem (여행하는 세일즈맨 문제)

Travelling Salesman Problem (여행하는 세일즈맨 문제)

이 문제는 내가 군대를 갔다가 대학교에 복학한 후에 거의 처음 참석한, 콜로퀴움 세미나에서 들은 주제이다. 그것이 아마도 1994년일 것이다. 그로부터 지금이 2012년이니까, 대충 18년전이다. 20년 가까이 되었다.

알고리즘 책을 봤다. 거기에 거의 처음으로 나오는 문제가 이것이다.
언뜻 보기에는 너무나도 쉬워 보이는 문제가 정말로 풀기에는 너무나도 어려운 문제이다. 이런 문제들이 무척 많은데, 그 중에서 가장 널리 알려진 것에 해당한다.

(1)
일단, 풀이를 위해 모든 경우의 수를 검토하는 것은 너무나도 방대한 시간이 걸리므로, 사실상 불가능하다.
그래서, 가장 쉬워 보이는 방법인,

(2)
일단 가장 짧게 가는 경로를 차례로 선택하기
이것은 무척 그럴듯하지만, 알고리즘 책에서는 이것이 좋은 해답이 아니라고, 보여주고 있다. 그 이유는,  실제로 적용하려고 하면, 불만족스러운 결과를 내는 경우를 쉽게 만날 수 있다. 그런 경우를 알고리즘 책에서는 몇개를 보여준다.
그리고, 그 경우는 너무 흔하게 만날 수 있는 경우라는 것을 알게된다. 그리고, 불만족스러운 결과는 너무나도 어이없는 이상한 동작을 보여주게 된다.
 따라서, 이런 경우를 몇개 보고 나면, 이 방법을 쓰고 싶은 생각은 전혀 없어지게 된다.

(3)
앞의 (2)번 방법을 조금 변형 시킨 방법
(2)의 방법을 유지하고 단지, 시작점을 잘 선택하면 될 것 같아 보인다. 하지만, 알고리즘 책을 쓴 사람은 어떤 다른 경우에, 이 방법으로 만든 경로가 아닌, 이 방법 말고 더 좋은 경로를 보여준다.

그래서, 쉬워 보이는 풀이들은 모두 제외되고, 본격적으로 어려운 방법들을 소개하기 시작한다.


왜 이런 어려운 문제를 봐야하는가?
이것은, 여행자가 여행 계획을 세우는데에만 필요한 것이 아니며, 특히 공장 자동화 (Factory Automation) 또는 생산 자동화 (Automated Production)에서 너무나도 빈번히 만나게 되는 문제이기 때문이다. 실제로 자동화 설비를 만들려면, 이것을 만족스럽게 해결할 방안이 있어야 오늘 당장 필요한 제품을 만들 수 있는 종류의 작업이 너무나도 많기 때문이다.

참고 목록

가장 본격적으로 이 문제를 다루고 있는 곳.
http://www.tsp.gatech.edu/

한국에서 인공지능을 공부하고 있는 학생의 개인 사이트 자료
http://www.aistudy.com/problem/traveling_salesman_problem.htm

구글 검색
구글 검색 : travelling salesman problem

영어 위키피디아
http://en.wikipedia.org/wiki/Travelling_salesman_problem

한국어 위키피디아
http://ko.wikipedia.org/wiki/외판원_문제

mathematica로 유명한 wolfram의 수학세상 자료
http://mathworld.wolfram.com/TravelingSalesmanProblem.html

이것을 주제로 영화가 만들어지고 있는 모양이다.
http://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film)

내가 보고 있는 알고리즘 책
http://www.algorist.com/


한국에서는 좀 더 전문적인 수학/전산 단체(대학교 포함) 혹은 전문인의 자료가 없는 것이 아쉽다.
http://blog.naver.com/the2384/10106444843


위에서 영화가 만들어지고 있다고 했던 위키피디아에 있는 공식 영화 제작사(또는 판매사) 사이트이다.
http://www.travellingsalesmanmovie.com/
여기에 이 영화에 나온 수학인 "P=NP 인가?" 라는 문제는 무슨 문제인가에 대한 설명이 있다.
무척 좋은 설명이라서, 불안정하게 계속 변하고 사라지는 웹에 놔두기에는 너무 아까운 내용의 글이라서 복사해서 떠왔다. 나중에 번역좀 해 봐야겠다.

P vs. NP
THE MATH BEHIND THE FILM

The P vs. NP problem is the most notorious unsolved problem in computer science. First introduced in 1971, it asks whether one class of problems (NP) is more difficult than another class (P).

Mathematicians group problems into classes based on how long they take to be solved and verified. "NP" is the class of problems whose answer can be verified in a reasonable amount of time. Some NP problems can also be solved quickly. Those problems are said to be in "P", which stands for polynomial time. However, there are other problems in NP which have never been solved in polynomial time.

The question is, is it possible to solve all NP problems as quickly as P problems? To date, no one knows for sure. Some NP questions seem harder than P questions, but they may not be.

Currently, many NP problems take a long time to solve. As such, certain problems like logistics scheduling and protein structure prediction are very difficult. Likewise, many cryptosystems, which are used to secure the world's data, rely on the assumption that they cannot be solved in polynomial time.

If someone were to show that NP problems were not difficult?that P and NP problems were the same?it would would have significant practical consequences. Advances in bioinformatics and theoretical chemistry could be made. Much of modern cryptography would be rendered inert. Financial systems would be exposed, leaving the entire Western economy vulnerable.

Proving that P = NP would have enormous ramifications that would be equally enlightening, devastating, and valuable...

Press

'Travelling Salesman' movie considers the repercussions if P equals NP
by Duncan Geere, Wired
"Mathematical puzzles don't often get to star in feature films, but P vs NP is the subject of an upcoming thriller"


Travelling Salesman, Thriller Set In a World Where P=NP
Slashdot
"A movie that features science and technology is always welcome, but is it not often we have one that focuses on computer science. Travelling Salesman is just such a rare movie."


Travelling Salesman - A Movie About P=NP
by Alex Armstrong, I-Programmer
"We all know that the P=NP question is truly fascinating, but now it is about to be released as a movie."

ACME Science Podcast
Strongly Connected Components #46, ACME Science
"I speak with Timothy about where he got the idea for the movie, how he made sure that the mathematics was correct, and why science movies just may be the new comic book movies."


The Travelling Salesman's Power
by Kenneth W. Regan, Godel’s Lost Letter
"At last someone is taking the position that P = NP is a possibility seriously. If nothing else, the film's brain trust realize that being equal is the cool direction, the direction with the most excitement, the most worthy of a major motion picture."


Podcast: Rolling out the red carpet for the Travelling Salesman
by Rachel Thomas, Plus Magazine
"Travelling Salesman is an unusual movie: despite almost every character being a mathematician there's not a mad person in sight."