분할 정복 기법을 이용한 외판원 문제 근사 알고리듬 > 논문 검색첫페이지로 이동

본문에서는 분할 정복 기법(divide and conquer method)을 이용하여 TSP(traveling salesman problem)의 해를 근사하는 방법을 제안한다. 분할 정복 기법을 이용하기 위해서 주어진 꼭짓점(vertex)들을 적당히 분할하는 방법이 필요하다. 이에 서로 다른 두 꼭짓점을 잇는 변(edge)의 가중치(weight)를 변수로 하는 밀도 함수를 적용하여 밀도가 가장 높은 지점에서부터 일정 이하의 거리(변의 가중치)를 가지는 꼭짓점들을 한 집단으로 묶는 방법을 이용하였다. 해당 방법을 이용했을 때 밀도 함수에 이용되는 상수 k의 값만 잘 잡혀있다면, 적절히 분할되어 실제 해와 유사한 값을 보였으며, 이 오차율은 0.033 미만으로 확인되었다. 이는 본문에서 제안하는 분할 정복 기법을 이용하는 근사 방법은 사용하기에 충분한 성능을 보인다는 것을 의미한다. 이 방법을 통해 실제 상황의 문제를 해결하였을 때, 오차율은 약 0.009 정도로 아주 낮은 수치를 보였다.

In this text, we propose a method to approximate the solution of the traveling salesman problem (TSP) using the divide and conquer method. To use the divide and conquer method, a method of appropriately dividing the given vertices is required. Accordingly, a density function using the weight of the edges connecting two different vertices as a variable was applied to group vertices having a distance (weight of the sides) below a certain distance from the highest density point. If only the value of the constant k used for the density function was well determined when using the method, it was properly divided and showed a value similar to the actual solution, and this error rate was confirmed to be less than 0.033. This means that the approximation method using the segmentation conquest technique proposed in the text shows sufficient performance to use. When the problem of the actual situation was solved through this method, the error rate was very low, about 0.009.