한국의 81,998개 술집을 둘러보는 최단 도보 경로
(math.uwaterloo.ca)- 여행하는 세일즈맨 문제(TSP) 는 81,998개의 한국 바를 방문하는 최단 경로를 찾는 문제로, **Open Source Routing Machine (OSRM)**을 사용하여 해결됨
- 이 경로는 178일 이상 소요되는 최적의 경로로, OSRM의 계산을 통해 증명됨
- LKH 코드와 Concorde 코드를 사용하여 cutting-plane method를 적용, 대규모 TSP 문제 해결
- 수학적 최적화와 운영 연구는 자원 효율성을 높이기 위한 도구 개발에 중점
- 연구는 Roskilde University와 University of Waterloo에서 수행되었으며, IBM CPLEX Optimizer와 Leaflet 라이브러리 사용
한국의 81,998개 바를 방문하는 최단 경로
- 여행하는 세일즈맨 문제(TSP) 는 81,998개의 한국 바를 방문하는 최단 경로를 찾는 문제로, Open Source Routing Machine (OSRM) 을 사용하여 해결되었음
- 이 경로는 178일 이상 소요되는 최적의 경로로, OSRM의 계산을 통해 증명되었음
- LKH 코드와 Concorde 코드를 사용하여 cutting-plane method를 적용, 대규모 TSP 문제를 해결하였음
대규모 TSP 문제 해결
- 수학적 최적화와 운영 연구는 자원 효율성을 높이기 위한 도구 개발에 중점을 두고 있음
- 연구는 Roskilde University와 University of Waterloo에서 수행되었으며, IBM CPLEX Optimizer와 Leaflet 라이브러리를 사용하였음
연구팀 및 감사
- 연구팀은 William Cook, Daniel Espinoza, Marcos Goycoolea, Keld Helsgaun으로 구성됨
- IBM의 CPLEX Optimizer와 Leaflet 라이브러리를 사용하여 연구를 수행하였음
- 한국 경찰청의 데이터베이스를 통해 한국 바의 위치를 확보하였음
한국의 81,998개 술집을 모두 돌아보는 최단 도보 경로는 178일 글을 해커뉴스에 긱뉴스 계정으로 올렸는데요.
투표를 많이받아서 6시간동안 탑을 차지하더니 인기 글이 되어서 다시 GN+로 수입(?)되었네요.
해당 글이 영문도 같이 있어서 그렇게 해본건데, 종종 영문 포함 글들은 해커뉴스쪽으로 올려보려고 합니다.
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 솔버를 블랙박스로 본다면 근본적으로 매우 간단하지만 매우 유용함
- 새로운 바가 몇 개 열리고 몇 개는 닫힌 것 같음
- 다시 계산할 시간임