배송 순서 개선: 열린 경로와 2-opt

창고에서 출발해 모든 배송지를 한 번씩 방문하되, 마지막 배송지에서 창고로 돌아오지는 않습니다. 이 열린 경로를 짧게 만드는 과정을 통해 초기해, 지역 탐색, 차분 평가를 함께 배웁니다.

배열과 반복문을 알면 따라갈 수 있습니다. 그림과 데모는 로그인 없이 볼 수 있고, 글 마지막에는 일반 C++17 환경에서 실행할 완성 파일도 있습니다.

문제 계약을 상태로 옮기기

미니 물품 배송에서 구현할 함수는 다음과 같습니다.

코드 환경: h-contest 제출용. 공개 API 선언과 설명 조각을 먼저 읽고, 아래 ‘제출 가능한 기본 구현’을 user.cpp에 넣습니다.

extern int get_dist(int a, int b);
extern int get_path_dist(const int order[], int size);

void build_path(int n, const int points[][2], int order[]);

build_path는 값을 반환하지 않습니다. 최종 방문 순서를 order[0]부터 order[n - 1]까지 직접 써 넣어야 합니다.

항목	계약
상태	`0`부터 `n - 1`까지 정확히 한 번씩 들어간 순열 `order[]`
시작점	`order[0] = 0`인 창고 고정
거리	`get_dist(a, b)`가 주는 맨해튼 거리
목적 함수	인접한 두 위치 사이 거리의 합을 최소화
끝점	마지막 배송지에서 창고로 돌아오지 않는 열린 경로
보조 함수	`get_path_dist(order, size)`로 부분 또는 전체 경로 거리 확인
잘못된 답	중복, 누락, 범위 밖 번호, `order[0] != 0`이면 큰 패널티

테스트의 n은 4, 8, 12, 16, 20, 36, 52, 68, 84, 100입니다. 가장 큰 경우에는 모든 순열을 볼 수 없으므로, 작은 경우의 exact 탐색과 큰 경우의 휴리스틱을 분리해 생각할 수 있습니다.

점수식을 먼저 정확히 쓴다

이 문제의 점수는 다음과 같습니다.

cost(order) =
    dist(order[0], order[1])
  + dist(order[1], order[2])
  + ...
  + dist(order[n - 2], order[n - 1])

TSP 순회와 달리 아래 항은 없습니다.

dist(order[n - 1], order[0])

이 차이는 초기해와 개선 연산에 모두 영향을 줍니다. 마지막 위치는 창고 근처로 돌아올 필요가 없고, 경로 끝을 포함하는 구간을 뒤집을 때는 오른쪽 바깥 간선도 존재하지 않습니다.

0단계: 유효한 기준선

가장 단순한 기준선은 번호 순서입니다.

for (int i = 0; i < n; ++i) {
    order[i] = i;
}

이 순열의 비용을 기록해 두고 다음 초기해와 비교합니다.

1단계: nearest neighbor 초기해

첫 번째 실전 초기해는 현재 위치에서 가장 가까운 미방문 배송지를 고르는 nearest neighbor입니다.

order[0] = 0
used[0] = true

for pos = 1 .. n - 1:
    current = order[pos - 1]
    current에서 가장 가까운 미방문 cand를 찾는다
    order[pos] = cand
    used[cand] = true

시간 복잡도는 O(n^2)이고 n <= 100에서는 충분히 빠릅니다. 매 단계의 선택만 보면 자연스럽지만, 가까운 점을 먼저 소비해 마지막에 멀리 떨어진 점 하나가 남을 수 있으므로 이것만으로 끝내지는 않습니다.

동점 처리도 하나의 파라미터입니다. 같은 거리라면 번호가 작은 점, 다음 후보가 많은 점, 현재 배송지 밀집 구역 안쪽의 점을 고르는 방식이 서로 다른 초기해를 만듭니다.

2단계: 열린 경로의 2-opt 차분

2-opt는 order[left..right] 구간을 뒤집는 연산입니다. 창고를 고정해야 하므로 left >= 1인 구간만 고릅니다.

대칭 거리에서는 구간 내부 간선의 방향만 반대로 바뀌고 비용은 같습니다. 따라서 모든 경로를 다시 더하지 않고 경계 간선만 비교할 수 있습니다.

