d라이브러리

미국을 여행하는 야구팬들을 위해 랍 프래트 SAS 연구원이 외판원 문제를 응용하여 30개 야구장 경기 관람 동선을 최적화했습니다. 조사 결과 24.8일 동안 약 4989km를 이동하는 경로가 최적이었으며 이는 실제 야구 팬들이 이미 실행했던 일정보다 짧게 나왔습니다.

외판원 문제(TSP)는 여러 도시를 최소 비용으로 한 번씩 방문하는 경로 찾기 문제입니다. 해밀턴이 제안한 퍼즐에서 비롯된 TSP는 계산 복잡성으로 유명합니다. 랜드연구소는 외판원 문제를 풀기 위해 분기한정법을 사용해 답의 범위를 줄였고 이를 통해 계산 시간을 단축하였습니다

외판원 문제는 모든 도시를 한 번씩 방문하며 최소 비용의 이동경로를 찾는 NP-완전 문제로, 효율적인 해결 알고리즘의 존재 여부가 미지수다. 수학자들은 근사 알고리즘 연구를 통해, 방향에 상관없는 이동의 경우 정답의 1.5배 이내, 방향이 다른 이동의 경우 5500배 이내의