3-옵션

최적화에서, 3-opt는 여행 판매원 문제와 관련된 네트워크 최적화 문제를 해결하기 위한 단순한 로컬 검색 알고리즘이다.단순한 2-opt 알고리즘에 비해 속도는 느리지만 고품질 솔루션을 생성할 수 있다.

3-opt 분석은 네트워크(또는 둘러보기)에서 3개의 연결(또는 가장자리)을 삭제하여 3개의 하위 인터페이스를 생성하는 것을 포함한다.그런 다음 최적의 네트워크를 다시 연결하는 7가지 다른 방법을 분석한다.이 프로세스는 다른 세트의 3개 연결에 대해 네트워크에서 가능한 모든 조합을 시도할 때까지 반복된다.3-opt의 단일 실행은 $O(n^{3})$ $O(n^{3})$ ) ${\displaystyle O(n^{3})$ 의 시간 복잡성을 가지고 있으며 $O(n^{3})$ ^[1] 반복된 3-opt는 시간 복잡성이 더 높다.

이것은 3옵션 스왑이 주어진 경로를 조작하는 메커니즘이다.

반항하다 reverse_reverse_if_reversible(관광을 하다, i, j, k):     """역투어가 투어를 짧게 할 수 있다면 그렇게 하라."""     # 주어진 여행 [...A-B...C-D...E-F...]     A, B, C, D, E, F = 관광을 하다[i-1], 관광을 하다[i], 관광을 하다[j-1], 관광을 하다[j], 관광을 하다[k-1], 관광을 하다[k % 렌(관광을 하다)]     d0 = 거리를 두다(A, B) + 거리를 두다(C, D) + 거리를 두다(E, F)     d1 = 거리를 두다(A, C) + 거리를 두다(B, D) + 거리를 두다(E, F)     d2 = 거리를 두다(A, B) + 거리를 두다(C, E) + 거리를 두다(D, F)     d3 = 거리를 두다(A, D) + 거리를 두다(E, B) + 거리를 두다(C, F)     d4 = 거리를 두다(F, B) + 거리를 두다(C, D) + 거리를 두다(E, A)      만일 d0 > d1:         관광을 하다[i:j] = 뒤바뀐(관광을 하다[i:j])         돌아오다 -d0 + d1     엘리프 d0 > d2:         관광을 하다[j:k] = 뒤바뀐(관광을 하다[j:k])         돌아오다 -d0 + d2     엘리프 d0 > d4:         관광을 하다[i:k] = 뒤바뀐(관광을 하다[i:k])         돌아오다 -d0 + d4     엘리프 d0 > d3:         tmp = 관광을 하다[j:k] + 관광을 하다[i:j]         관광을 하다[i:k] = tmp         돌아오다 -d0 + d3     돌아오다 0

그 원칙은 꽤 간단하다.원래 거리 $d_{0}$ $d_{0}$ ${\$ 을 계산하고 $d_{0}$ 각 수정 비용을 계산한다.더 나은 비용을 찾으려면 수정 내용을 적용하고 $\delta$ ${\displaystyle \delta }($ 상대 비용)를 반환하십시오.이것은 위의 메커니즘을 이용한 완전한 3옵션 스왑이다.

반항하다 3_opt(관광을 하다):     """3가지 교환에 기초한 반복적인 개선."""     하는 동안에 진실의:         삼각주를 달다 = 0         을 위해 (a, b, c) 에 all_message(렌(관광을 하다)):             삼각주를 달다 += reverse_reverse_if_reversible(관광을 하다, a, b, c)         만일 삼각주를 달다 >= 0:             부숴뜨리다     돌아오다 관광을 하다  반항하다 all_message(n: 인트로):     ""모든 세그먼트 조합 생성""     돌아오다 ((i, j, k)         을 위해 i 에 범위(n)         을 위해 j 에 범위(i + 2, n)         을 위해 k 에 범위(j + 2, n + (i > 0)))

주어진 투어의 경우 모든 세그먼트 조합을 생성하고 각 조합에 대해 세그먼트를 반전시켜 투어를 개선하려고 시도하십시오.더 나은 결과를 찾는 동안 프로세스를 다시 시작하고 그렇지 않으면 완료하십시오.

참고 항목

참조

^ Blazinskas, Andrius; Misevicius, Alfonsas (2011). "Combining 2-OPT, 3-OPT and 4-OPT with K-SWAP-KICK perturbations for the traveling salesman problem". S2CID 15324387. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

F. BOCK (1965). An algorithm for solving traveling-salesman and related network optimization problems. unpublished manuscript associated with talk presented at the 14th ORSA National Meeting.
S. LIN (1965). Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44, 2245-2269. PDF로^{[permanent dead link]} 제공
S. LIN AND B. W. KERNIGHAN (1973). An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Res. 21, 498-516. PDF로^{[permanent dead link]} 제공
로컬 검색 휴리스틱스. (n.d.) 2008년 6월 16일 검색된 http://www.tmsk.uitm.edu.my/~나이마/csc751/slides/LS^{[permanent dead link]}.pdf

[1] Blazinskas, Andrius; Misevicius, Alfonsas (2011). "Combining 2-OPT, 3-OPT and 4-OPT with K-SWAP-KICK perturbations for the traveling salesman problem". S2CID 15324387. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

[1]

Search

3-옵션

네임스페이스

더

참고 항목

참조