a = order[left - 1]
b = order[left]
c = order[right]

before = dist(a, b)
after  = dist(a, c)

right + 1 < n이면 오른쪽 경계도 더합니다.

d = order[right + 1]

before += dist(c, d)
after  += dist(b, d)

after < before이면 구간을 뒤집습니다. right == n - 1일 때는 오른쪽 경계 간선이 없으므로 첫 비교만 해야 합니다. TSP용 2-opt 공식을 그대로 복사해 마지막 위치와 창고 사이의 가짜 복귀 간선을 넣으면 다른 문제를 최적화하게 됩니다.

작은 경로를 손으로 따라가기

다음처럼 x축 위에 다섯 위치가 있다고 하겠습니다.

0 = 0, A = 1, B = 9, C = 8, D = 2

현재 경로가 0 -> A -> B -> C -> D이면 비용은 다음과 같습니다.

1 + 8 + 1 + 6 = 16

꼬리 구간 B -> C -> D를 뒤집으면 0 -> A -> D -> C -> B가 됩니다.

1 + 1 + 6 + 1 = 9

이때 내부 간선 B-C, C-D는 방향만 바뀌므로 총비용이 같습니다. 실제 변화는 A-B가 A-D로 바뀐 것뿐입니다. 열린 경로의 끝을 뒤집을 때 경계 하나만 비교하는 이유가 여기서 보입니다.

같은 x축 위에서 꼬리 B-C-D를 뒤집으면 방문 순서가 0-A-D-C-B가 됩니다. 내부 거리는 그대로이고 A에서 꼬리로 이어지는 거리만 8에서 1로 줄어 총비용이 16에서 9가 됩니다.

그림 크게 보기

위아래 그림의 점은 같은 x좌표에 고정되어 있습니다. 곡선 화살표는 방문 순서를 나타내며, 비용은 곡선 길이가 아니라 두 점의 x좌표 차이입니다. 초록색 내부 간선은 방향만 바뀌어 비용 1 + 6이 그대로이고, 주황색 경계 간선의 비용만 8 → 1로 바뀝니다.

작은 입력에서 모든 left, right 조합을 뒤집어 보고, 차분식의 결과가 get_path_dist로 다시 구한 비용 변화와 같은지 대조합니다. 인접한 두 점과 경로 끝을 포함하는 구간도 넣습니다.

열린 경로 2-opt: 구간과 경계 비용 비교하기

뒤집을 구간을 바꾸며 전후 경로와 경계 간선의 차분을 비교해 보세요. 맨해튼 거리를 사용하며 시작점 0은 고정합니다. 끝점을 포함하는 구간에서는 오른쪽 경계를 더하지 않습니다. 더 좋아지지 않는 후보도 직접 확인할 수 있습니다.

제출 가능한 기본 구현

아래 코드는 nearest neighbor로 초기해를 만든 뒤, 더 좋아지는 2-opt만 반복합니다. STL이나 C 헤더 없이 고정 배열과 helper 함수만 사용합니다.

extern int get_dist(int a, int b);
extern int get_path_dist(const int order[], int size);

static void reverse_range(int order[], int left, int right) {
    while (left < right) {
        int temp = order[left];
        order[left] = order[right];
        order[right] = temp;
        ++left;
        --right;
    }
}

void build_path(int n, const int points[][2], int order[]) {
    int used[100];
    (void)points;

    for (int i = 0; i < n; ++i) {
        used[i] = 0;
    }

    order[0] = 0;
    used[0] = 1;

    for (int pos = 1; pos < n; ++pos) {
        int current = order[pos - 1];
        int best = -1;
        int best_dist = 0;

        for (int cand = 0; cand < n; ++cand) {
            if (used[cand]) continue;

            int dist = get_dist(current, cand);
            if (best == -1 || dist < best_dist) {
                best = cand;
                best_dist = dist;
            }
        }

        order[pos] = best;
        used[best] = 1;
    }

    for (int pass = 0; pass < 80; ++pass) {
        int improved = 0;

        for (int left = 1; left < n - 1; ++left) {
            for (int right = left + 1; right < n; ++right) {
                int a = order[left - 1];
                int b = order[left];
                int c = order[right];
                int before = get_dist(a, b);
                int after = get_dist(a, c);

                if (right + 1 < n) {
                    int d = order[right + 1];
                    before += get_dist(c, d);
                    after += get_dist(b, d);
                }

                if (after < before) {
                    reverse_range(order, left, right);
                    improved = 1;
                }
            }
        }

        if (!improved) break;
    }
}

