병목 현상 여행 세일즈맨 문제

Bottleneck traveling salesman problem

병목 현상 여행 판매원 문제(병목형 TSP)는 이산형 또는 결합형 최적화의 문제다.문제는 사이클의 최고 중량 에지의 무게를 최소화하는 가중 그래프에서 해밀턴 사이클(각 노드를 정확히 한 번 방문)을 찾는 것이다.[1]처음에는 길모어&고모리(1964)에 의해 약간의 추가적인 제약이 있고, 가핀켈&길버트(1978)에 의해 완전히 일반화되었다.[1][2][3]

복잡성

문제는 NP-hard인 것으로 알려져 있다.이에 대한 의사결정 문제 버전인 "특정 길이의 x에 대해 x보다 긴 에지가 없는 그래프 G에 해밀턴식 사이클이 있는가?"는 NP-완전이다.NP-완전성은 해밀턴 사이클을 찾는 문제로부터의 감소에 의해 즉시 뒤따른다.[4]

알고리즘

병목현상 TSP에서 일반적인 TSP(가장자리 길이의 합을 최소화하는 것이 목표인 경우)로 또 다른 감소는 병목현상 TSP의 알고리즘을 사용하여 병목현상 TSP를 해결할 수 있게 한다. 병목현상 TSP의 가장자리 가중치를 동일한 상대적 순서를 가진 다른 숫자로 대체하면 병목현상 해결책은 그대로 유지된다.변동이 없는또한, 시퀀스의 각 숫자가 더 작은 숫자의 합계를 초과하는 경우 병목현상 해결책도 일반적인 TSP 솔루션과 동일할 것이다.예를 들어, 이러한 결과는 각 가중치를 n으로i 재설정하여 얻을 수 있다. 여기서 n은 그래프에서 정점의 수이고 i는 가중치의 정렬된 순서에서 가장자리의 원래 가중치의 순위다.예를 들어, 이러한 변환에 따라 Hold-Karp 알고리즘을 사용하여 시간 O(n22n)에서 병목현상 TSP를 해결할 수 있다.[1]

또는 최대 x에서 무게의 가장자리의 하위그래프가 해밀턴 사이클을 가질 수 있도록 가장 작은 x에 대한 이진 검색이나 순차 검색을 수행하여 문제를 해결할 수 있다.이 방법은 실행 시간이 해밀턴 사이클을 찾는 시간보다 큰 로그 인자에 불과한 해결책으로 이어진다.[1]

변형

비대칭 병목현상 TSP에서는 노드 A에서 B까지의 중량과 B에서 A까지의 중량이 다른 경우(예: 한 방향으로 교통체증이 있는 두 도시 사이의 이동시간)가 있다.

유클리드 병목현상 TSP, 즉 평면 병목현상 TSP는 병목현상 TSP로, 거리는 일반 유클리드 거리로 한다.그 문제는 여전히 NP-hard로 남아있다.그러나 많은 휴리스틱스는 다른 거리 기능보다 그것에 더 효과적이다.

최대 산란 여행 판매원 문제는 최대 길이를 최소화하기보다는 최소 가장자리 길이를 최대화하는 해밀턴 사이클을 찾는 것이 목표인 여행 판매원 문제의 또 다른 변형이다.그것의 적용 분야는 의료 영상 분석과 시공간 둘 다에서 가까운 단계의 열 증가를 피하기 위한 항공기 제조에서의 금속 작업 단계의 스케줄링이다.모든 에지 길이를 무효화함으로써(또는 결과를 양성으로 유지하기 위해, 충분히 큰 상수에서 모두 빼냄) 병목 TSP 문제의 한 예로 번역할 수 있다.그러나 이러한 변환은 최적의 솔루션을 보존하지만, 그 솔루션에 대한 근사치의 품질을 보존하지는 않는다.[1]

미터법 근사 알고리즘

그래프가 미터법 공간인 경우 최대 에지 중량이 최적값의 2배 이하인 해밀턴 사이클을 찾는 효율적인 근사 알고리즘이 있다.이 결과는 플라이스치너의 정리대로 따르는데, 2Vertex로 연결된 그래프의 사각형에는 항상 해밀턴 사이클이 포함되어 있다.가장 작은 값인 임계값 θ을 쉽게 찾을 수 있어 무게 θ의 가장자리가 2 연결 그래프를 형성한다.병목현상 TSP는 그 자체로 2-연결 그래프로서 적어도 θ의 무게의 가장자리를 포함해야 하기 때문에 병목현상 TSP 중량에 대한 유효한 하한을 제공한다.그러나 기껏해야 θ의 무게 가장자리 서브그래프의 제곱은 해밀턴이다.미터법 공간에 대한 삼각형 불평등에 의해, 그것의 해밀턴 사이클은 최대 2㎛의 무게의 가장자리를 가진다.[5][6]

이 근사비는 가장 잘 가능하다.예를 들어, 가중치가 없는 그래프는 가장자리 가중치를 1로 설정하고 정점의 모든 비인접 쌍 사이의 거리를 2로 설정하여 메트릭 공간으로 변환할 수 있다.이 미터법 공간에서 2보다 높은 비율의 근사치를 사용하여 원본 그래프에 NP-완전한 문제인 해밀턴 사이클이 포함되어 있는지 여부를 확인할 수 있다.[6]

입력이 미터법 공간이라는 가정이 없으면 유한 근사비가 가능하지 않다.[1]

참고 항목

참조

  1. ^ a b c d e f Kabadi, Santosh N.; Punnen, Abraham P. (2007), "The bottleneck TSP", in Gutin, Gregory; Punnen, Abraham P. (eds.), The Traveling Salesman Problem and Its Variations, Combinatorial Optimization, Springer, pp. 697–735, doi:10.1007/0-306-48213-4_15.
  2. ^ Gilmore, P. C.; Gomory, R. E. (1964), "Sequencing a one state-variable machine: A solvable case of the traveling salesman problem", Oper. Res., 12 (5): 655–679, doi:10.1287/opre.12.5.655, JSTOR 167772.
  3. ^ Garfinkel, R. S.; Gilbert, K. C. (1978), "The bottleneck traveling salesman problem: Algorithms and probabilistic analysis", Journal of the ACM, 25 (3): 435–448, doi:10.1145/322077.322086, S2CID 12062434.
  4. ^ Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, A2.3: ND24, p. 212, ISBN 0-7167-1045-5.
  5. ^ Parker, R. Garey; Rardin, Ronald L. (1984), "Guaranteed performance heuristics for the bottleneck traveling salesman problem", Operations Research Letters, 2 (6): 269–272, doi:10.1016/0167-6377(84)90077-4.
  6. ^ a b Hochbaum, Dorit S.; Shmoys, David B. (May 1986), "A unified approach to approximation algorithms for bottleneck problems", Journal of the ACM, New York, NY, USA: ACM, 33 (3): 533–550, doi:10.1145/5925.5933, S2CID 17975253.