| [ QuizWit ] in KIDS 글 쓴 이(By): outsider (하얀까마귀) 날 짜 (Date): 2001년 2월 12일 월요일 오후 03시 15분 47초 제 목(Title): TSP 밤에 잠이 잘 안 와서, 세일즈맨 문제를 떠올리고 이런저런 당치않은 상상을 하기 시작했습니다. 직관적으로 떠오르는 솔루션 두가지: 1) n개의 TSP path를 구성하고 있는 점들이 이미 있을 때, n+1개째의 점을 추가하려면, 새로 추가하는 점을 A라 할 때, 기존의 edge들 하나하나에 대해서 edge의 양 끝 B, C를 B-C로 이어져 있는 것을 B-A-C로 바꿔줘본다. 모든 edge에 대해 다 시도해 보고 제일 짧은 것을 택한다. 잘되면 삼각형부터 시작해서 쉽게 path를 구성할 수 있지 않을까? 2) n개의 모든 vertex에 대해 각각을 잇는 edge들을 일단 모두 그린다. n(n-1)/2 개. 길이가 긴 것부터 짧은것까지 죽 정렬한 다음에 긴것부터 하나씩 제거해가면서, 이걸 제거해도 모든 vertex를 지나는 폐곡선이 유지되나를 본다. 폐곡선이 깨진다면 그냥 그대로 냅두고, 안 깨지면 제거해버리고 다음 엣지를 또 검사한다. 이런식으로 모든 엣지를 슥슥. 근데 곧바로 떠오르는 자연스러운 다음 생각: 이따위로 쉽게 풀리는 문제라면 (1,2번 모두 polynomial time에 풀리는 알고리즘이니..) TSP가 발표된 그 자리에서 -_- 나왔을 테니 틀림없이 반례가 있을텐데... 반례 찾기 시작. 1번을 찾고, 2번을 찾다가 성공적으로 잠들었습니다. ^^; 각각에 대해 (가능한한 간단한) 어떤 반례가 있을까요? p.s. 2번을 생각하다가 나온건데, 최소의 TSP path는 도중에 edge끼리 교차하는 일이 없어야 할 것 같은데 맞는지요? -- @< //) `//<_ 하얀까마귀 |