외판원 문제

여행 판매원 문제(TSP)는 다음과 같은 질문을 던집니다: "도시 목록과 각 쌍의 도시 사이의 거리를 고려할 때, 각 도시를 정확히 한 번 방문하고 원래의 도시로 돌아오는 가장 짧은 경로는 무엇인가요?"그것은 이론적 컴퓨터 과학과 운영 연구에서 중요한 조합 최적화에서 NP-하드 문제입니다.

TSP의 일반화는 주행 구매자 문제와 차량 라우팅 문제입니다.

계산 복잡도 이론에서 TSP의 결정 버전(길이 L이 주어지면 그래프가 최대 L의 순회를 가지는지 여부를 결정하는 작업)은 NP-완전 문제 클래스에 속합니다.따라서, TSP에 대한 알고리즘에 대한 최악의 경우 실행 시간은 도시 수에 따라 초다항적으로 증가할 가능성이 있습니다.

이 문제는 1930년에 처음 공식화되었으며 최적화에서 가장 집중적으로 연구된 문제 중 하나입니다.이것은 많은 최적화 방법의 벤치마크로 사용됩니다.문제가 계산적으로 어렵지만 많은 휴리스틱과 정확한 알고리즘이 알려져 있기 때문에 수만 개의 도시를 가진 일부 사례는 완전히 해결할 수 있고 수백만 개의 도시를 가진 문제도 1%^[1]의 작은 부분 내에서 근사할 수 있습니다.

TSP는 기획, 물류, 마이크로칩 제조와 같은 가장 순수한 형태에도 여러 가지 응용 프로그램을 가지고 있습니다.약간 변형되어 DNA 염기서열 분석과 같은 많은 부분에서 하위 문제로 나타납니다.이러한 응용 분야에서 개념 도시는 예를 들어 고객, 납땜 지점 또는 DNA 조각을 나타내고 개념 거리는 이동 시간 또는 비용 또는 DNA 조각 간 유사성 측도를 나타냅니다.TSP는 천문학에서도 나타나는데, 천문학자들이 많은 소스를 관측하는 동안 망원경이 소스 간에 이동하는 시간을 최소화하기를 원할 것이기 때문입니다. 이러한 문제에서 TSP는 최적의 제어 문제 안에 포함될 수 있습니다.많은 애플리케이션에서 제한된 리소스나 시간 창과 같은 추가적인 제약 조건이 부과될 수 있습니다.

역사

여행 판매원 문제의 기원은 불분명합니다.1832년의 판매원 여행 안내서에는 이 문제가 언급되어 있으며 독일과 스위스를 통한 예시적인 여행이 포함되어 있지만 수학적인 처리는 포함되어 있지 않습니다.^[2]

TSP는 아일랜드 수학자 윌리엄 로완 해밀턴과 영국 수학자 토마스 커크먼에 의해 19세기에 수학적으로 만들어졌습니다.해밀턴의 이코시안 게임은 해밀턴 사이클을 찾는 것에 기반을 둔 레크리에이션 퍼즐이었습니다.^[3]TSP의 일반적인 형태는 1930년대 비엔나와 하버드에서 수학자들에 의해 처음 연구된 것으로 보이며, 특히 칼 멩거는 문제를 정의하고, 명백한 단순한 알고리즘을 고려하며, 가장 가까운 이웃 휴리스틱의 비최적성을 관찰합니다.

우리는 메신저 문제(실제로 이 문제는 각 집배원이 해결해야 하기 때문에, 어쨌든 많은 여행자가 해결해야 합니다)로 쌍방향 거리가 알려진 많은 지점에 대해 해당 지점을 연결하는 가장 짧은 경로를 찾아야 하는 과제를 나타냅니다.물론, 이 문제는 많은 시도를 통해 해결할 수 있습니다.시행 횟수를 주어진 점의 순열 횟수 아래로 밀어 넣는 규칙은 알려져 있지 않습니다.출발점에서 가장 가까운 지점까지 먼저 이동하고, 그 다음에 가장 가까운 지점까지 이동해야 한다는 규칙은 일반적으로 최단 경로를 산출하지 않습니다.^[4]

그것은 1930년대에 메릴 M에 의해 수학적으로 처음 고려되었습니다. 스쿨버스 라우팅 문제를 해결하려는 플러드.^[5]프린스턴 대학의 해슬러 휘트니는 이 문제에 대한 관심을 불러일으켰고, 그는 이 문제를 "48개 주 문제"라고 불렀습니다."여행 [또는 여행] 판매원 문제"라는 문구를 사용한 최초의 출판물은 줄리아 로빈슨에 의한 1949년 RAND Corporation 보고서 "Hamiltonian 게임(여행 판매원 문제)에 관하여"였습니다.^[6][7]

1950년대와 1960년대에, 산타 모니카에 있는 랜드 연구소가 그 문제를 해결하는 단계들에 상을 제공한 이후에, 그 문제는 유럽과 미국의 과학계에서 점점 인기를 얻게 되었습니다.^[5]RAND Corporation의 George Dantzig, Delbert Ray Fulkerson 및 Selmer M. Johnson은 문제를 정수 선형 프로그램으로 표현하고 솔루션의 절단면 방법을 개발했습니다.그들은 이 주제에 대한 중요한 논문으로 간주되는 것을 썼는데, 이 새로운 방법으로 49개 도시의 사례를 최적화하기 위해 투어를 구성하고 다른 투어는 이보다 더 짧을 수 없다는 것을 증명했습니다.그러나 Dantzig, Fulkerson and Johnson은 거의 최적해에 가까운 해가 주어지면 소수의 추가 부등식(컷)을 추가함으로써 최적성을 찾거나 최적성을 증명할 수 있을 것이라고 추측했습니다.그들은 이 아이디어를 끈 모델을 사용하여 그들의 초기 49개 도시 문제를 해결했습니다.그들은 49개의 도시 문제를 해결하기 위해 26개의 컷만 있으면 된다는 것을 발견했습니다.본 논문은 TSP 문제에 대한 알고리즘적 접근법을 제시하지는 않았지만, 나중에 TSP에 대한 정확한 해결 방법을 만드는 데 있어서는 그 안에 있는 아이디어가 필수적이었지만, 이러한 컷을 작성하는 데 있어서 알고리즘적 접근법을 찾는 데는 15년이 걸릴 것입니다.^[5]절단 평면 방법뿐만 아니라 Dantzig, Fulkerson 및 Johnson은 아마도 처음으로 분기 및 경계 알고리즘을 사용했습니다.^[5]

1959년에 Jillian Beardwood, J.H. Halton 그리고 John Hammersley는 Cambridge Philosophical Society 저널에 "많은 지점을 통과하는 가장 짧은 길"이라는 제목의 기사를 발표했습니다.^[8]비어드우드-Halton-Hammersley 정리는 판매원 여행 문제에 대한 실질적인 해결책을 제공합니다.저자들은 집이나 사무실에서 출발하여 일정한 장소를 방문한 판매원을 대상으로 최단 경로의 길이를 결정하는 점근적 공식을 도출하여 출발점으로 되돌아갑니다.

이후 수십 년 동안, 이 문제는 수학, 컴퓨터 과학, 화학, 물리학, 그리고 다른 과학의 많은 연구자들에 의해 연구되었습니다.그러나 1960년대에 최적 해법을 찾는 대신 길이가 최적 길이의 배수에 의해 증명 가능하게 제한되는 솔루션을 생성하고, 그렇게 함으로써 문제에 대한 하한을 생성하는 새로운 접근법이 만들어졌습니다. 이러한 하한은 분기 및 경계 접근법과 함께 사용됩니다.이렇게 하는 한 가지 방법은 그래프의 최소 신장 트리를 만든 다음 모든 가장자리를 두 배로 만드는 것이었습니다. 이는 최적의 투어 길이가 최소 신장 트리의 무게보다 최대 두 배라는 경계를 생성합니다.^[5]

1976년 크리스토피데스와 세르듀코프는 서로 독립적으로 이 방향으로 크게 발전했습니다.^[9] 크리스토피데스-세르듀코프 알고리즘은 최악의 경우 최적해보다 최대 1.5배 더 긴 해를 산출합니다.알고리즘이 간단하고 빠르기 때문에 많은 사람들이 거의 최적의 솔루션 방법으로 자리를 내주기를 희망했습니다.그러나 이러한 개선의 희망은 즉시 실현되지 않았으며, Christofides-Serdyukov는 2011년에 "그래픽" TSP의 하위 집합에 대해 약간 개선된 근사 알고리듬이 개발될 때까지 최상의 최악의 시나리오를 가진 방법으로 남아 있었습니다.^[10]2020년에 이 작은 개선은 완전한 (미터법) TSP로 확장되었습니다.^[11][12]

1972년 리처드 M. 카프(Richard M. Karp)는 해밀턴 사이클 문제가 NP-완전임을 보여주었고, 이는 TSP의 NP-경도를 의미합니다.이것은 최적의 투어를 찾는 명백한 계산상의 어려움에 대한 수학적인 설명을 제공했습니다.

