로컬 탐색 알고리즘, 완전한 혼동

Question

(a)와 (b)에서 2 교환 변환 연산자를 가정하면 경로 표현의 TSP 둘러보기 인 솔루션 A와 B를 둘러보기 C, D, E, F, G

(a) A: 1 2 3 4 5 6 7 

C: 1 3 5 7 2 4 6 
D: 1 2 5 4 3 6 7 
E: 2 3 1 7 5 4 6 
F: 4 1 7 5 3 2 6 
G: 1 2 3 7 6 5 4 

(b) B: 1 3 2 7 5 4 6 

C: 1 3 5 7 2 4 6 
D: 1 2 5 4 3 6 7 
E: 2 3 1 7 5 4 6 
F: 4 1 7 5 3 2 6 
G: 1 2 3 7 6 5 4 

나는 이것이 무엇을 요구하고 있는지 전혀 모른다.

Answer 1

정의 이 (문제 텍스트에서 추론, 어쩌면 당신이 너무 수업이 논의) 경로 표현에
TSP 투어 :
 는 숫자 1 (7)을 통해의 순서를 정렬, 각 숫자가 한 번 인용 한 번만.
  각 숫자는 여행사 직원이 방문한 도시를 나타냅니다. 예를 들어 D를 들어
  : 1 2 5 4 3 6 7는, 그것의 개념을 소개하는이 시점에서 아마 유용 판매원 도시 1에서 시작하는 것이, 시티 2로 이동, 표시 후
  도시 5 ... 도시 7
에 종료 '중지'라고 표기하고 소문자로 표기하십시오. 자, trhu g. (문제의 다양한 경로를 식별하는 데 사용되는 대문자와 전혀 관계가 없음). D 형 경로
에서, 정지 도시 1, C 정지시 5 등이다

2 교류 변환 연산자
  정확히 두 도시 교환하여 TSP로 변환 동작 (또는, 더 정확하게, 두 개의 정거장을 위해 도시를 바꾸는 것).
따라서 2 교환 변환 연산은 경로 X, 두 개의 중지 인덱스 m, n의 세 가지 인수를 취하는 작업으로 이해할 수 있으며 m 및 n의 도시가 스왑 된 경로 X '를 반환합니다. 우리가) (이 작업의 스위프를 호출 할 경우
, 우리는 쓸 수

Swp(A, c, e) = 1 2 5 4 3 6 7 

할당 (당신의 임무, 당신은 ;-) 그것을 받아 들일 것) TSP이다
연결 솔루션 A와 B를, D, E, F, G
C, D, EF 및 G (대문자 즉 경로) 중에서 식별하는 것이 요구됩니다. A (또는 B)의 "이웃"경로, 즉 이들 중 어느 것이 단일 Swp() 연산으로 A (또는 B)에서 파생 될 수 있는지 아마도 상기 동작 파라미터를 제공하기 위해). 하나는 최소한에, 하나는 스위프의 (안 여러 가지가있을 수 있으므로) 목록() 다른 경로 A에서 갈 필요가 작업을 찾을 필요가 하나로 할당을 해석 할 수 나아가

단계 수.