# 한국의 81,998개 술집을 둘러보는 최단 도보 경로

> Clean Markdown view of GeekNews topic #20517. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=20517](https://news.hada.io/topic?id=20517)
- GeekNews Markdown: [https://news.hada.io/topic/20517.md](https://news.hada.io/topic/20517.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2025-04-25T09:43:24+09:00
- Updated: 2025-04-25T09:43:24+09:00
- Original source: [math.uwaterloo.ca](https://www.math.uwaterloo.ca/tsp/korea/index.html)
- Points: 2
- Comments: 2

## Topic Body

- **여행하는 세일즈맨 문제(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** 라이브러리를 사용하여 연구를 수행하였음  
- **한국 경찰청**의 데이터베이스를 통해 한국 바의 위치를 확보하였음

## Comments



### Comment 37785

- Author: xguru
- Created: 2025-04-25T09:46:44+09:00
- Points: 1

[한국의 81,998개 술집을 모두 돌아보는 최단 도보 경로는 178일](https://news.hada.io/topic?id=20484) 글을 해커뉴스에 긱뉴스 계정으로 올렸는데요.  
투표를 많이받아서 6시간동안 탑을 차지하더니 인기 글이 되어서 다시 GN+로 수입(?)되었네요.  
  
해당 글이 영문도 같이 있어서 그렇게 해본건데, 종종 영문 포함 글들은 해커뉴스쪽으로 올려보려고 합니다.

### Comment 37783

- Author: neo
- Created: 2025-04-25T09:43:24+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=43778105) 
* 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 솔버를 블랙박스로 본다면 근본적으로 매우 간단하지만 매우 유용함
* 새로운 바가 몇 개 열리고 몇 개는 닫힌 것 같음
  - 다시 계산할 시간임