부분 집합의 합 문제에 이어, 또 다른 $NP$-$complete$ 대표 문제 중 하나인 외판원 순회 문제 문제를 간소화하여 풀어보자. 문제는 다음과 같다.

• $1, 2, ... , N$의 번호가 고유하게 매겨진 $N$개의 정점으로 구성된 그래프가 인접 행렬 형태로 주어진다.
• 임의의 한 정점에서 시작해, 나머지 $N-1$개의 정점을 모두 방문한 후 처음 시작한 정점으로 돌아오는 경로가 있을 수 있다.
• 정점 $i$에서 정점 $j$로 이동 시 $G_{ij}$의 비용이 발생할 때, 최소 비용으로 모든 정점을 순회하는 경우를 찾아 보아라.

첫째 줄에 정점의 개수 $N$이 주어진다. $(1 ≤ N ≤ 18)$

둘째 줄부터 $N$개의 줄에 걸쳐 그래프의 연결 상태가 $N \times N$ 크기의 인접 행렬 형태로 주어진다. $(1 ≤ G_{ij} ≤ 10,000; G_{ii} = 0)$

$G_{ij} = 0$라면 $i$에서 $j$로 향하는 간선이 존재하지 않는다는 의미이다.