구간 뒤집기는 순열의 원소를 추가하거나 지우지 않으므로 유효성을 자동으로 보존합니다. left가 1 이상이므로 창고도 항상 첫 위치에 남습니다.

2-opt 다음 개선 연산

2-opt가 멈췄다고 해서 좋은 경로를 모두 본 것은 아닙니다. 서로 다른 모양의 이웃을 추가하면 다른 지역 최적으로 이동할 수 있습니다.

연산	변화	주의할 경계
insertion	한 위치를 빼서 다른 두 위치 사이에 삽입	index 이동 뒤 위치 보정, 경로 끝
swap	두 배송지의 순서를 교환	두 위치가 인접할 때 겹치는 간선
double bridge	떨어진 여러 구간의 연결을 크게 변경	작은 `n`에서는 변화가 지나치게 큼
perturb + 2-opt	몇 번 무작위로 흔든 뒤 다시 2-opt	현재 best와 작업용 current 분리

insertion은 2-opt로 만들기 어려운 변화를 한 번에 만들 수 있습니다. 이때도 이동 전후에 달라지는 주변 간선만 계산하면 후보 하나를 O(1)에 평가할 수 있습니다. 다만 시작점 0은 이동 대상에서 제외해야 합니다.

나쁜 이동을 잠시 허용하려면 current와 best를 분리합니다. current는 흔들 수 있지만, 제출할 best는 실제 get_path_dist가 더 짧을 때만 교체하면 안전합니다.

초기해를 여러 개 만드는 법

nearest neighbor가 만드는 경로는 첫 몇 번의 선택에 크게 좌우됩니다. order[0] = 0은 고정이지만 두 번째 배송지는 여러 후보를 시도할 수 있습니다.

창고에서 가까운 후보 K개를 고른다
각 후보를 두 번째 위치로 고정한다
나머지는 nearest neighbor로 채운다
각 완성 경로에 2-opt를 적용한다
get_path_dist로 가장 짧은 경로를 남긴다

n <= 100이면 K를 작게 둔 multi-start도 충분히 가볍습니다. 완전히 무작위인 시작만 반복하는 것보다, 서로 다른 두 번째 배송지를 강제하면 탐색한 초기해의 차이가 분명해집니다.

작은 입력은 exact 탐색으로 쓴다

n = 4이면 창고를 제외한 순열은 3! = 6개이고, n = 8이어도 7! = 5040개입니다. 이 두 경우는 모든 순열을 직접 확인할 수 있습니다.

작은 입력의 exact 탐색은 두 가지 역할을 합니다.

앞 테스트 케이스의 점수를 실제 최적으로 만든다.
nearest neighbor와 2-opt가 최적해에서 얼마나 떨어지는지 확인하는 oracle이 된다.

n = 12부터는 11!이라 같은 방식이 급격히 비싸집니다.

내 컴퓨터에서 실행하기

완성 C++17 예제 내려받기. 위 제출 코드를 보존하고, 맨해튼 거리 함수와 입력·출력용 main을 덧붙였습니다. 파일 전체는 로컬 실행용입니다. h-contest에 제출할 때는 위 build_path와 보조 함수 부분을 사용합니다.

입력은 점의 개수 N과 N개의 (x, y) 좌표입니다. 1 <= N <= 100, 좌표는 0..999로 제한합니다. 첫 점이 창고이며 점 번호는 입력 순서대로 0부터 붙습니다. 출력 첫 줄은 비용, 둘째 줄은 방문 순서입니다.

c++ -std=c++17 -O2 ordering-two-opt.cpp -o ordering-two-opt
./ordering-two-opt < points.txt

points.txt에 그림의 다섯 점을 넣습니다.

9
0 1 4 3 2

이 출력은 nearest neighbor로 초기해를 만든 뒤 2-opt를 적용한 최종 결과입니다. 번호 순서의 비용 16에서 시작해 구간을 하나씩 뒤집는 과정은 위 데모에서 확인할 수 있습니다.

다음 강의에서는 차분식이 맞는지, 경로 전체를 다시 더하는 독립 계산으로 검증합니다.