Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 최근접 이웃 알고리즘으로 순회 판매원 문제(TSP) 구현하기

순회 판매원 문제(Traveling Salesman Problem, TSP)는 여러 도시를 각각 한 번씩 모두 방문한 뒤 출발 도시로 되돌아올 때, 총 이동 비용이 최소가 되는 경로를 찾는 고전적인 조합 최적화 문제입니다. 이 글에서는 탐욕(Greedy) 기법 중 하나인 최근접 이웃(Nearest Neighbour) 알고리즘을 이용해 TSP를 구현하는 C++ 프로그램을 살펴봅니다.

최근접 이웃 알고리즘의 동작 원리

최근접 이웃 알고리즘은 이름 그대로 매 단계마다 현재 도시에서 가장 가까운 미방문 도시를 골라 이동하는 방식으로 동작합니다. 전체 절차는 다음과 같습니다.

  1. 출발 도시를 하나 정하고 방문 처리한다.
  2. 현재 도시에서 아직 방문하지 않은 도시 중 이동 비용이 가장 작은 도시를 찾는다.
  3. 그 도시로 이동하며 총비용에 해당 비용을 더하고 방문 처리한다.
  4. 모든 도시를 방문할 때까지 위 과정을 반복한다.
  5. 마지막 도시에서 출발 도시로 돌아오는 비용을 더해 경로를 완성한다.

C++ 예제 코드

다음 예제는 4개 도시와 도시 간 이동 비용 행렬을 입력으로 사용하여, 최근접 이웃 알고리즘으로 최소 비용 경로를 계산합니다.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    // 도시 간 이동 비용(거리) 행렬
    vector<vector<int>> graph = {
        { 0, 10, 15, 20 },
        {10,  0, 35, 25 },
        {15, 35,  0, 30 },
        {20, 25, 30,  0 }
    };
    int n = graph.size();

    vector<bool> visited(n, false);
    vector<int> path;

    int current = 0;              // 출발 도시
    visited[current] = true;
    path.push_back(current);
    int totalCost = 0;

    // 매 단계에서 가장 가까운 미방문 도시를 선택
    for (int step = 1; step < n; step++) {
        int nearest = -1;
        int minDist = INT_MAX;
        for (int next = 0; next < n; next++) {
            if (!visited[next] && graph[current][next] < minDist) {
                minDist = graph[current][next];
                nearest = next;
            }
        }
        visited[nearest] = true;
        path.push_back(nearest);
        totalCost += minDist;
        current = nearest;
    }

    // 마지막으로 출발 도시로 복귀하는 비용 추가
    totalCost += graph[current][path.front()];
    path.push_back(path.front());

    cout << "방문 경로: ";
    for (size_t i = 0; i < path.size(); i++) {
        cout << path[i];
        if (i + 1 < path.size()) cout << " -> ";
    }
    cout << endl;
    cout << "최소 비용: " << totalCost << endl;
    return 0;
}

실행 결과

방문 경로: 0 -> 1 -> 3 -> 2 -> 0
최소 비용: 80

프로그램은 도시 0에서 출발해 1 → 3 → 2 순서로 이동한 뒤 다시 도시 0으로 돌아오는 경로를 선택하며, 이때 총 이동 비용은 80이 됩니다.

시간 복잡도와 알고리즘의 특징

  • 시간 복잡도: 각 단계마다 모든 미방문 도시와의 거리를 비교하므로 전체 수행 시간은 O(n²)입니다.
  • 공간 복잡도: 방문 여부 배열과 경로 저장에 O(n)의 메모리를 사용합니다.
  • 근사 해법: 빠르게 그럴듯한 해를 구할 수 있지만 항상 최적해를 보장하지는 않으며, 시작 도시에 따라 결과 경로와 비용이 달라질 수 있습니다.
  • 활용: 도시 수가 많아 완전 탐색(O(n!))이 현실적으로 불가능한 경우, 초기 해를 빠르게 얻는 휴리스틱으로 널리 활용됩니다.

정리하면, 최근접 이웃 알고리즘은 구현이 간단하고 속도가 빨라 대규모 TSP 인스턴스에 유용한 1차 접근 방법입니다. 다만 더 나은 품질의 해가 필요하다면 2-opt, 담금질 기법(simulated annealing) 등의 개선 기법과 함께 사용하는 것이 좋습니다.