왜 "다 따져보면" 안 되나요? 출발점을 정한 뒤 나머지 지점의 순서를 모두 나열하면 (n−1)! 가지, 순환 경로는 방향이 같으므로 그 절반입니다.

최적해 (동적 계획법, Held-Karp) — "어느 지점들을 거쳐 지금 여기 있나"만 기억하면 같은 상황을 두 번 계산하지 않아도 됩니다. 계산량이 2ⁿ·n² 로 줄어 15개 지점이면 수백만 번 계산으로 끝나지만, 30개면 다시 불가능해집니다.

최근접 이웃 — 지금 있는 곳에서 가장 가까운 미방문 지점으로 갑니다. 순식간에 끝나지만 마지막에 멀리 떨어진 곳이 남아 크게 돌아오는 함정이 있습니다. 2-opt — 경로에서 서로 교차하는 두 변을 골라 풀어 다시 잇기를 반복합니다. 교차가 없어질 때까지 다듬으면 최근접 이웃의 결과가 보통 5~15% 짧아집니다.

직선 거리의 한계 — 강·산·일방통행은 모릅니다. 실제 도로 거리로 바꾸려면 길찾기 API(카카오모빌리티·OSRM 등)로 지점 사이 거리 행렬을 받아 같은 알고리즘에 넣으면 됩니다.