외판원 문제

도시들과 도시 사이의 거리가 주어질 때 모든 도시를 한 번씩 거쳐 출발점으로 돌아오는 가장 짧은 순회를 찾는 문제다. 「길이가 k 이하인 순회가 있는가」로 묻는 결정 문제 판은 NP-완전이고, 가장 짧은 순회를 찾는 최적화 판은 NP-난해다. 도시가 n 개면 순회는 (n−1)!/2 가지다. 거리가 삼각 부등식을 따르면 최적의 1.5배 이내를 보장하는 근사 알고리즘이 있고, 실전에서는 도시 수만 개짜리 사례의 최적해도 구해져 있다.