Traveling Salesman Problem

FrontPage|FindPage|TitleIndex|RecentChanges| UserPreferences P RSS
Extracted from TuringMachine.

NP class에 해당하는 문제의 예) "어떤 graph에서 length가 k보다 작은 hamiltonian cycle이 있는가?"
전산학에서 NP 문제의 또다른 유명한 예가 바로 TSP(Traveling Salesman Problem)이다.

세일즈맨이 n 개의 도시를 방문하려한다. 그런데 각각의 두 도시 사이의 거리가 일정하지 않다. 세일즈맨이 모든 도시를 한번씩 들르며 n 개의 도시를 순회하고자 할 때, 최단 경로를 찾는 효율적인 알고리즘이 존재하는가? 여기서 효율적이란 말은 polynominal time(다항시간 : n의 다항식 order의 시간)에 계산될 수 있다는 것이다. 모든 도시 간의 거리가 주어져 있으므로, 결국 문제가 되는 것은 최단 총거리 값을 search하는 방법이다.

가장 쉽게 생각할 수 있는 방법은 n개의 도시를 배열할 수 있는 모든 경우의 수에 대하여 search를 실행하는 것이다. 이 방법은 너무나 무식한 방법으로 n!개의 순열을 모두 search해야한다. 따라서 이 경우 exponential time이 걸린다. 즉, n이 커지면 탐색 시간은 e^n order로 커진다는 것이다.

그런데 문제는 비록 TSP의 해답을 구하는데 걸리는 시간은 지수시간이지만, 임의의 답이 최적해인지를 검증하는데 걸리는 시간은 다항시간이라는 데 있다. 그렇기 때문에 최적해를 구하는 다항시간의 알고리즘도 존재하는 게 아닐까 기대하게 되는 게 사람 심리. ..이러한 문제를 미정다항시간문제(NP = nondeterministic problem)이라고 한다. 과연 NP=P인가? 즉, 위에서 말한 저런 타입의 문제(NP)가 우리가 몰라서 그렇지 사실은 다항시간문제(p)가 아닐까 하는 의문이 풀리지 않았다는 것이다. 현재도 많은 수학자들이 매달려있는 이 문제를 풀면 Clay 수학연구소로부터 100만 달러의 상금을 탈 수 있다.

엄밀하게 이야기하면, TSP의 답을 구하는 것도 NP, TSP의 답이 맞는지 검증하는 것도 NP입니다. 최적화(optimization) 문제와 결정 문제를 같은 선 상에서 이야기하면 안 됩니다.

실제로 GeneticAlgorithm을 이용해 학부생 수준에서 n=1000인 경우 TSP를 풀어보았는데 팬티엄2 450MHz에서 한시간 이상의 시간이 걸렸다는... 실제로 얼마나 도움이 되는지는 잘 모르겠네요.-_-;; --오티움

GA를 이용한 TSP의 성공이 바로 얼마전에 문병로교수님의 연구실에서 있었다고 들었습니다. --naya
How do you define a success?
그게 아마 이전보다 좋은 알고리즘을 발견했다는 걸겁니다. TSP를 polynorminal time에 풀었다는 건 모든 NP에 대해 NP=P 를 증명했다는 이야기랑 같은 건데, 제가 알기로는 아직 100만 달러를 먹은 사람이 없거든요^^;;--오티움
네 마자요.. 제가 쪼끔 애매하게 말했는데요.. 죄송. 다만 GA가 그렇게 의미도 없는 알고리즘이라고 생각될 만큼 아무거나가 아니란 말이 하고 싶었을뿐인데 와전되버렸습니다.. 죄송.. --naya


"; if (isset($options[timer])) print $menu.$banner."
".$options[timer]->Write()."
"; else print $menu.$banner."
".$timer; ?> # # ?>