본 논문은 외판원 문제의 해를 쉽게 구하는 알고리즘을 제안하였다. 사전에, n(n-1)개의 데이터에 대해 각 정점에서의 거리 오름차순으로 정렬시켜 최단거리 상위 10개인 10n개를 결정하였다. 첫 번째로, 각 정점 $v_i$의 최단거리인 $r_1=d\{v_i,v_j\}$로 연결된 부분경로를 하나의 지역으로 결정하였다. $r_2$에 대해서는 지역 내 정점간 간선은 무조건 연결하고, 지역간 간선은 연결 규칙을 적용하였다. 전체적으로 하나의 해밀턴 사이클이 형성될 때까지 $r_3$ 부터는 지역간 간선만 연결하는 방법으로 정복하였다. 따라서 제안된 방법은 지역분할정복 방법이라 할 수 있다. 실제 지도상의 도시들인 TSP-1(n=26) TSP-2(n=42)와 유클리드 평면상에 랜덤하게 생성된 TSP-3(n=50)에 대해 제안된 알고리즘을 적용한 결과 TSP-1과 TSP-2는 최적해를 구하였다. TSP-3에 대해서는 Valenzuela와 Jones의 결과보다 거리를 단축시킬 수 있었다. 전수탐색 방법은 n!인데 반해, 제안된 알고리즘의 수행복잡도는 $O(n^2)$이며, 수행횟수는 최대 10n이다.
본 논문은 외판원 문제의 해를 쉽게 구하는 알고리즘을 제안하였다. 사전에, n(n-1)개의 데이터에 대해 각 정점에서의 거리 오름차순으로 정렬시켜 최단거리 상위 10개인 10n개를 결정하였다. 첫 번째로, 각 정점 $v_i$의 최단거리인 $r_1=d\{v_i,v_j\}$로 연결된 부분경로를 하나의 지역으로 결정하였다. $r_2$에 대해서는 지역 내 정점간 간선은 무조건 연결하고, 지역간 간선은 연결 규칙을 적용하였다. 전체적으로 하나의 해밀턴 사이클이 형성될 때까지 $r_3$ 부터는 지역간 간선만 연결하는 방법으로 정복하였다. 따라서 제안된 방법은 지역분할정복 방법이라 할 수 있다. 실제 지도상의 도시들인 TSP-1(n=26) TSP-2(n=42)와 유클리드 평면상에 랜덤하게 생성된 TSP-3(n=50)에 대해 제안된 알고리즘을 적용한 결과 TSP-1과 TSP-2는 최적해를 구하였다. TSP-3에 대해서는 Valenzuela와 Jones의 결과보다 거리를 단축시킬 수 있었다. 전수탐색 방법은 n!인데 반해, 제안된 알고리즘의 수행복잡도는 $O(n^2)$이며, 수행횟수는 최대 10n이다.
This paper introduces a 'divide-and-conquer' algorithm to the travelling salesman problem (TSP). Top 10n are selected beforehand from a pool of n(n-1) data which are sorted in the ascending order of each vertex's distance. The proposed algorithm then firstly selects partial paths that are interconne...
This paper introduces a 'divide-and-conquer' algorithm to the travelling salesman problem (TSP). Top 10n are selected beforehand from a pool of n(n-1) data which are sorted in the ascending order of each vertex's distance. The proposed algorithm then firstly selects partial paths that are interconnected with the shortest distance $r_1=d\{v_i,v_j\}$ of each vertex $v_i$ and assigns them as individual regions. For $r_2$, it connects all inter-vertex edges within the region and inter-region edges are connected in accordance with the connection rule. Finally for $r_3$, it connects only inter-region edges until one whole Hamiltonian cycle is constructed. When tested on TSP-1(n=26) and TSP-2(n=42) of real cities and on a randomly constructed TSP-3(n=50) of the Euclidean plane, the algorithm has obtained optimal solutions for the first two and an improved one from that of Valenzuela and Jones for the third. In contrast to the brute-force search algorithm which runs in n!, the proposed algorithm runs at most 10n times, with the time complexity of $O(n^2)$.
This paper introduces a 'divide-and-conquer' algorithm to the travelling salesman problem (TSP). Top 10n are selected beforehand from a pool of n(n-1) data which are sorted in the ascending order of each vertex's distance. The proposed algorithm then firstly selects partial paths that are interconnected with the shortest distance $r_1=d\{v_i,v_j\}$ of each vertex $v_i$ and assigns them as individual regions. For $r_2$, it connects all inter-vertex edges within the region and inter-region edges are connected in accordance with the connection rule. Finally for $r_3$, it connects only inter-region edges until one whole Hamiltonian cycle is constructed. When tested on TSP-1(n=26) and TSP-2(n=42) of real cities and on a randomly constructed TSP-3(n=50) of the Euclidean plane, the algorithm has obtained optimal solutions for the first two and an improved one from that of Valenzuela and Jones for the third. In contrast to the brute-force search algorithm which runs in n!, the proposed algorithm runs at most 10n times, with the time complexity of $O(n^2)$.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 해밀턴 사이클(Hamiltonian cycle)의 특별한 경우인 외판원 문제 (travelling salesman problem, TSP)의 최적 해를 찾는 알고리즘을 제안한다. TSP는 n개의 도시 (노드)가 존재할 경우, 한 도시에서 출발하여 나머지 n-1개의 도시들을 최단거리로 방문하고 다시 출발 도시로 되돌아오는 문제이다.
본 논문은 지역 분할정복법으로 TSP의 최적 해에 가능한 가까운 해를 구하는 알고리즘을 제안한다. 제안된 방법은 Valenzuela와 Jones[10]의 방법과는 차이가 있다.
본 논문은 현재까지 수학분야의 미해결 난제로 알려진 TSP 문제에 대해 최적 해에 가장 근사한 해를 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 사전에 n(n-1)개 데이터에 대해 각 정점에 대해 거리의 오름차순으로 정렬시켜 상위 10개를 선택하였다.
제안 방법
제안된 알고리즘은 사전에 n(n-1)개 데이터에 대해 각 정점에 대해 거리의 오름차순으로 정렬시켜 상위 10개를 선택하였다. 결국, 제안된 알고리즘은 10n개의 데이터를 적용해 TSP 문제의 해를 구하였다.
두 번째로, r2데이터에 대해 지역 내부 정점들 간 (inner local area)은 연결하며, 지역간 정점들 (inter local area)은 “연결 규칙”을 적용하고 지역에서 해제시키는 방법을 적용한다.
첫번째로, 각 정점 vi의 최단거리인r1 = d{vi,vj}를 연결하여 형성된 부분 경로를 하나의 지역으로 결정하였다. 두번째로, r2에 대해서는 지역 내 정점들 간에는 무조건 연결하고, 지역 간 정점들 간에는 연결 규칙을 적용하여 연결하였다. r3부터는 하나의 해밀턴 사이클이 형성될 때까지 지역 간 연결을 수행하였다.
본 장에서는 가장 인접한 정점들 간을 연결한 지역으로 분할하고, 분할된 지역을 연결하는 방법을 제안한다. 제안된 알고리즘의 특징은 초기 해인 해밀턴 사이클을 구하지 않는다.
세 번째로, 해밀턴 사이클이 형성될 때까지 r3부터 순서대로 지역간 정점들 (inter local area)에 대해 “연결 규칙”을 적용하고 지역에서 해제시키는 방법을 적용한다.
각 정점에서의 거리를r1,r2,…,r10이라 하자. 제안된 방법은 n개의 정점 전체를 각 정점에서의 최단거리 정점들로 구성된 인접 지역들로 분할하고 분할된 지역들 간을 연결하여 최종적으로 하나의 해밀턴 사이클을 얻는 방법이다.
본 논문은 현재까지 수학분야의 미해결 난제로 알려진 TSP 문제에 대해 최적 해에 가장 근사한 해를 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 사전에 n(n-1)개 데이터에 대해 각 정점에 대해 거리의 오름차순으로 정렬시켜 상위 10개를 선택하였다. 결국, 제안된 알고리즘은 10n개의 데이터를 적용해 TSP 문제의 해를 구하였다.
본 장에서는 가장 인접한 정점들 간을 연결한 지역으로 분할하고, 분할된 지역을 연결하는 방법을 제안한다. 제안된 알고리즘의 특징은 초기 해인 해밀턴 사이클을 구하지 않는다. 반면에, 사전처리 단계로 n(n-1)개의 데이터에 대해 정점에서의 거리 데이터를 오름차순으로 정렬시켜 상위 10개 (top 10) 최단거리 정보인 n ×10개의 데이터만을 추출한다.
본 알고리즘에는 지역분할정복 기법이 적용되었다. 첫번째로, 각 정점 vi의 최단거리인r1 = d{vi,vj}를 연결하여 형성된 부분 경로를 하나의 지역으로 결정하였다. 두번째로, r2에 대해서는 지역 내 정점들 간에는 무조건 연결하고, 지역 간 정점들 간에는 연결 규칙을 적용하여 연결하였다.
대상 데이터
TSP-2의 최적 해는 1번부터 42번까지 순서대로 방문하고 다시 1번으로 되돌아오는 경우로 12,345mile = 699이다. TSP-3 데이터는 50개의 정점을 유클리드 좌표로 랜덤하게 생성한 자료이며, 실제 거리의 단위는 제시되어 있지 않아 mm로 재 계산하였다. Valenzuela와 Jones[10]은 TSP-3 데이터에 대해 결정론적 이등분법으로 8개의 지역으로 분할하여 1번부터 50번까지 순서대로 방문하고 다시 1번으로 되돌아오는 경우로 최단거리는 1,615mm를 제시하였다.
본 논문에서는 두 도시 i,j 간의 거리d{i,j}=d{j,i}이며, d{i,j}는 존재하지 않는 대칭행렬을 대상으로 한다.
실험에 적용된 데이터는 Dantzig, Fulkerson과 Johnson[17]이 제시한 TSP-2와 Valenzuela와 Jones[10]가 제시한 TSP-3로 그림 3에 제시되어 있다.
알고리즘을 설명하기 위해 그림 1의 Pleines [16]가 제안한 데이터를 활용한다. TSP-1은 유럽의 26개 도시를 여행하는 경우로 각 도시를 번호로 표기하였다.
이론/모형
본 알고리즘에는 지역분할정복 기법이 적용되었다. 첫번째로, 각 정점 vi의 최단거리인r1 = d{vi,vj}를 연결하여 형성된 부분 경로를 하나의 지역으로 결정하였다.
성능/효과
TSP-3 데이터에 대해 제안된 알고리즘을 적용한 결과는 표 3의 상위 10 거리정보를 획득하여 그림 5와 같이 수행되었다. TSP-3에 제안된 알고리즘을 적용한 결과 얻은 해는 1,375mm로 Valenzuela와 Jones[10]가 제시한 해 1,615mm에 비해 240mm를 감소시켰다. 그러나 이 값이 최적해 인지 여부는 검증되지 않았다.
제안된 알고리즘을 적용한 결과 TSP-1은 rS에서, TSP-2는 r6에서, TSP-3는 r4에서 해를 구할 수 있었다. 결국, 10n개 데이터 들 중에서 최대8n개의 데이터만이 활용됨을 알 수 있다.
후속연구
결국, 본 논문은 TSP 문제의 해를 빠르게 구할 수 있음을 검증하였다. 따라서 본 알고리즘을 TSP 문제의 최선의 알고리즘으로 적용할 수 있을 것이다.
따라서 대규모의 TSP에 대해서는 초기해를 구하기 위해 n(n-1)개의 모든 노드들 간의 거리를 대상으로 하면 많은 시간이 소요된다. 또한, 모든 노드들 간의 거리가 TSP의 최적해인 해밀턴 사이클 간선들로 선택되지 않아 최적해를 구하는데 불필요한 시간만 소요된다. 해밀턴 사이클은 모든 정점의 차수 (degree)는 dG(vi)=2이며, 서로 연결되어 있어 간선의 개수는 |e|=n이다.
질의응답
핵심어
질문
논문에서 추출한 답변
정확한 방법 (exact method)과 근사 방법에 대한 설명은?
TSP의 해법 (solution method)은 정확한 방법 (exact method)과 근사 방법 (approximate method)으로 분류된다. [7,8] 정확한 방법은 최적해 (optimal solution)를 얻음을 보장하기 위해 n개의 정점들 사이의 간선 대칭행렬에 대해 n!회 수행된다. 반면에, 근사법은 발견적 방법 또는 분할정복법으로 최적 해를 찾음을 보장하지는 못하지만 적당히 좋은 해법을 빠르게 찾기 위해 일반적으로 사용 된다. [7] 발견적 방법은 초기해로 해밀턴 사이클을 형성하는 구성단계, 해를 개선하는 지역개선단계, 지역적으로 최적화된 경로를 개선하는 확장단계로 순으로 진행된다.
TSP의 해법은?
TSP는 n!의 전수 탐색 방법 이외에는 효율적인 해법이 알려지지 않은 수학분야의 최대 난제들 가운데 하나로 남아 있다.[3-5] 2010년 영국 런던대 연구진은 “컴퓨터가 수일 동안 풀어야만 하는 TSP 문제에 대해 뒤영벌 (a bumblebee)은 컴퓨터 도움 없이도 매일 꿀을 수집하기 위해 꽃들을 찾아다닐 때 에너지 소비를 최소화하기 위해 최단거리를 찾아다니는 TSP 문제를 해결하고 있다.
외판원 문제는 어떤 경우인가?
본 논문에서는 해밀턴 사이클(Hamiltonian cycle)의 특별한 경우인 외판원 문제 (travelling salesman problem, TSP)의 최적 해를 찾는 알고리즘을 제안한다. TSP는 n개의 도시 (노드)가 존재할 경우, 한 도시에서 출발하여 나머지 n-1개의 도시들을 최단거리로 방문하고 다시 출발 도시로 되돌아오는 문제이다.
참고문헌 (17)
A. Likas and V. T. Paschos, "A Note on a New Greedy-solution Representation and a New Greedy Parallelizable Heuristic for the Traveling Salesman Problem," Chaos, Solutions and Fractals, Vol. 13, pp. 71-78, 2002, doi:10.1016/S0960-0779(00)00227-7.
A. Schrijver, "On the History of Combinatorial Optimization (till 1960)," in Handbook of Discrete Optimization'' (K. Aardal, G.L. Nemhauser, R. Weismantel, eds.), Elsevier, Amsterdam, pp. 1-68, http://homepages.cwi.nl/-lex/files/histco.pdf, 2005.
J. Denzinger, D. Fuchs, M. Fuchs, and M. Kronenburg, "The Teamwork Method for Knowledge-Based Distributed Search: The travelling salesman problem," University of Kaiserslautern, 2008.
S. Vempala, "18.433 Combinatorial Optimization: NP-completeness," http://ocw.mit.edu/NR/rdonlyres/Mathematics/18-433Fall2003/778D00DB-F21C-486C-ABD8-F5E7F5C929C3/O/I20.pdf, 2003.
L. Stougie, "2P350: Optimaliseringsmethoden," http://www.win.tue.nl/-leen/OW/2P350/Week8/week8.pdf, College Wordt ggeven op vinjdagmiddag, 2001.
M. Lihoreau, L. Chittka, and N. E. Raine, "Travel Optimization by Foraging Bumblebees Through Readjustments of Traplines after Discovery of New Feeding Locations," The American Naturalist, Vol. 176, No. 6, pp. 744-757, 2010, doi:10.1086/657042.
E. Charniak and M. Herlihy, "CSC 751 Computational Complexity: Local Search Heuristics," Department of Computer Science, Brown University, 2008.
D. S. Johnson and L. A. McGeoch, "The Traveling Salesman Problem and Its Variations," Kluwer Academic Publishers, pp. 369-443, 2002.
A. Kazakov, R. A. Watson, and M. Zwolinski, "Traveling Salesman Problem: Local Search and Divide and Conquer Working Together," Independent Research Review, pp. 1-8, University of Southmapton, 2009.
C. L. Valenzuela and A. J. Jones, "Evolutionary Divide and Conquer (I): A Novel Genetic Approach to the TSP," Evolutionary Computation, Vol. 1, No. 4, pp. 313-333, 1994, doi:10.1162/evco.1993.1.4.313.
S. Lin, "Computer Solutions of the Traveling Salesman Problem," Bell System Technical Journal, Vol. 44, pp. 2245-2269, 1965, doi:10.1002/j.1538-7305.1965.tb04146.
L. H. Chuin, "IS 703: Decision Support and Optimization," School of Information Systems," Department of Computer Science, Brown University, 2008.
J. Pleines, "ZIP-Methode: ein Kombinatorischer Ansatz zur Optimalen Losung Allgemeiner Traveling-Salesman-Problem (TSP)," Konnen bekannte Losungen nicht nur auf Gesamtgrphen sondern auf Teilgraphen angewandt werden, so bringt die ZIP-Methode den entscheidenden Quantensprung der rechentechnischen Vereinfachung, http://www.jochen-pleines.de/download /ZIP2006.pdf, 2006.
G. Dantzig, R. Fulkerson, and S. Johnson, "Solution of a Large-scale Traveling-Salesman Problem," The Rand Corporation, http://www.cse.wustl.edu/-chen/7102/TSP.pdf, 1954.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.