Robot Tour Optimization

상위 문서: 알고리즘 설계와 분석

개요

Robot Tour Optimization 문제란, 어떠한 공장에서 납땜 인두와 같은 도구가 장착된 로봇팔이 주어졌을 때, 회로 기판을 제조할 때는 모든 칩과 다른 부품들을 기판에 고정하기 위해서 취해야 하는 가장 효율적인 동선을 찾는 것이다. 더 구체적으로, 각 칩에는 보드에 납땜되어야 하는 접점들의 집합이 있다. 이 작업을 위해 로봇 팔을 프로그래밍하려면, 로봇이 첫 번째 접점을 방문(그리고 납땜)하고, 그다음 두 번째, 세 번째 접점을 방문하는 식으로 작업이 끝날 때까지 동선을 구성해야 하며, 또한 모든 작업을 마친 후에는 다음 보드를 준비하기 위해서 첫 번째 접점으로 되돌아가므로, 로봇팔의 동선은 닫힌 순회 동선이 된다. 이때 두 점 사이를 이동하는 시간은 그 거리와 비례한다. 따라서 요약하자면 아래와 같은 알고리즘 문제이다.

입력: 평면 위의 n개 점으로 이루어진 집합 S.
출력: 집합 S의 각 점을 방문하는 가장 짧은 닫힌 순회 동선은 무엇인가?

알고리즘

Nearest Neighbor Tour

해당 문제에 대해 가장 쉽게 취할 수 있는 접근법은 현재 로봇팔이 위치한 접점에서 가장 가까이에 위치한 접점을 다음 접점으로 선택하는 것이다. 이는 아래와 같은 수도 코드(pseudo code)를 통해서 나타낼 수 있다.

파일:Figure 1. Nearest Neighbor Tour is Wrong.png

Figure 1. Nearest Neighbor Tour is Wrong

Pick and visit an initial point [math]\displaystyle{ p_0 }[/math]
[math]\displaystyle{ p = p_0 }[/math]
[math]\displaystyle{ i=0 }[/math]
While there are still unvisited points
    [math]\displaystyle{ i=i+1 }[/math]
    Let [math]\displaystyle{ p_i }[/math] be the closest unvisited point to [math]\displaystyle{ p_{i-1} }[/math]
    Visit [math]\displaystyle{ p_i }[/math]
Return to [math]\displaystyle{ p_0 }[/math] from [math]\displaystyle{ p_i }[/math]

하지만 이러한 단순한 접근법은 틀렸다. Figure 1은 이를 증명하는 반례이다.

Closest Pair Tour

해당 알고리즘은 체인(chain)이라는 개념을 사용한다. 체인은 연결된 점들의 경로를 의미하여, 시작과 끝에 끝점(endpoint)이 존재한다. 이때 알고리즘의 처음에는 모든 점은 길이가 0인 체인으로 간주된다. 알고리즘의 매 단계 마다 서로 다른 체인에 속한 끝점 들 중, 가장 가까운 쌍을 골라서 연결한다. 이때 주의해야 할 것은 모든 점이 하나의 체인으로 합쳐지기 전까지는 체인의 양 끝점이 연결되어 해당 알고리즘이 조기 종료되지 않도록 하는 것이다. 만약 하나의 체인에 모든 점이 속한다면, 해당 체인의 양 끝점을 서로 연결하여 사이클을 종료한다. 이는 아래와 같은 수도 코드를 따른다.

Let [math]\displaystyle{ n }[/math] be the number of points in the set 
For [math]\displaystyle{ i = 1 }[/math] to [math]\displaystyle{ n - 1 }[/math] do
    [math]\displaystyle{ d=\infty }[/math]
For each pair of endpoints [math]\displaystyle{ (x, y) }[/math] of partial paths
    If [math]\displaystyle{ dist(x, y) \le d }[/math] then //떨어져 있는 체인 사이의 거리가 최소가 되도록 하는 두 접점 찾기
        [math]\displaystyle{ x_m =x,y_m =y,d=dist(x,y) }[/math]
    Connect [math]\displaystyle{ (x_m, y_m) }[/math] by an edge //해당 두 접점을 이어 같은 체인에 속하도록 한다.
Connect the two endpoints by an edge.

Figure 2. Closest Pair Tour is Wrong

Figure 2. Closest Pair Tour is Wrong

이는 figure 1의 경우에는 잘 맞아 떨어지는 것을 관찰할 수 있다. 하지만 이는 Figure 2의 경우에 대해서는 실패를 한다는 것을 관찰할 수 있다. 즉, 해당 알고리즘은 최선의 결과를 보장하지 않는다. 이를 통해서 알 수 있는 것은, 지역적으로 가장 가까운 연결이 항상 전역적으로 좋은(최적) 경로를 보장하진 않는다는 것이다.

해당 알고리즘의 장점은 구현이 간단하고 직관적이므로 많은 상황에서 “그럴듯한” 해를 빨리 만든다는 것이다. 하지만 최적의 해를 보장하지 않으므로 구조에 따라 나쁜 해를 만들 수 있다는 단점이 있다. 해당 알고리즘의 시간 복잡도를 계산하면, 각 단계 마다 끝점의 쌍을 전수조사 하므로 대략 O(n³)이라고 볼 수 있다. 그 이유는 n개의 단계에서 각 단계의 비용이 후보쌍의 수에 비례하므로 O(n²)만큼 소요되기 때문이다.

A Correct Algorithm: Exhaustive Search

가장 직관적이고 정확함을 보장할 수 있는 알고리즘은 존재하는 모든 경우의 수에 대하여 모두 조사하는 것이다. 이는 아래와 같은 수도 코드에 따라 작동한다.

[math]\displaystyle{ d=\infty }[/math]
For each of the [math]\displaystyle{ n! }[/math] permutations [math]\displaystyle{ P_i }[/math] of the [math]\displaystyle{ n }[/math] points //n개의 항으로 이루어진 n!개의 순열에 대하여,
If ([math]\displaystyle{ P_i \le d }[/math]) then //최소값을 찾는다.
    [math]\displaystyle{ d = cost(P_i) }[/math] and [math]\displaystyle{ P_{min} = P_i  }[/math] 
Return [math]\displaystyle{ P_{min} }[/math]

위 알고리즘을 이해하는 것은 어렵지 않다. 하지만 해당 알고리즘의 문제는 매우 느리다는 것이다. 시간 복잡도가 O(n!)이기 때문에, 만약 입력의 크기 10을 넘어간다면 실행하는 것은 점점 불가능에 가까워 진다. 따라서 이는 정확하지만(correct), 효율적이지는 않은(not efficient) 알고리즘이다.