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