휴리스틱 검증: 차분 계산과 스트레스 테스트

앞 강의에서 만든 경로가 짧아졌더라도 계산이 맞는지는 별도로 확인해야 합니다. 이번에는 같은 배송 경로를 두 가지 방법으로 평가해 오류를 찾고, 실패를 작은 입력으로 남기는 방법을 배웁니다.

빠른 풀이가 맞는지 확인하려면 다른 방법으로 계산한 기준 답이 필요합니다. 작은 입력에서는 완전탐색을 돌릴 수 있습니다. 같은 함수를 이름만 바꾸어 두 번 호출하면 비교 결과가 같아도 아무것도 검증하지 못합니다.

최적 비용과 비교할 수 있는 경우

TSP 완전탐색과 DP는 작은 입력에서 같은 최적 비용을 내야 합니다. 정점 수를 작게 잡고 두 구현에 같은 비용 행렬을 넣습니다. 경로 자체는 최적해가 여러 개일 수 있으므로 비용과 방문 조건을 비교합니다.

ORDERING은 창고 0이 고정된 열린 경로입니다. n = 4면 나머지 세 배송지의 순서 6개만 확인하면 됩니다. 휴리스틱이 그 최적 비용과 다르다고 곧바로 버그인 것은 아닙니다. 유효한 답인지와 최적해에서 얼마나 떨어졌는지를 구분해서 기록합니다.

ORDERING의 차분 계산을 검증하기

열린 경로 2-opt는 뒤집는 구간의 경계 간선만 비교합니다. 이 계산에는 전체 경로를 더하는 get_path_dist라는 별도의 기준이 있습니다.

1. 유효한 order[]를 복사해 두고 전체 비용 before를 구합니다.
2. 모든 1 <= left < right < n에서 경계 간선의 비용 변화 delta를 계산합니다.
3. 해당 구간을 실제로 뒤집고 전체 비용 after를 다시 구합니다. after - before == delta여야 합니다.
4. 같은 구간을 다시 뒤집어 배열과 비용이 원래대로 돌아오는지 확인합니다.

인접한 두 위치, 마지막 배송지를 포함한 구간, 거리 0인 서로 다른 점을 포함합니다. 특히 right == n - 1일 때는 복귀 간선이 없습니다. 순열의 중복·누락과 order[0] == 0도 함께 확인하면 비용 계산과 상태 변경을 나누어 추적할 수 있습니다.

잘못된 차분식이 드러나는 입력

x축 좌표가 0=0, A=1, B=9, C=8, D=2이고 순서가 0,A,B,C,D라면 꼬리 B,C,D를 뒤집어 봅니다. 전체 비용은 16 → 9라서 차분은 −7이어야 합니다. 열린 경로 그림과 같은 입력입니다.

그런데 사이클 공식을 잘못 가져오면 없는 복귀 간선까지 계산합니다. 제거 비용은 A-B + D-0 = 8+2=10, 추가 비용은 A-D + B-0 = 1+9=10이어서 잘못된 차분 0이 나옵니다. 이 한 입력으로 차분식과 전체 재계산의 불일치를 재현할 수 있습니다. 실제 뒤집기 뒤 다시 뒤집었을 때는 원래 순열과 비용 16이 돌아와야 합니다.

비교할 두 계산을 분리하기

경계식의 정답을 다른 경계식으로 확인하면 같은 실수를 공유할 수 있습니다. 기준 계산은 처음부터 끝까지 모든 인접 거리를 더해야 합니다. 복구 검사에서는 비용뿐 아니라 순열 자체가 원본과 같은지도 봅니다.

무작위 입력에서 실패를 재현하기

작은 입력을 여러 개 생성해 같은 비교를 반복합니다. 공통 난수 코드의 seed를 고정하면 실패한 실행을 다시 만들 수 있습니다. 입력 생성용 seed와 풀이 내부의 탐색 seed는 따로 기록합니다.

불일치를 찾으면 seed만 남기지 말고 실제 입력, 이동 구간, 예상값과 실제값도 저장합니다. 원소를 줄여도 실패가 남는지 확인하면 경계 하나가 빠진 경우인지, 차분식 자체가 틀린지 찾기 쉽습니다. 줄이는 동안에도 원래 문제의 입력 조건은 유지해야 합니다.

점수와 시간 비교

차분과 유효성 검사를 통과한 뒤 동일한 TC·탐색 예산에서 초기해, 2-opt, 새 연산을 비교합니다. 평균뿐 아니라 어떤 TC가 나빠졌는지도 봅니다. 튜닝에 쓰지 않은 입력을 따로 남겨 특정 seed에만 맞춘 변경을 구분합니다.

최대 입력의 시간 측정에는 초기화, 입력 처리, 점수 재계산, 최종 답 생성도 포함합니다. 스트레스 반복문과 검증용 출력은 로컬 하네스에 두고 제출 함수에는 넣지 않습니다.

실행 가능한 스트레스 테스트

검증 프로그램 내려받기는 일반 C++17 환경에서 실행하는 독립 예제입니다. 서버 로그인이나 문제 채점기가 필요하지 않습니다.

c++ -std=c++17 -O1 -g -fsanitize=address,undefined \
  -fno-sanitize-recover=all ordering-stress.cpp -o ordering-stress
./ordering-stress

프로그램은 다음 순서로 검사합니다.

1. 그림의 꼬리 뒤집기에서 실제 차분이 -7인지, 잘못된 사이클 공식이 0을 내는지 확인합니다.
2. 고정 seed 20261004로 1,000개의 작은 좌표·순열을 만듭니다.
3. 모든 유효한 구간에 대해 경계 차분과 전체 재계산을 비교합니다.
4. 이동 후 시작점·방문 조건과 두 번 뒤집은 뒤의 원상 복구를 검사합니다.

PASS: fixed tail counterexample and 1000 seeded cases

불일치가 나면 좌표, 원래 순열, 구간, 기대 차분과 계산 차분을 표준 오류로 출력하고 실패로 종료합니다. seed는 입력을 다시 만드는 단서이고, 실제 입력은 난수 생성 코드를 바꾼 뒤에도 남는 재현 자료입니다. 이 검사는 차분과 상태 변경의 일관성을 확인하며, 최적 경로를 찾는다는 보장은 하지 않습니다.