Traveling salesman problem(TSP)은 외판원 순회라 해서 도시가 n개 존재할 때, 특정 도시에서 다른 도시로 이동할 때 드는 distance value(d)가 주어지게 되고, 어떠한 도시에서부터 나머지 다른 모든 도시들을 돌고 다시 출발한 도시로 돌아왔을 때 드는 최소한의 d값을 구하는 문제이다. 이 문제는 모든 도시를 단 한번씩만 방문할 수 있으며, dynamic programming을 사용해서 subproblem을 통해서 구할 수 있다. Dynamic programming을 사용하지 않으면 모든 경우의 수를 전부 따져야 하기 때문에 시간 복잡도가 굉장히 오래 걸린다. 가령 3개의 도시만 하더라도 3!의 경우가 존재하기 때문에 O(n!)이다. 도시 수가 적으면 큰 상관이 없겠지만, 도시 수가 많아지면 많아질수록 이 시간 복잡도는 허용되지 않는 범위가 될 것이다. 그래서 dynamic programming을 적용해서 문제를 간단하게 만들 것이다.
부분 문제로 어떠한 것을 이용해야 하는 것일까? 최소 거리는 계속해서 더해지게 된다. 도시가 많아지면 전체적인 순서는 달라지더라도 특정 부분은 겹치는 부분이 많을 것이다. 가령 5개의 도시만 생각해보자. 12345 순서로 갈 수도 있지만, 21345 순서로 갈 수도 있다. 이때, 345 순서는 중복되기 때문에 매번 계산을 하지 않고 미리 계산해 놓은 결과를 사용하자는 것이다.
위의 C(S,j)에서 S는 이미 방문한 도시들에 대한 정보이고, j는 첫 도시부터 이동하고나서 도착한 가장 최근 도시에 대한 정보이다. 그래서 우리는 만약 중간에 i 도시에서 j 도시로 넘어갈 때, 우리는 이전의 최소 거리의 합과 이제 이동할 거리를 합할 생각이다. Code는 다음과 같다.