1970년대 후반과 1980년대에 그뢰첼, 파드베르크, 리날디 등이 절단기와 가지 및 경계를 사용하여 최대 2,392개 도시의 사례를 정확히 해결했습니다.

1990년대에 Applegate, Bixby, Chvátal 및 Cook은 최근의 많은 레코드 솔루션에 사용된 프로그램 콩코드를 개발했습니다.Gerhard Reinelt는 1991년에 TSPLIB를 발표했는데, TSPLIB는 다양한 난이도의 벤치마크 사례를 모아 놓은 것으로, 많은 연구 그룹에서 결과를 비교하기 위해 사용해 왔습니다.2006년, Cook과 다른 사람들은 현재 해결된 TSPLIB 인스턴스 중 가장 큰 마이크로칩 레이아웃 문제에 의해 85,900개의 도시 인스턴스를 통해 최적의 투어를 계산했습니다.수백만 개의 도시가 있는 다른 많은 사례에서 최적의 투어에서 2-3% 이내로 보장되는 솔루션을 찾을 수 있습니다.^[13]

묘사

그래프문제로

TSP는 도시가 그래프의 정점이고 경로가 그래프의 가장자리이며 경로의 거리가 가장자리의 가중치인 무방향 가중 그래프로 모델링할 수 있습니다.한 번씩 꼭지점을 방문한 후 지정된 꼭지점에서 시작하여 마무리하는 최소화 문제입니다.모형이 완전한 그래프인 경우가 많습니다(즉, 각 정점 쌍은 가장자리로 연결됨).두 도시 사이에 경로가 존재하지 않는 경우, 충분히 긴 에지를 추가하면 최적 둘러보기에 영향을 주지 않고 그래프가 완성됩니다.

비대칭 및 대칭

대칭 TSP에서 두 도시 사이의 거리는 각각의 반대 방향에서 동일하며 무방향 그래프를 형성합니다.이 대칭성은 가능한 해의 수를 절반으로 줄입니다.비대칭 TSP에서는 양방향으로 경로가 존재하지 않거나 거리가 달라 방향 그래프를 형성할 수 있습니다.이러한 대칭성이 깨질 수 있는 대표적인 사례로 출발과 도착 요금이 다른 도시의 교통 충돌, 일방통행, 항공료 등을 들 수 있습니다.

관련문제

• 그래프 이론의 관점에서 동등한 공식은 다음과 같습니다. 완전한 가중 그래프(꼭짓점은 도시를 나타내고 가장자리는 도로를 나타내고 가중치는 도로의 비용 또는 거리)가 주어지면 최소 가중치를 갖는 해밀턴 사이클을 구합니다.
• 출발 도시로 돌아가는 것에 대한 요구사항은 문제의 계산 복잡도를 바꾸지 않습니다. 해밀턴 경로 문제를 참조하십시오.
• 또 다른 관련 문제는 병목 여행 세일즈맨 문제(병목 TSP)입니다. 가장 무거운 에지의 최소 무게를 가진 가중 그래프에서 해밀턴 사이클을 찾으십시오.예를 들어, 큰 버스로 좁은 길을 피하는 것.^[14]이 문제는 명백한 교통 및 물류 분야와는 별개로 실질적으로 상당히 중요합니다.대표적인 예가 인쇄 회로 제조입니다: PCB에 구멍을 뚫기 위해 드릴 기계의 경로를 스케줄링하는 것입니다.로봇 기계 가공 또는 드릴링 용도에서 "도시"는 기계에 대한 부품 또는 드릴링할 구멍(크기가 다른)이며, "이동 비용"은 로봇을 다시 조립하는 시간(단일 기계 작업 순서 문제)을 포함합니다.^[15]
• "여행하는 정치인 문제"라고도 알려진 일반화된 여행 세일즈맨 문제는 "도시"가 하나 이상 있는 "주"를 다루며, 세일즈맨은 각 "주"에서 정확히 하나의 "도시"를 방문해야 합니다.칼의 변화를 최소화하기 위해 절단 재고 문제에 대한 해결책을 주문할 때 하나의 응용 프로그램이 발생합니다.다른 하나는 반도체 제조에서의 드릴링(drilling)에 관한 것으로, 예를 들어, 미국 특허 7,054,798을 참조합니다.Noon과 Bean은 일반화된 여행 세일즈맨 문제가 동일한 도시 수를 가진 표준 TSP로 변형될 수 있지만, 거리 행렬이 수정될 수 있음을 보여주었습니다.
• 순차발주 문제는 도시 간 우선관계가 존재하는 일련의 도시를 방문하는 문제를 다루고 있습니다.
• Google의 일반적인 인터뷰 질문은 데이터 처리 노드 간에 데이터를 라우팅하는 방법입니다. 데이터를 전송하는 경로는 시간에 따라 다르지만 노드도 컴퓨팅 성능과 스토리지에 따라 달라지므로 데이터를 어디로 보낼지에 대한 문제가 가중됩니다.
• 여행 구매자 문제는 한 세트의 상품을 구매하는 것으로 부과된 구매자를 말합니다.그는 몇몇 도시에서 이 제품들을 구입할 수 있지만, 다른 가격에 살 수 있고 모든 도시에서 같은 제품을 제공하는 것은 아닙니다.목표는 총 비용(여행 비용 + 구매 비용)을 최소화하고 필요한 모든 제품을 구입할 수 있는 일부 도시 간 경로를 찾는 것입니다.

정수 선형 프로그래밍 공식

TSP는 정수 선형 프로그램으로 공식화될 수 있습니다.^[16][17][18]몇 가지 제형이 알려져 있습니다.두 가지 주목할 만한 제형은 밀러입니다.터커-젬린(MTZ) 공식과 단치히-풀커슨-존슨(DFJ) 제제.DFJ 제형은 더 강하지만 MTZ 제형은 특정 설정에서 여전히 유용합니다.^[19][20]

이 두 공식 모두에서 공통적인 것은 도시에 숫자 $1{\displaystyle \mathrm{},}$ ${\displaystyle \dots ,}$n ${\displaystyle 1,\ldots,n}$로 레이블을 지정하고$$ > 0 ${\displaystyle c_{ij}>0}$을(를) $도시{\displaystyle }$ i ${\displaystyle i}$에서 도시 $j{\displaystyle }$ ${\displaystyle j}$까지의 비용(거리)으로 삼는다는 것입니다$.$제형의 주요 변수는 다음과 같습니다.

${\displaystyle x_{ij}={\begin{case}1&{\text{case}1&{\text{case}}}i{\text{case}}j\0&{\text{case}}\end{case}}$

이는 공식이 정수 프로그램이 되는 0/1 변수이기 때문입니다. 다른 모든 제약 조건은 순수하게 선형 제약 조건입니다.특히 이 프로그램의 목표는

둘러보기 길이 ∑ ${\displaystyle \underset{}{\overset{}{i}}}$ = ${\displaystyle \underset{}{\overset{}{1}}}$ ${\displaystyle \underset{}{\overset{}{}}}$ ∑ j ≠ ${\displaystyle \underset{}{\overset{}{i,}}}$ ${\displaystyle \underset{}{\overset{}{j}}}$= ${\displaystyle \underset{}{\overset{}{1}}}$ n ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle i_{}}$ ${\displaystyle j_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle j_{}}$ ${\displaystyle \sum _{i$=$1}^{n}\sum _{j\neqi,j$=$1}^{n}c_{ij}x_{ij}}.$

