전산학에서 어려운 NP-complete 문제의 일종으로 아주 유명한 "Travelling Salesman 문제"를 brute-force한 방법으로 푸는 걸 시각적으로 보여주는 프로그램입니다.
이 문제의 목표는 정점이 여러 개 있을 때, 각 정점들을 한 번씩만 모두 지나가는 최단거리를 구하는 것입니다. 언뜻 쉬운 문제 같지만, 모든 경우를 고려해서 "가장" 짧은 거리를 구하려면 정점 개수의 팩토리얼 가지의 경우를 고려해야 하기 때문에 정점이 열 개만 넘어가도 계산량이 폭발적으로 많아집니다. 이 프로그램을 돌려 보면서, 시간 복잡도가 지수함수인 문제의 위력를 실감해 보십시오.
Ctrl+N을 누르면 점을 초기화하고, +나 -를 누르면 정점 개수를 4개에서 25개까지 조절할 수 있습니다. 정점은 무작위한 위치에 생성되나, 마우스로 끌어서 위치를 바꿀 수도 있습니다.
F5를 누르면 계산을 시작합니다. 최단거리는 발견될 때마다 실시간으로 고쳐집니다. 진행 상황은 제목 표시줄에 나타나고요. 점 개수가 10~12개일 때가 가장 봐 줄 만 하고, 13개 이상은 무리입니다.
멀티스레드, 비재귀적으로 순열 생성하기와 같은 테크닉이 쓰였으니, 소스를 분석해 보시면 관심 있는 분들에게 도움이 될 것입니다.