확률적 알고리즘

위키백과 ― 우리 모두의 백과사전.

확률적 알고리즘(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)¹⁰⁰이다. 그러므로 거의 대부분의 경우에서, 이와 같은 소수 판별법은 매우 좋은 알고리즘이라고 생각할 수 있다. 특히n이 아주 크다면, 이 방법 이외에는 효율적인 알고리즘이 없다. 알고리즘을 여러번 시행하면 오류가 일어날 확률을 원하는 만큼 줄일 수도 있다.

작은 확률로 오류가 발생하더라도 알고리즘을 조금만 주의해서 실행시키면 오류가 일어날 확률을 천문학적으로 작은 숫자만큼 줄일수 있기 때문에, 실제로 오류가 발생하는 것은 그다지 큰 문제가 되지 않는다. 실제로 결정론적으로 소수를 판별하는 다항시간 알고리즘이 발견되었어도, 다양한 암호 관련 소프트웨어에서는 기존의 소수 판별법을 그대로 사용하고 있으며, 소수 판별 분야에서는 결정론적 알고리즘이 가까운 시일 안에 기존 확률적 알고리즘을 대체할 수는 없을 것으로 보인다.

확률적 알고리즘을 사용하면 오류가 일어날 확률이 2⁻¹⁰⁰⁰이라고 할 때, 여기서 중요한 철학적 문제가 생긴다. '이것을 과연 수학적 증명이라고 볼 수 있느냐'는 것이다. 사실, 알고리즘이 실행되다가 오류가 일어날 확률은 이 알고리즘을 컴퓨터에서 실행시키다가 컴퓨터 자체의 오류가 날 확률보다 현저히 낮다. 그러나 100% 확실한 것은 아니므로 수학적으로 엄밀하다고 할 수는 없다. 이 문제에 대한 명백한 해답은 아직까지 없다.

[편집] 응용

퀵 정렬은 아마도 난수를 사용하는 알고리즘 중에서 가장 유명한 실용 알고리즘일 것이다. 결정론적 알고리즘을 사용하면 어떤 경우 n개를 정렬하는데 O(n²) 만큼의 시간이 걸린다. (예를 들어 거꾸로 정렬돈 원소에서 pivot을 계속해서 잘못 선택하여 n개의 원소를 1:n - 1으로 분해하는 경우가 반복되는 경우.) 그러나 만약 임의의 원소를 무작위로 선택하는 방법을 쓰면, 높은 확률로 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²log(n)번 실행시켜서 실행 결과중 가장 작은 값을 선택하면, 높은 확률로 최소절단을 찾아낼 수 있다.

[편집] 참고문헌

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York (NY), 1995.
M. Mitzenmacher and E. Upfal. Probability and Computing : Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY), 2005.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0262032937. Chapter 5: Probabilistic Analysis and Randomized Algorithms, pp.91–122.
Christos Papadimitriou (1993) Computational Complexity, Addison Wesley, ISBN 0201530821, Chapter 11: Randomized computation, pp.241–278.

원본 주소 "http://ko.wikipedia.org../../../%ED%99%95/%EB%A5%A0/%EC%A0%81/%ED%99%95%EB%A5%A0%EC%A0%81_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.html"

분류: 알고리즘