| [ QuizWit ] in KIDS 글 쓴 이(By): Zaharang ( 자하랑) 날 짜 (Date): 2001년 2월 13일 화요일 오후 06시 49분 00초 제 목(Title): Re: TSP 수학적으로도 그렇게 simple하게 표현합니다. 워낙 간단한 문제라 별다른 표현이 없는데? Given the positions of N cities, what is the shortest closed tour in which each city can be visited once? 굳이 formulation하자면... Given a set of n nodes and the coordinates of each node, find a round trip of minimum total length visiting each node exactly once. The distance from node i to node j is the same as from node j to node i (Symmetric TSP). 음. 이거 가지고 학부때 죽어라고 branch-bound 알고리즘 만들어서 남들 노드 16~17개에 만족할때 무식하게 어레이에 다 올려서 20개까지 돌리다가 당시의 Sun3기계를 과감하게 날려먹던 기억이 새록새록 나는군요. 논문주제도 이거 비스므레한 건데 왜 기억이 하나도 안날까. 너무 많이 연구된 거라서 알고리즘도 수십종, 휴러스틱도 수백종... 아래 사이트가 거의 bible 수준. http://www.ing.unlp.edu.ar/cetad/mos/TSPBIB_home.html |