5246 : A47 - 휴리스틱: 2-opt 로컬 서치
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
2차원 평면 위에 $N$개의 도시가 있으며, 1부터 $N$까지 번호가 붙어 있습니다.
도시 $i$는 좌표 $(X_i, Y_i)$에 위치하며, 두 도시 사이의 거리는 유클리드 거리 $\sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2}$입니다.
도시 1에서 출발하여 모든 도시를 한 번씩 방문하고 다시 도시 1로 돌아오는 경로를 구하려 합니다.
탐욕법(Nearest Neighbor)으로 생성된 초기 경로에 대해, 경로의 두 구간을 뒤집어 전체 거리를 단축시키는 2-opt 국소 탐색(Local Search) 기법을 적용하여 교차 간선을 개선한 최적화 경로를 구하세요.
단, 2-opt 교환은 더 이상 거리가 단축되지 않을 때까지 반복 적용합니다.
[제약 조건]
• $2 \le N \le 10$
• $N$ 는 정수
도시 $i$는 좌표 $(X_i, Y_i)$에 위치하며, 두 도시 사이의 거리는 유클리드 거리 $\sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2}$입니다.
도시 1에서 출발하여 모든 도시를 한 번씩 방문하고 다시 도시 1로 돌아오는 경로를 구하려 합니다.
탐욕법(Nearest Neighbor)으로 생성된 초기 경로에 대해, 경로의 두 구간을 뒤집어 전체 거리를 단축시키는 2-opt 국소 탐색(Local Search) 기법을 적용하여 교차 간선을 개선한 최적화 경로를 구하세요.
단, 2-opt 교환은 더 이상 거리가 단축되지 않을 때까지 반복 적용합니다.
[제약 조건]
• $2 \le N \le 10$
• $N$ 는 정수
입력 설명
첫째 줄에 정수 $N$이 주어집니다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 도시의 좌표 $X_i, Y_i$가 공백으로 구분되어 주어집니다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 도시의 좌표 $X_i, Y_i$가 공백으로 구분되어 주어집니다.
출력 설명
방문하는 도시의 번호를 순서대로 $N+1$개 줄에 걸쳐 출력하세요. (첫 번째와 마지막 도시는 반드시 1이어야 합니다)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7
1 1
4 1
2 5
3 4
3 2
4 2
5 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
2
6
7
3
4
5
1