추가 제약 조건 없이 {$$x ${\displaystyle i_{}}$ ${\displaystyle j_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {i,j}_{}}$ ${\displaystyle \{x_{ij}\}_{i,j}}$은(는) 투어의 에지 집합에서 매우 멀리 떨어져 있는 에지 집합의 모든 부분 집합에 효과적으로 범위를 지정하며 모든 x ${\displaystyle i_{}}$ ${\displaystyle j_{}}$ = 0 ${\displaystyle x_{ij}$=$0인$ 사소한 최소값을 허용합니다$.$따라서, 두 공식 모두 또한 각 정점에서 정확히 하나의 들어오는 에지와 하나의 나가는 에지가 있다는 제약 조건을 갖는데, $이$는 ${\displaystyle \mathrm{2n}}${\$displaystyle 2n}$개의$$ 선형 방정식으로 표현될 수 있습니다.

${\displaystyle \sum _{}^{}}{\displaystyle \underset{}{\overset{}{}}\underset{}{\overset{}{i}}}$ ${\displaystyle =}$ ${\displaystyle \underset{}{\overset{}{1}}}$${\displaystyle ,}$ ${\displaystyle \underset{}{\overset{}{i}}}$ $\ne$ ${\displaystyle \underset{}{\overset{}{j}}}$ n ${\displaystyle \underset{}{\overset{}{}}}$i ${\displaystyle j_{}}$ = ${\displaystyle 1}$ ${\$$displaystyle$$\su$ j$}^{n}x$=$1$$j$${\displaystyle \underset{}{\overset{}{=}}}$$1,\ldots,$${\displaystyle \underset{}{\overset{}{n}}}$$}$ ${\displaystyle 및}$${\displaystyle \underset{}{\overset{}{}}}$${\displaystyle \sum _{}^{}}$ j ${\displaystyle {}_{}}$ ${\displaystyle \underset{}{\overset{}{1,}}}$ ${\displaystyle \underset{}{\overset{}{}}}$ i ${\displaystyle \underset{}{\overset{}{j}}}$의${\displaystyle \underset{}{\overset{}{}}}$${\displaystyle \underset{}{\overset{}{j}}}$ ≠ = ${\displaystyle 1}$ ${\displaystyle \su$${\displaystyle \underset{}{\overset{}{m}}}$$_{j=1,j\neq i}^{n}x$${\displaystyle \underset{}{\overset{}{\_}}}$${ij$${\displaystyle \underset{}{\overset{}{\}}}}$=$1$$i$입니다$.$

이를 통해 로컬에서 선택한 가장자리 집합이 순회의 것처럼 보이지만, 모든 정점을 방문하는 순회가 하나 있다는 글로벌 요구 사항을 위반하는 솔루션을 허용할 수 있습니다.선택된 에지는 각 정점의 부분 집합에만 방문하는 여러 투어를 구성할 수 있기 때문에 TSP를 어려운 문제로 만드는 것은 거의 틀림없이 이 글로벌 요구 사항입니다.MTZ와 DFJ 공식은 이 최종 요구 사항을 선형 제약 조건으로 표현하는 방식에 차이가 있습니다.

밀러-터커-젬린 제제^[21]

위와 같은 ${\displaystyle {xi}_{}}$ ${\displaystyle j_{}}$ ${\displaystyle x_{ij}$ 변수 외에도 ${\displaystyle 각}$ $i$ = ${\displaystyle 2,}$ ${\displaystyle \dots ,}$ n ${\displaystyle$i = 2$,\ldots,n}$개의 더미 변수 ${\displaystyle {ui}_{}}$ ${\displaystyle u_{i}$가 있습니다$.$ 도시 $1$ ${\displaystyle u_{i}<u_{j}$는 합니다도시 $i{\displaystyle }$ ${\displaystyle i}$을(를) $도시{\displaystyle }$j {\$displaystyle j}$ 앞에 방문합니다$.$ 주어진 $투어{\displaystyle {}_{}}$(${\displaystyle {\mathrm{xi}}_{}}$j {\$displaystyle x_{$ij$$} 변수 값으로 인코딩됨)에 대해 도시 $1{\displaystyle \mathrm{}}$ ${\displaystyle$ u_{i}에서 출발할 때 ${\displaystyle {ui}_{}}$ ${\$를 해당 투어를 따르는 가장자리 수와 같게$$ 만들어 ${\displaystyle {ui}_{}}$ ${\$ 변수에$$ 대한 만족스러운 값을 찾을 수 있습니다.도시 $i{\displaystyle }$ ${\displaystyle i}$에 1}을$($를) 적용합니다$.$

선형 프로그래밍은 엄격(> {\displaystyle \geq $})$보다 엄격하지않은 부등식$$≥ ${\displaystyle$ \geq$$$})$을 선호하기 때문에 다음과 같은 제약을 가하고자 합니다.

${\displaystyle {uj}_{}}$ ${\displaystyle x_{}}$${\displaystyle i_{}}$ ${\displaystyle j_{}}$ $=$ ${\displaystyle 1}$ ${\displaystyle x$${\displaystyle {\_}_{}}$${ij$}=$1}$인 경우 ${\displaystyle {}_{}}$ ${\displaystyle {ui}_{}}$+ ${\displaystyle 1}$ ${\displaystyle u_{j}\gequ_{i}+1}$입니다$.$

${\displaystyle {xi}_{}}$ ${\displaystyle j_{}}$ = ${\displaystyle 0}$ ${\displaystyle x_{ij}$= 0 ${\displaystyle u_{j$$}\$$gequ_$${i}+x_$${ij}}$만 요구해도 ${\displaystyle {이}_{}}$를 달성할 수 없습니다$.$대신 MTZ는${\displaystyle }$(${\displaystyle n}$- ${\displaystyle 1}$) ${\displaystyle (n}$- ${\displaystyle 2}$) ${\displaystyle (n-1)$ (n - 2$)}$개의$$ 선형 제약 조건을 사용합니다.

${\displaystyle {}_{}}$$uj$${\displaystyle {}_{}}$+ (${\displaystyle n}$-${\displaystyle {}_{}2}$ )${\displaystyle }$${\displaystyle \ge }$ ${\displaystyle {ui}_{}}$+${\displaystyle }$( n${\displaystyle }$- ${\displaystyle 1}$) ${\displaystyle {\mathrm{xi}}_{}}$ j ${\displaystyle u_{j}+(n-1)\gequ_{i}+(n-1)x_{ij$}${\displaystyle {\}}_{}}$,${\displaystyle j}$ ∈${\displaystyle }${${\displaystyle 2,}$ ${\displaystyle \dots ,n\}}$ ${\displaystyle i,j\in \{2,\dotsc,n\}$

여기서 상수항 $n$ -${\displaystyle 2}$ ${\displaystyle n-2}$은(는) ${\displaystyle \mathrm{xi}}$ ${\displaystyle j_{}}$ = 0 ${\displaystyle x_{ij$}=$0}$이(가) ${\displaystyle {ui}_{}}$ ${\displaystyle u_{i}}$과(와) ${\displaystyle {ui}_{}}$ ${\displaystyle u_{i}$ 사이의 관계를 부과하지 않는 충분한 여유를 제공합니다$.$

${\displaystyle {ui}_{}}$ ${\$ 변수가$$ 단일 투어가 모든 도시를 방문하도록 강제하는 방법은 투어를 따르는 각 단계마다$$ ($적어도)$ 1 {\displaystyle $1}$ 증가하고, 투어가 도시 $1{\displaystyle \mathrm{}}${\$displaystyle 1}$을(를) 통과하는 경우에만 감소가 허용됩니다$.$ 이 제약 조건은 c를 통과하지 않는 모든 투어에서 위반됩니다.$it{\displaystyle \mathrm{}}$ 1 ${\displaystyle 1$ 따라서 이를 만족시킬 수 있는 유일한 방법은 투어 패스 시티 $1{\displaystyle \mathrm{}}$ ${\displaystyle 1}$이(가) 다른 모든 도시를 통과하는 것입니다.

따라서 TSP의 MTZ 공식화는 다음과 같은 정수 선형 프로그래밍 문제입니다.

${\displaystyle {\begin{aligned}\min \sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}&\colon &\x_{ij}\in {}&\{0,1\}&\i,j=1,\ldots,n;\u_{i}\in {}&\mathbf {Z}&i=2,\ldots,n;\\sum _{i=1,i\neq j}^{n}x_{ij}={&1&j=1,\ldots,n;\sum _{j=1,j\neq i}^{n}x_{ij}={&1&i=1,\ldots,\ldots,n;\u_{i}-u_{j}+(n-1)x_{ij}\leq {}&n-2&2\leq i\neq j\leq n;\2\leq {}&n&2\leq i\leq n.\end{aligned}}$

첫 번째 평등 집합은 각 도시가 정확히 한 개의 다른 도시에서 도착해야 하고, 두 번째 평등 집합은 각 도시에서 정확히 한 개의 다른 도시로 출발해야 합니다.마지막 제약 조건으로 인해 모든 도시를 포괄하는 단일 투어만 있을 뿐 모든 도시를 포괄하는 두 개 이상의 분리된 투어는 없습니다.이를 증명하기 위해 아래 (1) 모든 실현 가능한 해는 도시의 닫힌 시퀀스를 하나만 포함하고, (2) 모든 도시를 포함하는 단일 투어에 대해 제약 조건을 만족하는 더미$$ 변수 ${\displaystyle {ui}_{}}$ ${\$에 대한 값이 있음을 보여줍니다.

모든 실현 가능한 솔루션이 하나의 폐쇄된 도시 순서만 포함하고 있다는 것을 증명하려면 실현 가능한 솔루션의 모든 하위 투어가 도시 1을 통과한다는 것을 보여주면 됩니다(평등이 그러한 투어를 한 번만 보장한다는 점에 주목).도시 1을 통과하지 않는 k 단계의 하위 투어에 대해 ${\displaystyle {xi}_{}}$ ${\displaystyle j_{}}$ = 1 ${\displaystyle x_{ij$}=$1}$에 해당하는 모든 부등식을 합하면 다음을 얻습니다.

${\displaystyle (n-1)k\leq (n-1)k,}$

그것은 모순입니다.

이제 모든 도시를 포함하는 모든 단일 투어에 대해 제약 조건을 만족하는 더미$$ 변수 ${\displaystyle {ui}_{}}$ ${\$에 대한 값이 있음을 알아야 합니다.

일반성을 잃지 않고 도시 1에서 출발(그리고 종료)하는 것으로 투어를 정의합니다.$i$ ${\displaystyle i}$이(${\displaystyle 가}$) $t단계{\displaystyle (}$i${\displaystyle ,}$ ${\displaystyle t}$ = ${\displaystyle 2,}$ ${\displaystyle 3,}$ ${\displaystyle \dots ,n}$ ) {\$displaystyle t(i,t$ = $2,3,\ldots,n)}$에서 방문한 경우 ${\displaystyle {ui}_{}}$ = t ${\$$displaystyle u_{i$}= t$}$를 선택합니다$.$ 그런 다음

${\displaystyle u_{i}-u_{j}\leq n-2,}$

${\displaystyle {ui}_{}}$ ${\displaystyle u_{i}$는 $n$ ${\displaystyle n}$보다 클 수 없고 ${\displaystyle {uj}_{}}$ ${\displaystyle u_{j}}$는 2보다 작을 수 없으므로 ${\displaystyle {xi}_{}}$ ${\displaystyle j_{}}$ = ${\displaystyle \mathrm{0일}}$ 때마다 제약 조건이 충족됩니다$.$ {\$displaystyle x_{ij$}=$0.}$ ${\displaystyle {xi}_{}}$ ${\displaystyle j_{}}$ = ${\displaystyle 1}$ ${\displaystyle x_{ij$}=$1}$의 경우 다음과 같습니다$.$

${\displaystyle u_{i}-u_{j}+(n-1)x_{ij}=(t)-(t+1)+n-1=n-2,}$

제약 조건을 만족시키는

단치히-풀커슨-존슨 제제

도시에 숫자 1, …, n으로 레이블을 지정하고 다음을 정의합니다.

${\displaystyle x_{ij}={\begin{case}1&{\text{case}1&{\text{case}}}i{\text{case}}j\0&{\text{case}}\end{case}}$

i에서 city j까지의 거리를 city j> 0 ${\displaystyle c_{ij}$ > $0}$으로 합니다.그러면 TSP는 다음과 같은 정수 선형 프로그래밍 문제로 쓸 수 있습니다.

${\displaystyle {\begin{aligned}\min &\sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}\colon &\&\sum _{i=1,i\neq j}^{n}x_{ij}=1&j=1,\n\sum _{j=1,j\neq i}^{n}x_{ij}=1&i=1,\ldots,n;\&\sum _{i\in Q}{\sum _{j\neq i,j}{x_{ij}}\leq Q -1&\모든 Q\subsetneq \{1,\ldots,n\}, Q \geq 2\\\end{aligned}}$

하위 투어 제거 제약이라고 불리는 DFJ 공식의 마지막 제약 조건은 Q가 하위 투어를 구성할 수 없는 적절한 하위 집합을 보장하므로 반환되는 솔루션은 단일 투어이지 소규모 투어의 결합이 아닙니다.이로 인해 가능한 제약 조건이 기하급수적으로 증가하기 때문에 실제로는 행 생성으로 해결됩니다.^[22]

솔루션 계산

NP-하드 문제에 대한 전통적인 공격 라인은 다음과 같습니다.

• 작은 문제 크기에 대해서만 비교적 빠르게 작동하는 정확한 알고리즘을 고안합니다.
• "최적이 아닌" 또는 휴리스틱 알고리즘, 즉 합리적인 시간에 근사적인 솔루션을 제공하는 알고리즘을 고안합니다.
• 더 나은 또는 정확한 휴리스틱이 가능한 문제("하위 문제")에 대한 특수 사례 찾기

정확한 알고리즘

가장 직접적인 해결책은 모든 순열(순열 조합)을 시도해보고 어떤 순열이 가장 저렴한지(브런트 포스 검색 사용) 확인하는 것입니다.이 접근법의 실행 시간은 도시 수의 계승인$$$($ O$(n!)}$의 다항식 인자 내에 있으므로 이 솔루션은 20개 도시에 대해서만 실행 불가능하게 됩니다.

동적 프로그래밍의 가장 초기 응용 프로그램 중 하나는 $O{\displaystyle (}$n22n){\$displaystyle O(n^{2}2^{n})}$ 시간에 문제를 해결하는 Hold-Karp 알고리즘입니다$.$^[23]또한 동적 프로그래밍 접근 방식 이전에 Exclusion-Inclusion(배제-포함)을 통해 이 경계에 도달했습니다.

이러한 시간적 한계를 개선하는 것은 어려울 것으로 보입니다.예를 들어, O $시간{\displaystyle ({\mathrm{.}}^{9999n}}$ ${\displaystyle$ O$(1.9999^{n})}$에 실행되는 TSP에 대한 고전적인 정확한 알고리즘이 존재하는지$$ 여부가 확인되지 않았습니다.^[24]Ambainis 등으로 인한 TSP에 대한 현재 최고의 양자 정확 알고리즘은 O $시간{\displaystyle ({\mathrm{.}}^{728n}}$ ${\displaystyle O(1.728^{n})}$에 실행됩니다$.$^[25]

기타 접근 방식은 다음과 같습니다.

• 40-60개의 도시를 포함하는 TSP를 처리하는 데 사용할 수 있는 다양한 분기 및 경계 알고리즘.

• 선형 프로그래밍을 연상시키는 기법을 사용하는 점진적 개선 알고리즘최대 200개의 도시에 적합합니다.
• 분기 및 경계 및 문제별 절단 생성(분기^[26] 및 절단) 구현. 이것이 ^[27]대규모 인스턴스를 해결하기 위한 선택 방법입니다.이 접근 방식은 85,900개의 도시에 대한 사례를 해결하는 현재 기록을 보유하고 있습니다(Applegate et al. 참조) (2006).

TSPLIB의 15,112개 독일 도시에 대한 정확한 해결책은 1954년 조지 단치히, 레이 풀커슨, 셀머 M. 존슨이 제안한 절단면 방법을 사용하여 2001년 선형 프로그래밍에 기초하여 발견되었습니다.계산은 Rice University와 Princeton University에 위치한 110개의 프로세서 네트워크에서 수행되었습니다.총 계산 시간은 단일 500MHz Alpha 프로세서에서 22.6년과 맞먹었습니다.2004년 5월, 스웨덴의 모든 24,978개 마을을 방문하는 여행 세일즈맨 문제가 해결되었습니다. 길이가 약 72,500km에 달하는 여행이 발견되었고 더 짧은 여행은 존재하지 않는다는 것이 증명되었습니다.^[28]2005년 3월, 서킷 보드의 33,810 포인트를 모두 방문하는 여행 세일즈맨 문제는 Concorde TSP Solver를 사용하여 해결되었습니다: 길이 66,048,945개의 투어가 발견되었고 더 짧은 투어는 존재하지 않는다는 것이 증명되었습니다.계산에 소요된 시간은 약 15.7 CPU년이었습니다(Cook et al. 2006).2006년 4월에 Concorde TSP Solver를 사용하여 85,900 포인트의 인스턴스가 해결되었으며, 136개의 CPU-년을 초과했습니다(Applegate 등 참조). (2006).

휴리스틱 및 근사 알고리즘

다양한 휴리스틱과 근사 알고리즘이 고안되었는데, 이는 빠른 속도로 좋은 솔루션을 산출합니다.여기에는 다중 조각 알고리즘이 포함됩니다.최신 방법은 합리적인 시간 내에 매우 큰 문제(수백만 개의 도시)에 대한 솔루션을 찾을 수 있으며, 최적 솔루션에서 불과 2~3% 떨어진 높은 확률로 해결할 수 있습니다.^[13]

발견주의의 여러 범주가 인정됩니다.

건설적 휴리스틱

가장 가까운 이웃(NN) 알고리즘(욕심 많은 알고리즘)을 통해 판매원은 다음 조치로 가장 가까운 방문하지 않은 도시를 선택할 수 있습니다.이 알고리즘은 효과적으로 짧은 경로를 빠르게 산출합니다.평면에 무작위로 분포된 N개 도시의 경우, 알고리즘은 가능한 가장 짧은 경로보다 평균적으로 25% 더 긴 경로를 산출합니다.^[29]그러나 NN 알고리즘이 최악의 경로를 제공하는 도시 분포가 특별히 마련되어 있습니다.^[30]이것은 비대칭 TSP와 대칭 TSP 모두에 해당됩니다.^[31]Rosenkrantz et al. 은 NN 알고리즘이 삼각형 부등식을 만족하는 인스턴스에 대한 근사 인자 θ(${\displaystyle \log }$⁡ $){\displaystyle$ \$Theta$(\$log$V$)}$를 가지고 있음을 보여주었습니다.가장 가까운 방문하지 않은 도시의 그룹(파편)을 연결하는 가장 가까운 NF(Nearest Fragment) 연산자라고 불리는 NN 알고리즘의 변형은 연속적인 반복으로 더 짧은 경로를 찾을 수 있습니다.^[33]NF 연산자는 엘리트리스트 모델의 추가적인 개선을 위해 NN 알고리즘에 의해 얻어진 초기 솔루션에 적용될 수도 있으며, 여기서 더 나은 솔루션만이 받아들여집니다.

점 집합의 비트닉 투어는 점을 정점으로 하는 최소 주변 모노톤 다각형입니다. 동적 프로그래밍을 통해 효율적으로 계산할 수 있습니다.

또 다른 구성적 휴리스틱인 MTS(Match Twice and Stitch)는 두 개의 순차적 매칭을 수행하며, 첫 번째 매칭의 모든 에지를 삭제한 후 두 번째 매칭을 실행하여 일련의 사이클을 생성합니다.그런 다음 사이클을 연결하여 최종 투어를 생성합니다.^[34]

크리스토파이데스와 세르듀코프의 알고리즘

Christofides와 Serdyukov의 알고리즘은 비슷한 개요를 따르지만 최소 신장 트리를 다른 문제인 최소 가중치 완벽 일치의 솔루션과 결합합니다.이것은 최대 1.5배의 최적의 TSP 투어를 제공합니다.그것은 최초의 근사 알고리즘 중 하나였고, 부분적으로는 다루기 힘든 문제에 대한 실용적인 접근법으로서 근사 알고리즘에 관심을 끄는 역할을 했습니다.사실, "알고리즘"이라는 용어는 나중까지 일반적으로 근사 알고리즘으로 확장되지 않았습니다. Christofides 알고리즘은 처음에는 Christofides 휴리스틱이라고 불렸습니다.^[9]

이 알고리즘은 최소 신장 트리의 비용을 두 배로 증가시키는 것에서 시작된 TSP의 하한을 개선하는 데 도움이 되는 그래프 이론의 결과를 사용하여 사물을 다르게 봅니다.오일러 그래프가 주어지면 $O{\displaystyle (n)}$ ${\displaystyle O(n)}$ 시간$$ 안에 오일러 투어를 찾을 수 있습니다.^[5]따라서 TSP의 도시를 정점으로 하는 오일러 그래프를 가지고 있다면 이러한 방법을 사용하여 TSP 해를 찾을 수 있음을 쉽게 알 수 있습니다.삼각 부등식에 의해 우리는 TSP 투어가 오일러 투어보다 더 길어질 수 없으며 따라서 TSP에 대한 하한이 있음을 알고 있습니다.이와 같은 방법에 대해서는 아래에서 설명합니다.

1. 문제에 대한 최소 확장 트리 찾기
2. 오일러 그래프를 만들기 위해 모든 모서리에 대해 중복 생성
3. 이 그래프에 대한 오일러 투어 찾기
4. TSP로 변환: 도시를 두 번 방문한 경우, 투어에서 이 전 도시에서 이 후 도시로 바로 가기를 만듭니다.

하한을 개선하기 위해서는 오일러 그래프를 생성하는 더 나은 방법이 필요합니다.삼각 부등식에 의해, 최고의 오일러 그래프는 최고의 여행 세일즈맨 투어와 같은 비용을 가져야 하므로, 최적의 오일러 그래프를 찾는 것은 적어도 TSP만큼 어렵습니다.이 방법 중 하나는 $O{\displaystyle ({n3\mathrm{}}^{}}$ ${\displaystyle O(n^{3})}$의 알고리즘을 사용하여 최소 가중치를 일치시키는 것입니다$.$^[5]

그래프를 오일러 그래프로 만드는 것은 최소 신장 트리로 시작합니다.그러면 홀수 순서의 모든 꼭짓점을 짝수로 만들어야 합니다.따라서 홀수 차수 정점에 대한 일치를 추가해야 하며, 이는 홀수 차수 정점의 순서를 1씩 증가시킵니다.^[5]이것은 우리에게 오일러와 같은 모든 정점이 짝수 순서인 그래프를 남깁니다.위의 방법을 적용하면 Christofides와 Serdyukov의 알고리즘을 얻을 수 있습니다.

1. 문제에 대한 최소 확장 트리 찾기
2. 홀수 순서의 도시 집합으로 문제에 대한 일치를 만듭니다.
3. 이 그래프에 대한 오일러 투어 찾기
4. 바로 가기를 사용하여 TSP로 변환합니다.

쌍대교환

쌍방향 교환 또는 2-opt 기법은 2개의 에지를 반복적으로 제거하고 에지 제거를 통해 생성된 조각들을 새롭고 짧은 투어로 다시 연결하는 2개의 다른 에지로 대체하는 것을 포함합니다.마찬가지로 3-opt 기법은 3개의 가장자리를 제거하고 다시 연결하여 더 짧은 투어를 형성합니다.이것들은 k-opt 방법의 특별한 경우들입니다.Lin-Kernighan이라는 레이블은 2-opt의 잘못된 이름입니다.린-커니건은 사실 더 일반적인 k-opt 방법입니다.

유클리드 사례의 경우, 2-광학은 크리스토피데스의 알고리즘보다 약 5% 더 나은 평균 솔루션을 제공합니다.그리디 알고리즘으로 만든 초기 해로 시작하면 다시 평균 이동 횟수가 크게 줄어 $O{\displaystyle (n)}$ ${\displaystyle O(n)}$이지만$$랜덤 시작의 경우 평균 이동 횟수는 $O{\displaystyle (n}$ ${\displaystyle \log }$⁡${\displaystyle (n)}$ ${\displaystyle O(n\log(n))}$입니다$.$ 다만 크기가 약간 증가하는 것이 순서이지만,작은 문제에 대한 초기 이동 횟수는 그리디 휴리스틱으로 만든 것에 비해 랜덤 시작에 대해 10배나 큽니다.이는 이러한 2-광학이 교차와 같은 솔루션의 '나쁜' 부분을 이용하기 때문입니다.이러한 유형의 휴리스틱은 경로 솔루션을 최적화하기 위해 차량 라우팅 문제 휴리스틱 내에서 종종 사용됩니다.^[29]

k-opt 휴리스틱 또는 린-커니간 휴리스틱

린-커니건 휴리스틱은 V-opt 또는 variable-opt 기법의 특별한 경우입니다.여기에는 다음 단계가 포함됩니다.

1. 둘러보기가 주어지면 k개의 상호 연결된 모서리를 삭제합니다.
2. 나머지 조각을 둘러보기로 다시 조립하여 분리된 부분선을 남기지 않습니다(즉, 조각의 끝점을 서로 연결하지 마십시오).이것은 사실상 고려 중인 TSP를 훨씬 더 간단한 문제로 단순화시킵니다.
3. 각 프래그먼트 엔드포인트는 2k - 2개의 다른 가능성에 연결할 수 있습니다. 사용 가능한 총 프래그먼트 엔드포인트 2k 중 고려 중인 프래그먼트의 엔드포인트 2개는 허용되지 않습니다.그런 다음 제한된 2k 도시 TSP를 브루트 포스 방법으로 해결하여 원래 조각의 최소 비용 재조합을 찾을 수 있습니다.

1965년 벨 연구소의 Shen Lin에 의해 소개된 것처럼 k-opt 방법 중 가장 인기 있는 것은 3-opt입니다.3-opt의 특별한 경우는 가장자리가 서로 분리되어 있지 않은 경우입니다(2개의 가장자리가 서로 인접함).실제로, 제거된 에지 중 두 개가 인접한 이 특별한 부분 집합으로 3-변경을 제한함으로써 일반 3-opt의 조합 비용 없이 2-opt보다 상당한 개선을 달성할 수 있습니다.이 소위 2.5 옵션이라고 불리는 옵션은 일반적으로 2-opt와 3-opt의 중간 정도에 속합니다. 달성된 투어의 질과 투어 달성에 소요되는 시간 모두에서 말입니다.

V-opt 휴리스틱

variable-opt 방법은 k-opt 방법의 일반화와 관련이 있습니다.k-opt 방법은 원래 둘러보기에서 고정된 수의 에지(k)를 제거하는 반면, variable-opt 방법은 제거할 에지 세트의 크기를 고정하지 않습니다.대신, 그들은 검색 프로세스가 계속 진행됨에 따라 세트를 확장합니다.이 계열에서 가장 잘 알려진 방법은 린-커니건 방법(위에서 2-opt의 잘못된 이름으로 언급됨)입니다.Shen Lin과 Brian Kernighan은 1972년에 그들의 방법을 처음 발표했고, 그것은 거의 20년 동안 여행하는 판매원 문제를 해결하는 가장 신뢰할 수 있는 발견이었습니다.1980년대 후반에 데이비드 존슨과 그의 연구팀에 의해 벨 연구소에서 더 발전된 가변 옵션 방법이 개발되었습니다.이러한 방법(때로는 린-커니건-존슨이라고도 함)은 린-커니건 방법을 기반으로 하며, 타부 탐색과 진화 컴퓨팅에서 아이디어를 추가합니다.기본적인 Lin-Kernighan 기법은 최소 3-opt를 보장하는 결과를 제공합니다.린-커니건-존슨 방법은 린-커니건 투어를 계산한 다음, 적어도 네 개의 가장자리를 제거하고 투어를 다른 방식으로 다시 연결하는 돌연변이로 설명된 투어를 섭동시키고, 그 다음 새로운 투어를 V-opting합니다.이 돌연변이는 종종 린-커니건에 의해 확인된 지역 최소값에서 투어를 옮기기에 충분합니다.V-opt 방법은 문제에 대한 가장 강력한 휴리스틱으로 널리 간주되며 해밀턴 사이클 문제와 다른 휴리스틱이 실패하는 다른 비계량 TSP와 같은 특수한 경우를 해결할 수 있습니다.수년간 Lin-Kernighan-Johnson은 최적의 솔루션이 알려진 모든 TSP에 대한 최적의 솔루션을 찾아냈고, 이 방법이 시도된 다른 모든 TSP에 대해 가장 잘 알려진 솔루션을 찾아냈습니다.

무작위 개선

로컬 검색 휴리스틱 하위 알고리듬을 사용하는 최적화된 마르코프 체인 알고리듬은 700~800개 도시에 대한 최적 경로에 매우 가까운 경로를 찾을 수 있습니다.

TSP는 유전 알고리즘, 시뮬레이션 어닐링, 타부 검색, 개미 군집 최적화, 강 형성 역학(군집 지능 참조) 및 교차 엔트로피 방법과 같은 조합 최적화를 위해 고안된 많은 일반 휴리스틱의 시금석입니다.

압축 삽입 휴리스틱

볼록한 선체와 같은 하위 투어에서 시작하여 다른 꼭짓점을 삽입합니다.

개미집락 최적화

인공지능 연구자 마르코 도리고는 1993년 ACS(개미 군락 시스템)라고 불리는 개미 군락의 시뮬레이션을 이용하여 TSP에 대해 휴리스틱하게 "좋은 해결책"을 생성하는 방법을 설명했습니다.^[36]그것은 먹이원과 둥지 사이의 짧은 길을 찾기 위해 실제 개미에서 관찰되는 행동을 모델링합니다. 이는 각 개미가 다른 개미들에 의해 퇴적된 흔적 페로몬을 따르는 것을 선호하기 때문에 발생하는 행동입니다.

ACS는 지도에서 가능한 많은 경로를 탐색하기 위해 많은 가상 개미 에이전트를 보냅니다.각각의 개미는 도시까지의 거리와 도시의 가장자리에 축적된 가상 페로몬의 양을 결합한 휴리스틱에 기초하여 다음에 방문할 도시를 확률적으로 선택합니다.개미들은 탐험을 하고, 그들이 모두 여행을 마칠 때까지 그들이 건너는 각각의 가장자리에 페로몬을 축적합니다.이때 가장 짧은 여행을 마친 개미는 완전한 여행 경로를 따라 가상 페로몬을 축적합니다(글로벌 트레일 업데이트).페로몬의 예치량은 여행 기간에 반비례합니다: 여행 기간이 짧을수록 더 많이 예치됩니다.

특수한 경우

미터법

델타-TSP 또는 δ-TSP라고도 알려진 메트릭 TSP에서, 시외 거리는 삼각형 부등식을 만족합니다.

TSP의 매우 자연스러운 제한은 도시 사이의 거리가 삼각형 부등식을 만족시키기 위한 메트릭을 형성하도록 요구하는 것입니다. 즉, A에서 B까지의 직접 연결은 중간 C를 경유하는 경로보다 결코 더 멀리 있지 않습니다.

${\$$AB}\leqd_{$$AC}+d_{CB$

그런 다음 모서리 스팬은 꼭짓점 집합에 메트릭을 구축합니다.도시를 평면상의 점으로 볼 때, 많은 자연 거리 함수는 측정 지표이며, TSP의 많은 자연 사례는 이 제약을 만족합니다.

다음은 다양한 메트릭에 대한 메트릭 TSP의 몇 가지 예입니다.

• 유클리드 TSP에서 두 도시 사이의 거리는 해당 지점 사이의 유클리드 거리입니다.
• 직선형 TSP에서 두 도시 사이의 거리는 x 좌표와 y 좌표의 차이의 절대값의 합입니다.이 메트릭은 종종 맨하탄 거리 또는 도시 블록 메트릭이라고 불립니다.
• 최대 메트릭에서 두 점 사이의 거리는 x 좌표와 y 좌표의 차이의 절대값의 최대값입니다.

예를 들어, 인쇄 회로 기판에 주어진 구멍 세트를 뚫는 기계를 라우팅할 때 마지막 두 가지 메트릭이 나타납니다.맨하탄 미터법은 처음에 한 좌표를 조정하고 다른 좌표를 조정하는 기계에 해당하므로 새로운 점으로 이동하는 시간은 두 움직임의 합입니다.최대 메트릭은 두 좌표를 동시에 조정하는 기계에 해당하므로 새 점으로 이동하는 시간은 두 움직임 중 느린 속도입니다.

TSP의 정의에 따르면, TSP는 도시를 두 번 방문하는 것을 허용하지 않지만, 많은 애플리케이션들은 이 제약이 필요하지 않습니다.이러한 경우 대칭적인 비메트릭 인스턴스를 메트릭 인스턴스로 축소할 수 있습니다.이것은 원래의 그래프를 도시간 거리 $d{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{AB}}_{}}$가$${\$displaystyle d_{$인 완전한 그래프로 대체합니다.$AB}}$은(는) 원래 그래프에서 A와 B 사이의 최단 경로 길이로 대체됩니다$$.

유클리드적

유클리드 평면에 있는 점들의 경우, 여행 판매원 문제에 대한 최적의 해결책은 모든 점들을 통해 단순한 다각형, 즉 점들의 다각화를 형성합니다.^[37]교차가 있는 최적이 아닌 솔루션은 로컬 최적화를 통해 교차 없이 더 짧은 솔루션으로 만들 수 있습니다.유클리드 거리는 삼각형 부등식을 따르므로 유클리드 TSP는 미터법 TSP의 특별한 경우를 형성합니다.그러나 입력 지점이 정수 좌표를 갖는 경우에도 거리는 일반적으로 제곱근의 형태를 띠며, 순회 길이는 라디칼의 합이므로 다양한 순회 길이의 정확한 비교를 수행하는 데 필요한 기호 계산을 수행하기가 어렵습니다.

일반 TSP와 마찬가지로 정확한 유클리드 TSP는 NP-하드이지만 라디칼의 합에 대한 문제는 결정 버전이 NP에 있으므로 NP-완전임을 증명하는 데 장애가 됩니다.거리가 정수로 반올림된 문제의 이산화된 버전은 NP-완전입니다.^[38]합리적인 좌표와 실제 유클리드 미터법으로 유클리드 TSP는 PSPACE의 하위 클래스인 ^[39]카운팅 계층에 있는 것으로 알려져 있습니다.임의의 실제 좌표에서는 셀 수 없이 많은 입력이 있기 때문에 유클리드 TSP는 그러한 클래스에 있을 수 없습니다.이러한 복잡성에도 불구하고, 유클리드 TSP는 근사에 대한 일반적인 메트릭 사례보다 훨씬 쉽습니다.^[40]예를 들어, 유클리드 TSP의 인스턴스와 연관된 그래프의 최소 신장 트리는 유클리드 최소 신장 트리이므로 n개의 점(가장자리 수보다 상당히 작음)에 대한 예상 O(n log n) 시간으로 계산할 수 있습니다.이를 통해 위의 삼각형 부등식을 가진 TSP에 대한 간단한 2-근사 알고리즘이 더 빠르게 작동할 수 있습니다.

일반적으로, 임의의 c > 0에 대하여, d는 유클리드 공간의 차원의 수이고, TSP의 기하학적 인스턴스에 대해 최대 (1 + 1/c)배의 길이의 순회를 찾는 다항식 시간 알고리즘이 있습니다.

${\displaystyle O\left(n(\log n))^{(O(c{\sqrt {d}))^{d-1}\right)},}$

시간. 이를 PTAS(다항식 시간 근사 체계)라고 합니다.^[41]산지브 아로라와 조셉 S. B. 미첼은 유클리드 TSP를 위한 PTAS를 동시에 발견한 공로로 2010년 괴델상을 수상했습니다.

실제로는 더 약한 보장을 가진 더 단순한 휴리스틱이 계속 사용되고 있습니다.

비대칭

대부분의 경우 TSP 네트워크에서 두 노드 사이의 거리는 양방향으로 동일합니다.A에서 B까지의 거리가 B에서 A까지의 거리와 같지 않은 경우를 비대칭 TSP라고 합니다.비대칭 TSP의 실질적인 적용은 스트리트 레벨 라우팅(일방향 스트리트, 슬립 로드, 고속도로 등에 의해 비대칭으로 생성됨)을 사용한 경로 최적화입니다.

대칭으로의 변환

비대칭 TSP 그래프를 푸는 것은 다소 복잡할 수 있습니다.다음은 노드 A, B 및 C 사이의 모든 가능한 경로 가중치를 포함하는 3×3 행렬입니다.한 가지 옵션은 크기 N의 비대칭 행렬을 크기 2N의 대칭 행렬로 바꾸는 것입니다.^[42]

비대칭 경로 가중치

	A	B	C
A		1	2
B	6		3
C	5	4

크기를 두 배로 늘리기 위해 그래프의 각 노드를 복제하여 두 번째 고스트 노드를 생성합니다. 두 번째 고스트 노드는 매우 낮은(아마도 음의) 가중치를 가진 "고스트" 에지가 있는 원래 노드에 연결되며 여기서 -w로 표시됩니다. (또는 고스트 에지는 가중치가 0이고 다른 모든 에지에 가중치 w가 추가됩니다.)위에 표시된 원본 3×3 행렬은 왼쪽 하단에 표시되고 원본은 오른쪽 상단에 표시됩니다.행렬의 두 사본 모두 대각선이 -w로 표시되는 저비용 홉 경로로 대체되었습니다.새 그래프에서 원래 노드를 직접 연결하는 에지가 없고 고스트 노드를 직접 연결하는 에지가 없습니다.

대칭 경로 가중치

	A	B	C	A'	B'	C'
A				−w	6	5
B				1	−w	4
C				2	3	−w
A'	−w	1	2
B'	6	−w	3
C'	5	4	−w

고스트 노드와 대응하는 원래 노드를 연결하는 "ghost" 에지의 가중치 -w는 모든 고스트 에지가 새 그래프의 최적 대칭 TSP 솔루션에 속해야 함을 보장하기에 충분히 낮아야 합니다(w=0이 항상 충분히 낮지는 않음).결과적으로 최적의 대칭 투어에서 각 원래 노드는 고스트 노드 옆에 나타납니다(예: 가능한 경로는 $A$ → ${\displaystyle {}^{}}$→ ${\displaystyle \mathrm{C}}$ → ${\displaystyle {}^{}}$→ ${\displaystyle {}^{}}$→ ${\displaystyle \mathrm{A}}$ {\$to A'\to C'\to B'\to$A$}$→ A ${\displaystyle \mathrm {A\$to C}\to B\to B'\$to A$ 원래 노드와 고스트 노드를 다시 병합하면 원래 비대칭 문제의 (최적) 해결책을 얻을 수 있습니다(예: 우리의 예제에서).e, $A$ → ${\displaystyle \mathrm{C}}$ → ${\displaystyle \mathrm{B}}$ → A ${\displaystyle \mathrm {A\to C\to B\to$ A$}}).$

분석자의 문제

기하학적 측정 이론에는 다음과 같은 질문을 하는 유사한 문제가 있습니다. 유클리드 공간의 부분 집합 E가 어떤 조건에서 정류 가능한 곡선에 포함될 수 있는지(즉, E의 모든 점을 방문하는 유한한 길이의 곡선이 언제 있습니까?).이 문제는 분석가의 판매원 출장 문제로 알려져 있습니다.

사각형에 있는 점들의 랜덤 집합에 대한 경로 길이

$X$ ${\displaystyle 1_{}}$ ${\displaystyle \dots ,X_{}}$ n ${\displaystyle X_{1},\ldots,X_{n}}$를 $정사각형$ $[{\displaystyle 0,}$ ${\displaystyle 1{}^{}}$ ${\displaystyle 2^{}}$ ${\displaystyle [0,1]^{2}},$${\displaystyle {Ln}_{}^{}}$ ∗ ${\displaystyle L_{n}^{\ast}}$를 일반적인 유클리드 거리에 따라 이 점 집합에 대한 가장 짧은 경로 길이(즉, TSP 해)라고 가정합니다.거의^[8] 확실하게는

${\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}\오른쪽 화살표 \beta \qquad {\text{when}}}n\to \infty,}$

여기서 $\beta$ ${\displaystyle \$beta }은(는) 명시적으로 알려지지 않은 양의 상수입니다.L ${\displaystyle n_{}^{}}$ ∗ ≤ 2 ${\displaystyle \mathrm{n}}$+ 2 ${\displaystyle L_{n}^{*}\leq 2{\sqrt {n}}+2}($아래 참조)이므로, 유계 수렴 정리로부터 $\beta$ = ${\displaystyle \underset{}{lim}}$ ${\displaystyle \underset{}{n}}$ → ∞ ${\displaystyle \underset{}{}}$ ${\displaystyle [{}_{}^{}}$ ${\displaystyle n_{}^{}}$ ∗${\displaystyle {}_{}^{}}$]${\displaystyle }$/ ${\displaystyle n}$ ${\displaystyle$\beta =$\lim _{n\to \infty}\mathbb {E}$ 따라서 $\beta$ ${\displaystyle$\beta }의 하한 및 상한은 $E{\displaystyle }$[${\displaystyle {}_{}^{}}$ ${\displaystyle n_{}^{}}$ ∗${\displaystyle {}_{}^{}}$ ${\displaystyle \m$}$atbb {E$$[L_{$n}^{*}}.

거의 확실한 한계 L ${\displaystyle \frac{n_{}^{}}{}}$ ∗ ${\displaystyle \frac{{}_{}^{}}{}}$ → ${\displaystyle \beta }$ ${\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}\$오른쪽 $화살표 \$beta }을(를) n →$$∞ {\$displaystyle$ n$\to$ \infty$}$로 지정하면 독립 위치 X ${\displaystyle 1_{}}$ ${\displaystyle \dots ,}$ ${\displaystyle X_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle X_{1},\ldots, X_{n}$이(가) 균일한 가장자리를 가진 정지 에르고딕 프로세스의 관측치로 대체될 수 있습니다.

상한

• $하나$는 L ∗ ≤${\displaystyle 2}$ ${\displaystyle \mathrm{n}}$ +$$2 {\$displaystyle$ L$^{*}\leq$2{\$sqrt$ {n$}}+2}$이므로$,$ 정사각형의 $너비$ $n {\displaystyle {\$$sqrt${$n}}$ 조각 각각의 내부 점을 단조롭게 방문하는 순진한 경로를 사용하여$\beta$ ${\displaystyle \le }$ ${\displaystyle 2}$ ${\displaystyle \beta \leq 2}$입니다.
• 증명된 L ${\displaystyle n_{}^{}}$ ∗ ≤ ${\displaystyle \sqrt{2}}$ n${\displaystyle }$+ ${\displaystyle 1.75}$ ${\displaystyle L_{n}^{*}\leq {\sqrt {2n}}$ + $1.75$ $따라서$ β${\displaystyle }$≤ ${\displaystyle 2}${\$displaystyle \leq${\$sqrt {2$ 나중에 Karloff(1987)에 의해 개선된 $\beta$ ${\displaystyle \le }$ ${\displaystyle$ \$leq 0$
• 피쳐는^[45] $\beta {\displaystyle }$ ${\displaystyle \le }$ ${\displaystyle 0.73}$의 상한을 나타냈습니다${\displaystyle .}$ ${\displaystyle \beta \leq 0.73\dots$ $\}.$

하한값

• $E{\displaystyle }$[${\displaystyle {}_{}^{}}$ ${\displaystyle n_{}^{}}$ ∗${\displaystyle {}_{}^{}}$] ${\displaystyle \mathbb {E} [L_{n}^{*}}}$이(가)$$ 0 {\$displaystyle$X_{$0}}$과(와) 가장 가까운 점 ${\displaystyle {Xi}_{}}$ ≠ X ${\displaystyle 0_{}}${\$displaystyle X_{i}\neq X_{0}}$ 사이의 $거리$의$$n {\displaystyle $n}$보다 크다는 것을 관찰하면 (짧은 계산 후) 얻을 수 있습니다$.$

${\displaystyle \mathbb {E} [L_{n}^{*}]\geq {\tfrac {1}{2}}{\sqrt {n}}}.$

• $E{\displaystyle }$[${\displaystyle {}_{}^{}}$ ${\displaystyle n_{}^{}}$∗${\displaystyle {}_{}}$${\displaystyle \mathbb {E} [L_{n}^{*}}}$가 $X$ ${\displaystyle 0_{}}$ ${\$$displaystyle {\tfrac$ {$1}{2}}$과 X 0 {\$displaystyle X_{$${\displaystyle 0_{}}$$}},$ X j ≠ X ${\displaystyle 0_{}}$ ${\displaystyle X_{i},$보다 크고$,$ 이는 다음 값을 제공합니다.

${\displaystyle \mathbb {E} [L_{n}^{*}]\geq \left ({\tfrac {1}{4}}+{\tfrac {3}{8}\right){\sqrt {n}}={\tfrac {5}{8}}{\sqrt {n}}}$

• 현재^[46] 가장 좋은 하한은

${\displaystyle \mathbb {E} [L_{n}^{*}]\geq ({\tfrac {5}{8}}+{\tfrac {19}{5184}}){\sqrt {n}}}$

• Hold와 Karp는 ${\displaystyle {Ln}_{}^{}}$ ∗ ${\displaystyle L_{n}^{*}}$에 대한 수치 하한을 제공하는 다항식 시간 알고리듬을 제공했으며$,$ 따라서 최대 1% 또는 그 미만으로 보이는 $\beta {\displaystyle (}$≃ ${\displaystyle {Ln}_{}^{}}$ ∗${\displaystyle {}_{}^{}}$/ ${\displaystyle n)}$ ${\displaystyle \beta (\simeq L_{n}^{*}/{\sqrt {n}})}$에 대해 수치 하한을 제공했습니다.특히 데이비드 S. 존슨은^[49] 컴퓨터 실험을 통해 하한값을 얻었습니다.

${\displaystyle L_{n}^{*}\gtrsim 0.7080{\sqrt {n}}+0.522,}$

여기서 0.522는 이웃이 더 적은 정방형 경계 근처의 점들에서 나오고, 크리스틴 L. 발렌주엘라와 안토니아 J. 존스는 다음과^[50] 같은 다른 수치 하한을 구했습니다.

${\displaystyle L_n^{}}$ ∗ ≳ ${\displaystyle 0_{}^{}\mathrm{.}7078n}$+ ${\displaystyle 0.551}$ ${\displaystyle L_{n}^{*}\gtrsim 0.7078{\sqrt {n}}+0.551}$입니다$.$

계산 복잡도

문제는 NP-hard인 것으로 나타났으며(정확히는 복잡도 클래스 FP에^NP 대해 완전함; 함수 문제 참조), 의사결정 문제 버전("비용과 숫자 x를 고려할 때 x보다 저렴한 왕복 경로가 있는지 여부 결정")은 NP-완전합니다.병목 여행 세일즈맨 문제도 NP-hard입니다.문제는 도시가 유클리드 거리가 있는 평면에 있는 경우뿐만 아니라 다른 많은 제한적인 경우에도 NP-hard로 남아 있습니다.각 도시를 '단 한 번' 방문하는 조건을 제거한다고 NP-경도가 제거되는 것은 아닙니다. 평면적인 경우 각 도시를 한 번만 방문하는 최적의 관광이 있기 때문입니다(그렇지 않으면 삼각형 부등식으로 인해 반복 방문을 건너뛰는 지름길로 인해 관광 길이가 증가하지 않습니다).

근사의 복잡성

일반적인 경우, 최단 여행 세일즈맨 투어를 찾는 것은 NPO 완료입니다.^[51]거리 측정이 메트릭이면(따라서 대칭인) 문제는 APX-완전이^[52] 되고 크리스토피데스와 세르듀코프의 알고리즘은 1.5 이내로 근사합니다.^[53][54][9]

거리가 1과 2로 제한된 경우(단, 메트릭임) 근사 비율은 8/7이 됩니다.^[55]삼각형 부등식이 존재하는 비대칭적인 경우, 최근까지 로그 성능 보장만 알려져 있었습니다.^[56]2018년에는 Svensson, Tarnawski 및 Vegh에 의해 상수 인자 근사치가 개발되었습니다.^[57]Traub and Vygen에 의해 가장 잘 알려진 현재 알고리즘은 ${\displaystyle 22}$ +${\displaystyle }$ε ${\displaystyle 22+\varepsilon}$의 성능비를 달성합니다$.$ 근사 한계에서 가장 잘 알려진 것은 75/74입니다.

최장 여행 세일즈맨 투어를 찾는 최대화 문제는 대략 63/38 이내입니다.^[60]거리 함수가 대칭인 경우, 결정론적 알고리즘에 의해 4/3 이내, 무작위 알고리즘에 의해 ${\displaystyle \frac{125}{}}$(${\displaystyle 33}$ +${\displaystyle }$ε${\displaystyle )}$ ${\displaystyle {\tfrac {1}{25}}(33 +\varepsilon )}$ 이내에서 가장 긴 여행을 근사화할 수 있습니다.

사람과 동물의 성능

TSP, 특히 유클리드 변형 문제는 인지 심리학 연구자들의 관심을 끌었습니다.인간은 선형에 가까운 방식으로 거의 최적의 솔루션을 신속하게 생산할 수 있으며, 노드가 10~20개인 그래프의 경우 효율이 1% 감소하고 노드가 120개인 그래프의 경우 효율이 11% 감소하는 성능을 제공할 수 있습니다.^[63][64]인간이 문제에 대해 거의 최적에 가까운 해결책을 정확하게 생성하는 명백한 용이성으로 인해 연구자들은 인간이 하나 이상의 휴리스틱을 사용한다는 가설을 세웠고, 가장 인기 있는 두 이론은 거의 틀림없이 볼록-헐 가설과 교차 회피 휴리스틱입니다.^[65][66][67]그러나 추가적인 증거에 따르면 인간의 성과는 상당히 다양하며 그래프 기하학뿐만 아니라 개인차도 작업의 성과에 영향을 미치는 것으로 보입니다.^[68][69][70]그럼에도 불구하고, 결과는 TSP의 컴퓨터 성능이 이러한 문제에 대해 인간이 사용하는 방법을 이해하고 모방함으로써 향상될 수 있음을 시사하며, ^[71]또한 인간 사고의 메커니즘에 대한 새로운 통찰력을 이끌어냈습니다.^[72]Journal of Problem Solving의 첫 번째 호는 TSP에 대한 인간의 수행에 대한 주제를 다루었고,^[73] 2011년 리뷰는 이 주제에 대한 수십 개의 논문을 나열했습니다.^[72]

2011년 어린이 책인 "비둘기가 버스를 운전하게 내버려 두라!"의 이름을 딴 "비둘기가 버스를 운전하게 하라"는 제목의 동물 인지에 관한 연구는 여행 판매원 문제와 관련하여 실험실에서 여러 공급기 사이의 비둘기의 비행 패턴을 연구함으로써 비둘기의 공간 인지를 조사했습니다.첫 번째 실험에서 비둘기들은 실험실 구석에 배치되어 콩이 들어있는 근처 사료통으로 날아갈 수 있었습니다.연구원들은 비둘기들이 다음에 어떤 먹이를 선택할지를 결정하기 위해 대부분 근접성을 사용했다는 사실을 발견했습니다.두 번째 실험에서는 비둘기들이 모든 피더를 방문해야 한다면 기회가 있을 때마다 가장 가까운 피더로 비행하는 것이 비효율적일 수 있도록 피더를 배치했습니다.두 번째 실험의 결과는 비둘기들이 여전히 근접성에 기반한 해결책을 선호하면서도 "접근성에 기반한 효율적인 경로와 덜 효율적인 경로 사이의 여행 비용의 차이가 커질 때 경로를 따라 몇 단계 앞서 계획할 수 있다"^[74]는 것을 나타냅니다.이러한 결과는 일부 비 영장류가 복잡한 이동 경로를 계획할 수 있다는 것을 입증한 비 영장류에 대한 다른 실험과 일치합니다.이는 영장류가 아닌 사람들이 비교적 정교한 공간 인지 능력을 가지고 있을 수 있음을 시사합니다.

자연연산

음식 공급원의 공간적 구성을 제시할 때 아메보이드 피사룸 다두증은 음식 공급원 간의 효율적인 경로를 만들기 위해 형태를 조정하며, TSP에 대한 근사적인 해결책으로도 볼 수 있습니다.^[75]

벤치마크

TSP 알고리즘의 벤치마크에 대해서는 TSPLIB는^[76] TSP의 샘플 인스턴스 라이브러리이며 관련 문제는 TSPLIB 외부 참조를 참조하십시오.실제 도시의 목록과 실제 인쇄 회로의 레이아웃이 대부분입니다.

대중문화

• Timothy Lanzone 감독의 Traveling Salen은 컴퓨터 과학 역사상 가장 다루기 힘든 문제를 풀기 위해 미국 정부에 의해 고용된 4명의 수학자들의 이야기입니다: P vs. NP.^[77]
• 수학자 밥 보쉬는 TSP 파트라는 하위 장르에서 이 문제의 해결책을 사용합니다.^[78]

참고 항목

• 캐나다 여행자 문제
• 정확한 알고리즘
• 경로 점검 문제(일명 "중국 집배원 문제")
• TSP 문제 설정
• 쾨니히스베르크의 7개 다리
• 슈타이너 여행 판매원 문제
• 써브웨이 챌린지
• 튜브 챌린지
• 차량 라우팅 문제
• 그래프 탐색
• 중국집배원 혼혈문제
• 아크 루팅
• 제설기 라우팅 문제

메모들

참고문헌

추가열람

외부 링크

• Waterloo 대학의 Wayback Machine 여행 세일즈맨 문제(2013년 12월 17일 보관)
• TSPLIB, 하이델베르크 대학의 TSP 예제
• Wolfram 데모 프로젝트에 참여한 존 맥루언의 여행 세일즈맨 문제
• TSP 시각화 도구