[Algorithm Strategies] 04. Exhaustive Search - Traveling Sale

1. Exhaustive Search

1.1 Traveling Sale - Optimization Problem

1.1.1 Problem

- 어떤 나라에 n개의 큰 도시, 각 도시들은 모두 직선 도로로 연결

   - 한 영업 사원이 한 도시에서 출발해 다른 도시들을 전부 한번 씩 방문한 뒤 시작 도시로 돌아오려고 함

     - 이때 모든 경로 중 가장 짧은 경로로 찾는 방법

1.1.2 Algorithm Strategy

- 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환

double Exhaustive::shortestPath(vector<int>& path, vector<bool>& visited, double currentLength);

   - 모든 도시를 방문하는 방법 중 가장 거리가 짧은 위치를 찾아 값을 반환

1.1.3 implementation

- 모든 도시들을 방문했을 경우 거리를 반환하고 함수 종료

if (path.size() == n) return currentLength + dist[path[0]][path.back()];

   - 무한대의 값을 설정한 후 n개의 도시들을 돌면서 가장 짧은 거리를 계산

     - 가장 짧은 거리가 나올 경우 그 값을 반환하여 도시를 모두 방문하면서 가장 짧은 거리를 구할 수 있음

double ret = numeric_limits<double>::max();
for (int next = 0; next = n; next++)
{
    if (visited[next]) continue;
    int here = path.back(); path.push_back(next); visited[next] = true;
    double cand = shortestPath(path, visited, currentLength + dist[here][next]);
    ret = min(ret, cand); visited[next] = false; path.pop_back();
}
return ret;