Online 알고리즘 (1) - Online Algorithm

 

하루 24시간 1년 365일 요청을 받아 프로세스들을 진행하고 있는 서버가 존재합니다. 서버는 지속적으로 프로세스를 실행시키기 위한 시간, 컴퓨팅 자원등 프로세스에 대한 정보를 요청으로 받아 서버내의 자원을 분배하여 프로세스를 실행시켜야 합니다. 이 때, 우리는 어떠한 전략, 알고리즘을 이용하여 자원을 분배해야 할까요? 

 

Online 알고리즘은 위와 같은 문제를 효과적으로 풀기 위한 알고리즘입니다. Online 알고리즘에서의 Online의 의미는 '입력을 순차적으로 받으면서 진행하며 돌이킬 수 없는 결정을 하는 것' 을 나타내며, 우리가 흔히 알고있는 인터넷 온라인과는 이론적으로 아무 관련이 없습니다. Online의 반대말은 Offline이며 의미는 '모든 입력을 시작부터 끝까지 알고 있는 상태로 결정을 하는 것'을 나타냅니다. 앞으로 Offline 알고리즘은 주로 Online 알고리즘 $ALG$의 성능을 비교하기 위한 최적해 $OPT$로 나타내게 될 것입니다.

 

$$ \rho\ge\frac{ALG}{OPT} $$

 

Online 알고리즘의 성능은 Offline 알고리즘을 통해서 얻은 최적해와의 비율로 나타내며 $\rho-\text{competitive ratio}$로 판단할 수 있습니다. 그럼 간단한 알고리즘으로 예를 들어보도록 하겠습니다.

 

로봇이 한대가 있습니다. 로봇은 x-axis의 0에서 움직이기 시작합니다. 이 로봇은 1단위 시간당 1단위 거리를 이동가능하며 어느 방향으로든 x-axis에서 움직입니다. 로봇은 방향을 전환할 수도 있습니다. 그리고 x-axis 위의 어떤 임의의 점에 보석이 존재합니다. 로봇이 보석을 찾기위해 어떻게 움직여야 가장 빠르게 찾을 수 있을까요? 이 문제가 바로 Line search problem 이며 Cow path problem이라고도 합니다.

 

보석이 0으로 부터 d만큼 떨어진 곳에 존재한다고 가정합니다. 만약 로봇이 보석이 어느방향에 있는지 안다면, 로봇은 올바른 방향으로 움직일 수 있습니다. 그리고 시간은 d만큼 걸리겠죠. 이것이 최적의 Offline의 해입니다.

하지만 로봇은 어느 방향에 보석이 있는지 모른다면 어떻게 해야할까요? 양방향을 다 탐색해야합니다. 자연스럽게 지그재그 전략을 사용해야합니다.

 

 

• 처음에는 오른쪽으로 1만큼 이동합니다.
• 만약에 보석이 존재하지 않는다면 왼쪽으로 2만큼 이동합니다. 
• 만약에 보석이 존재하지 않는다면 오른쪽으로 4만큼 이동합니다.
• 전과 다른 반대방향으로 전에 이동한 거리의 2배를 하여 이동합니다.
• 보석을 찾을 때까지 반복합니다.

정리해보자면

 

$$\mathsf{Loc} = \left\{ \begin{array}{ll}2^i , & \text{if } i \text{ is odd}, \\ -(2*2^i), & \text{if } i \text{ is even}, \end{array} \right.$$

 

이러한 doubling 전략은 array resizable 구현 방식을 고려해보면 굉장히 익숙한 방법입니다. 그렇다면 이 전략의 최악의 경우는 어떻게 될까요? 만약 보석이 어떤 단계에서 조금이라도 범위밖에 있다면, 결국 로봇은 원점으로 돌아가고 "잘못된 방향"으로 2배를 이동한 후에 다시 되돌아와서 보석을 얻게 될 것입니다.

 

$$\text{distance }d = 2^i +\epsilon > 2^i \text{}, \text{distance } (-1)^i, \\ 2(1+2+... + 2^i+2^{i+1}) +d \le 2*2^{i+2}+d < 8d + d = 9d$$

 

따라서 doubling 전략은 $9-\text{competitive ratio}$의 알고리즘입니다.