8. 23

• 
• 가입 5달만에 랭크 100위권 달성!-_-v
• tsp solving.pdf
• tsp solving2.pdf
• Applied Mathematical Programming by Bradley, Hax, and Magnanti (Addison-Wesley, 1977) link
• 두려운 마음에 미뤄뒀던 TSP를 해결했다. N<=15까지 잘 돌아가는데 N<=20에서 자꾸 시간초과도 아닌 '오답'이 뜨길래 뭐가 문젠지 찾느라 한참을 고생했다. 그런데 Reverse Prunning을 꺼보니까 정답처리가 떴고 해당 함수 부분에 오류가 있었음을 알 수 있었다-_- 여기에 DP적용하고 MST에 대해서도 캐시를 적용하니까 수행시간이 1/10수준으로 줄어들었다. 알고스팟 TSP문제는 모든 간선이 존재하므로 크루스칼(ElogE)보단 프림(V²+E)을 적절히 최적화해서 휴리스틱을 구성하니 속도가 더 빨리 나왔던 것 같다. TSP3문제 가장 빠른 답안 달성! Integer Programming으로 만든 해법도 한 번 짜보고 싶다.