Hacker News 의견

• 1.33억 개의 별을 포함한 TSP 솔루션이 인상적임
  • 해당 투어는 최단 경로의 1.0038배 길이임
  • Bell Labs의 확률적 알고리즘을 사용하면 결과가 얼마나 나빠질지 궁금함
• 고전적인 TSP 접근 방식 설명
  • 모든 노드를 임의의 경로로 연결함
  • 경로를 두 곳에서 잘라 세 부분으로 만듦
  • 세 부분을 여섯 가지 가능한 방법으로 재배열하고 가장 짧은 것을 선택함
  • 개선이 없을 때까지 2-3단계를 반복함
  • 최적의 결과를 보장하지는 않지만 대부분의 실제 문제에서 최적이거나 매우 근접함
• 총 거리를 언급하지 않는 것이 이상함
  • 이동 시간을 해결하는 것이 목적이지만 실제 이동 거리를 아는 것도 흥미로울 것임
  • 칼로리 소모를 계산하거나 최단 거리 경로에서 얼마나 벗어났는지 확인할 수 있음
• 오하이오 크기의 나라에 거의 8만 2천 개의 바가 있다는 생각에 압도됨
• COVID 기간 동안 CityStrides를 사용하여 마을의 모든 거리를 걷는 목표를 세움
  • 걸은 거리를 추적하고 마을의 몇 퍼센트를 걸었는지 알려줌
  • 경로를 최적화하지는 않았지만 중복 없이 최대한 많은 거리를 걷는 것이 재미있는 정신적 퍼즐이었음
  • 자동화 도구도 재미있을 수 있지만 수작업으로 하는 것이 여정의 일부였음
  • CityStrides 사이트를 탐색하면서 사람들의 LifeMaps를 볼 수 있음
  • 어떤 사람들은 놀라운 양의 걷기를 함
• 60년대 아일랜드 군대에서 물어보던 질문이 생각남
  • "Bachelor's Walk에서 Collins Barracks까지 바를 지나지 않고 가는 방법은?"
  • 답은 "모든 바에 들어가는 것"이었음
• 이 데이터셋을 찾은 것이 인상적이지만 더 어렵지는 않음
  • 마지막 여행 판매원 최고 기록을 깨는 것과 계산을 끝내지 못하는 것 사이의 미묘한 균형임
• NP가 다시 P처럼 보임
  • 학교에서 13이 최대라고 배웠고, 80년대에 교수님이 15로 발전시킴
  • 그 후 20, 20,000, 이번에는 80,000이 증명됨
  • World TSP 페이지에서 기록이 1백만임
  • 현재 가장 큰 증명된 최적값은 3,178,031임
  • CUDA로 해야지 일반 C로 하면 안 됨
• Branch-and-bound는 "책에서 나온" 알고리즘임
  • LP 솔버를 블랙박스로 본다면 근본적으로 매우 간단하지만 매우 유용함
• 새로운 바가 몇 개 열리고 몇 개는 닫힌 것 같음
  • 다시 계산할 시간임