| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2001년 2월 12일 월요일 오후 04시 25분 35초 제 목(Title): Re: TSP 1번: 가장 간단한 approximation algorithm입니다. 이 아이디어를 조금 더 고친 버젼이 알고리즘 책 여기저기에 나와있습니다. 2번: " 모든 vertex를 지나는 폐곡선이 유지되나를 본다"는 게 쉽지 않죠? 또, 가장 긴 edge를 사용해야 하는 TSP는 쉽게 만들 수 있습니다. . . . . 식으로 반원의 한쪽 원주상에 있는 점들을 가지고 TSP를 만들어보세요. >최소의 TSP path는 도중에 edge끼리 교차하는 일이 없어야 할 것 같은데 맞는지요? 예. metric space 상에서의 TSP의 특징입니다. -- 박.. |