Travelling salesman problem

The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

Solution of a travelling salesman problem

TSP is a special case of the travelling purchaser problem and the vehicle routing problem.

In the theory of computational complexity, the decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class ofNP-complete problems. Thus, it is possible that the worst-case running time for any algorithm for the TSP increases superpolynomially (perhaps, specifically, exponentially) with the number of cities.

The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact algorithms are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of 1%.^[1]

The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources will want to minimise the time spent moving the telescope between the sources. In many applications, additional constraints such as limited resources or time windows may be imposed.

출처: https://en.wikipedia.org/wiki/Travelling_salesman_problem

다양한 풀이법이 존재하는 여행하는 외판원 문제입니다. 우선 완전 탐색 방법과 동적 계획법으로 풀어보겠습니다. heuristics 이나 integer programing 방법은 아직 제가 이해하기에는 어려운 면이 있어 나중에 업데이트를 해야되겠습니다.

우선 완전 탐색 방법은 설명할 것도 없이 재귀함수를 통해 모든 경로를 탐색하여 최소값을 구하는 방법입니다.

동적 계획법은 memoization 을 통해 이미 값을 구한 경로는 반복해서 값을 구하지 않고 건너뛰는 방법입니다. 이미 들린 도시의 값을 전달하기 위해 bit mask 방법을 사용해 memoization 이 가능하도록 하였습니다.

c++

#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
 
 
const int MAX_CITY = 20;
 
int numCity;
double distances[MAX_CITY][MAX_CITY];
 
#pragma region dynamic programming
double cache[MAX_CITY][1 << MAX_CITY];
#pragma endregion
 
#pragma region bruteForce
double bruteForce(vector<int>& visitedCity, vector<bool>& isVisited, double curLength)
{
    if (visitedCity.size() == numCity)
        return curLength + distances[visitedCity.back()][visitedCity[0]];
 
    double ret = 987654321;
 
    for (int next = 0; next < numCity; next++)
    {
        if (isVisited[next])
            continue;
        
        int here = visitedCity.back();
        visitedCity.push_back(next);
        isVisited[next] = true;
 
        double length = bruteForce(visitedCity, isVisited, curLength + distances[here][next]);
        ret = min(ret, length);
 
        isVisited[next] = false;
        visitedCity.pop_back();
    }
 
    return ret;
}
#pragma endregion
 
 
#pragma region dynamic programming
double dynamicProgramming(int here, int visitedCity)
{
    if (visitedCity == (1 << numCity) - 1)
        return distances[here][0];
 
    double& ret = cache[here][visitedCity];
 
    if (ret >= 0)
        return ret;
 
    ret = 987654321;
 
    for (int next = 0; next < numCity; next++)
    {
        if (visitedCity & (1 << next))
            continue;
 
        double length = dynamicProgramming(next, visitedCity + (1 << next)) + distances[here][next];
 
        ret = min(ret, length);
    }
 
    return ret;
}
#pragma endregion
 
int main() 
{
    //10 cities
    ifstream fin("input.in");
 
    fin >> numCity;
 
    memset(distances, 0, sizeof(distances));
 
    for (int i = 0; i < numCity; i++)
    {
        for (int j = i + 1; j < numCity; j++)
        {
            
            double dist1;
            fin >> dist1;
            distances[i][j] = distances[j][i] = dist1;
        }
    }
    
#pragma region bruteForce
    vector<int> visitedCity;
    visitedCity.push_back(0);
    vector<bool> isVisited(numCity, false);
    isVisited[0] = true;
 
    clock_t start = clock();
    cout << "bruteForce : " <<  bruteForce(visitedCity, isVisited, 0);
 
    clock_t end = clock();
    double time = double(end - start) / CLOCKS_PER_SEC;
    cout << " elapse time(s): " << time << endl;
#pragma endregion
 
 
#pragma region dynamic programming
    memset(cache, -1, sizeof(cache));
 
    start = clock();
    cout << "dynamicProgramming : " << dynamicProgramming(0, 0);
 
    end = clock();
    time = double(end - start) / CLOCKS_PER_SEC;
    cout << " elapse time(s): " << time << endl;
#pragma endregion
 
    system("pause");
    return 0;
}

bruteForce : 108 elapse time(s): 13.941

dynamicProgramming : 108 elapse time(s): 0.005