확률적 알고리즘

**확률적 알고리즘**(probabilistic algorithm) 또는 **무작위 알고리즘**(randomized algorithm)은 난수를 발생시켜 진행과정을 결정하는 알고리즘이다. 난수를 발생시키는 과정은 흔히 '동전을 던진다'고 표현하며, 실제로는 의사난수 생성기를 사용한다. 알고리즘의 성능을 평균적으로 향상시키기 위해 난수를 사용한다. 난수를 사용하기 때문에 알고리즘의 성능은 확률변수이며, 확률변수의 기댓값이 실제로 원하는 성능이다. 알고리즘 성능의 최악의 경우는 일어날 확률이 극히 작기 때문에 대부분 무시한다.
# 필요성
확률적 알고리즘의 필요성을 설명하기 위해 다음과 같은 예를 생각한다. *n*개의 원소가 들어있는 어떤 배열에서 절반은 *a*이고 나머지 절반은 *b*라고 할 때, 이 배열에서 *a*를 찾는 예를 생각하자. 만약 이것을 배열의 처음부터 순서대로 찾는다면 최악의 경우 n/2번의 연산이 필요하다. (*b*가 배열의 앞에 들어있고, *a*는 뒷 부분에 몰려있는 경우) 마찬가지로 뒤부터 찾는다고 해도 반대의 경우가 있을 수 있다. 혹은 하나씩 건너뛰면서 찾아보는 알고리즘이 있다고 해도 *a*와 *b*가 공교롭게도 원하는 형태와 반대로 배열된 경우에는 모두 n/2번의 연산이 필요하다. 즉 '결정론적 알고리즘'으로는 모든 가능한 입력의 경우에 대하여 빨리 실행된다고 보장할 수가 없다. 그러나 만약 배열에서 임의의 원소를 골라서 검사해보는 방식을 사용하면 '입력이 어떻게 되어있든지' '매우 높은 확률로' 원하는 원소를 찾을 수 있다. 암호학분야에서도 확률적 알고리즘은 매우 중요하다. 예를 들어, A가 어떤 은행에 전송하는 온라인 계좌이체명령을 암호화해서 전송할 때, 악의적 사용자가 A의 명령을 그대로 갈무리했다가 재전송하는 공격을 한다고 가정하자. 이와 같은 재전송 공격에 안전하려면, A와 은행이 프로토콜을 시행할 때 임의의 난수를 발생시켜서 알고리즘의 실행과정이 매번 달라져야 한다. 그러나 이와 같은 용도에 의사난수발생기를 사용한다면, 공격자가 의사난수발생기의 출력값을 예측할 수 있으므로 자연계에서 존재하는 실제 난수를 사용하던지 아니면 암호학적으로 안전한 의사난수발생기를 사용해야만 한다. 참고로 양자컴퓨터에서 돌아가는 모든 알고리즘은 본질적으로 확률적 알고리즘이다. 위의 예제에서 확률적 알고리즘은 언제나 옳은 결과를 내놓지만 실행시간이 오래 걸릴 확률이 약간이나마 존재한다. 어떤 경우에는 '오류가 발생할 확률이 어느 정도 존재하더라도' 알고리즘이 빠르게 실행되는 것을 원할 경우도 있다. 앞의 경우를 라스베가스 알고리즘이라고 하며, 뒤의 경우를 몬테카를로 알고리즘이라고 한다. (몬테카를로 알고리즘은 시뮬레이션에서 사용하는 몬테카를로 방법에서 이름을 따왔다). 모든 라스베가스 알고리즘은 다음과 같은 방법으로 몬테카를로 알고리즘으로 변형할 수 있다. :알고리즘의 실행시간이 미리 지정한 시간을 넘어가면, (틀릴 수도 있는) 임의의 결과값을 출력한다.
# 복잡도
주어진 문제를 풀기 위해 필요한 계산 용량을 연구하는 계산 복잡도 이론에서는, 확률적 알고리즘을 **확률적 튜링 기계**(probabilistic Turing machine)로 모형화한다. 라스베가스 알고리즘과 몬테카를로 알고리즘을 모두 대상으로 삼고, 이와 관련된 여러 가지 복잡도 종류를 연구한다. 가장 단순한 확률적 알고리즘은 RP에 속하는 것이다. RP는 효율적인 (다항시간이라는 뜻) 확률적 알고리즘 (혹은 확률적 튜링기계)가 존재하여 다음 두 가지 조건을 만족하는 판정 문제의 모임이다. * '아니오'에 해당하는 입력은 100% 확실한 확률로 '아니오'라는 결과가 나온다. * '예'에 해당하는 입력은 최소 50%의 확률로 '예'라는 결과가 나온다. 이것과 반대되는 종류는 co-RP라고 한다. '예'와 '아니오' 두가지 답변 모두 오류가 발생할 수 있는 복잡도는 BPP라고 한다. 평균적으로 다항시간안에 올바른 답을 낼 수 있는 문제들의 종류는 ZPP이다. ('평균적'이기 때문에 어떤 입력의 경우에는 알고리즘이 무한히 돌아가면서 결과가 안 나올 수도 있다.) 이와 같은 여러 가지 복잡도 종류에 포함되지 않는다고 생각되는 문제는 NP-난해같은 문제들이며, 이런 문제들은 실제로 앞에서 언급한 복잡도 종류에 포함되지 않는다고 추정된다. 이런 문제들을 풀려면 확률적 알고리즘으로도 충분하지 않으며, 근사 알고리즘을 사용할 수밖에 없다. 역사적으로 볼 때, 확률적 알고리즘에 대한 연구가 시작된 것은 1976년에 제안된 밀러-라빈 소수판별법 이후이다. 그때까지는 주어진 수가 소수인지 아닌지 판별하는 결정론적 알고리즘은 존재하지 않았다. 밀러-라빈 소수판별법은 두 개의 자연수 *k*와 *n*사이의 '증거'(witness)라는 이항관계를 사용한다. '증거' 관계는 다음과 같은 성질을 가진다. * *n*에 대한 증거가 존재하면, *n*은 합성수이다. (즉, *n*은 소수가 아니다.), * *n*이 합성수이면 *n*보다 작은 수 중에서 최소한 3/4은 *n*이 합성수라는 증거이다. * *k*와 *n*이 주어졌을 때, *k*가 *n*이 합성수라는 것에 대한 증거인지 아닌지 판별하는 빠른 알고리즘이 존재한다. 위와 같은 내용에서 소수 판별 문제가 Co-RP에 속하는 것을 알 수 있다. 합성수 *n*보다 작은 임의의 수를 100번 선택하여 알고리즘을 실행시킨다면, 이런 '증거'를 못 찾을 확률은 (1/4)100이다. 그러므로 거의 대부분의 경우에서, 이와 같은 소수 판별법은 매우 좋은 알고리즘이라고 생각할 수 있다. 특히*n*이 아주 크다면, 이 방법 이외에는 효율적인 알고리즘이 없다. 알고리즘을 여러 번 시행하면 오류가 일어날 확률을 원하는 만큼 줄일 수도 있다. 작은 확률로 오류가 발생하더라도 알고리즘을 조금만 주의해서 실행시키면 오류가 일어날 확률을 천문학적으로 작은 숫자만큼 줄일수 있기 때문에, 실제로 오류가 발생하는 것은 그다지 큰 문제가 되지 않는다. 실제로 결정론적으로 소수를 판별하는 다항시간 알고리즘이 발견되었어도, 다양한 암호 관련 소프트웨어에서는 기존의 소수 판별법을 그대로 사용하고 있으며, 소수 판별 분야에서는 결정론적 알고리즘이 가까운 시일 안에 기존 확률적 알고리즘을 대체할 수는 없을 것으로 보인다. 확률적 알고리즘을 사용하면 오류가 일어날 확률이 2−1000이라고 할 때, 여기서 중요한 철학적 문제가 생긴다. '이것을 과연 수학적 증명이라고 볼 수 있느냐'는 것이다. 사실, 알고리즘이 실행되다가 오류가 일어날 확률은 이 알고리즘을 컴퓨터에서 실행시키다가 컴퓨터 자체의 오류가 날 확률보다 현저히 낮다. 그러나 100% 확실한 것은 아니므로 수학적으로 엄밀하다고 할 수는 없다. 이 문제에 대한 명백한 해답은 아직까지 없다.
# 응용
퀵 정렬은 아마도 난수를 사용하는 알고리즘 중에서 가장 유명한 실용 알고리즘일 것이다. 결정론적 알고리즘을 사용하면 어떤 경우 *n*개를 정렬하는데 {\color{Blue}O}(n^2) 만큼의 시간이 걸린다.예를 들어 거꾸로 정렬된 원소에서 피벗(pivot)을 계속해서 잘못 선택하여 n개의 원소를 1:n - 1으로 분해하는 경우가 반복되는 경우. 그러나 만약 임의의 원소를 무작위로 선택하는 방법을 쓰면, 높은 확률로 {\color{Blue}O}(n \log n)만큼의 실행시간이 걸린다. 많은 양의 자료를 정렬할 때, 이 차이는 매우 크다. 더욱 복잡한 예로는 그래프 이론과 관련된 문제가 있다. 다음은 minimum cut 알고리즘이다. find_min_cut(undirected graph G) { while G에서 2개 이상의 꼭짓점이 있을 때 do { G에서 임의의 변 (u,v)를 뽑는다 multi-edge는 그대로 유지하면서 변을 축약시킨다. 모든 고리를 없앤다. } 남은 모서리를 되돌린다. } 여기서 모서리 (u,v)를 줄인다는 것은 새로운 꼭짓점 w를 더하고 (u,x) 혹은 (v,x)를 (w,x)로 바꾸고, G에서 u와 v를 없애는 것이다. (간단히 설명하자면, 모서리를 줄인다고 생각하지 말고 두 꼭지점을 선택한 다음에 두 꼭지점을 하나로 합쳐버린다고 생각하면 쉽다.) n이 이 그래프의 꼭짓점의 개수라고 하면, 알고리즘은 최소 n^{-2}\ 의 확률로 최소 절단을 찾아낸다. 그러므로 위 알고리즘을 n^2 \log n\ 번 실행시켜서 실행 결과중 가장 작은 값을 선택하면, 높은 확률로 최소 절단(minimum cut)을 찾아낼 수 있다.