TravelingSalesmanProblem

n개의 도시가 있고, 각 도시간의 거리가 있을 때, 모든도시를 거치는 가장 짧은 경로를 푸는 문제. also more formally called directed HamiltonianPathProblem.

n이 증가함에 따라 ComputationalComplexity가 급격히 증가하는 대표적인 [[NP]]-complete Problem이다. BigOhNotation으로 TimeComplexity를 표현하면 '''O(C^n^)'''

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||