BioHackersNetn개의 도시가 있고, 각 도시간의 거리가 있을 때, 모든도시를 거치는 가장 짧은 경로를 푸는 문제. also more formally called directed HamiltonianPathProblem.
n이 증가함에 따라 ComputationalComplexity가 급격히 증가하는 대표적인 NP-complete Problem이다. BigOhNotation으로 TimeComplexity를 표현하면 O(Cn)
MetropolisAlgorithm 페이지에 보면, TSP문제를 푸는 JavaApplet 프로그램을 볼수 있다.
예제프로그램 TspSolver.py으로 도시개수에 따른 수행시간비교 (IBM p690 1CPU, Permutation이용)
Numer of cities |
Path |
Distance |
Time(sec) |
0 |
. |
0 |
2.28881835938e-05 |
1 |
0 |
0 |
3.2901763916e-05 |
2 |
0, 1 |
0.672324796349 |
0.000115871429443 |
3 |
1, 0, 2 |
0.945174301694 |
0.000323057174683 |
4 |
1, 3, 0, 2 |
1.01731284864 |
0.0015242099762 |
5 |
0, 1, 2, 3, 4 |
1.55294601167 |
0.00891494750977 |
6 |
1, 4, 5, 0, 3, 2 |
2.02538077212 |
0.0609500408173 |
7 |
3, 0, 6, 1, 2, 4, 5 |
1.63212360019 |
0.482034921646 |
8 |
0, 5, 6, 2, 7, 1, 4, 3 |
2.10825713515 |
4.30308294296 |
9 |
5, 4, 6, 8, 7, 0, 1, 3, 2 |
2.24051225861 |
42.6521940231 |
10 |
5, 4, 2, 6, 9, 1, 7, 3, 0, 8 |
2.49560470526 |
465.248432875 |
11 |
3, 8, 9, 1, 4, 10, 5, 7, 2, 0, 6 |
3.08470515919 |
5576.83088613 |
12 |
7, 5, 4, 3, 6, 9, 2, 1, 11, 0, 8, 10 |
2.27237596408 |
71951.927316 |