| [ QuizWit ] in KIDS 글 쓴 이(By): Convex (4ever 0~) 날 짜 (Date): 1999년 6월 9일 수요일 오전 01시 10분 47초 제 목(Title): Re: [질문] 어느 가난한 가수가.... Approx. Alg. 쓰는 방법은 뭐 시중에 책 보면 다 나오는데. 전제조건이 유클리디언 디스턴스 상이나 삼각혀으이 부등식 조건을 만족하는 경우라면 근사 알고리즘을 쓸 수 있죠. 그러할 경우 근사(어프록시메이션) 알고리즘은 최적해(옵티멀 솔루션) 에서 몇% 벗어나는 해라던지.. 상수 몇배에 해당하는 근사해를 구할 수 있다던지 하는 것이겠죠. Minimum Spanning Tree 를 쓰면 2배 이내로 구할 수 있고, Christofides 의 휴리스틱 알고리즘을 쓰면 1.5배 이내로 구할 수 있습니다. 이게 굉장히 유명한 예이고... 92년도에 Bentley 라는 사람의 방법을 쓰면 근사해보다 약간 더 높은 값으로 구할 수 있음. 그리고 숙제는 가급적이면 혼자힘으로 풀게 합시다. --,--`-<@ 매일 그대와 아침햇살 받으며 매일 그대와 눈을 뜨고파.. 잠이 들고파.. Till the rivers flow up stream | Love is real \|||/ @@@ Till lovers cease to dream | Love is touch @|~j~|@ @^j^@ Till then, I'm yours, be mine | Love is free | ~ | @@ ~ @@ |