라스베이거스 알고리즘

컴퓨팅에서 라스베이거스 알고리즘(Las Vegas algorithm)은 항상 올바른 결과를 제공하는 확률적 알고리즘이다. 즉, 항상 올바른 결과를 생성하거나 실패를 알린다. 그러나 라스베이거스 알고리즘의 실행 시간은 입력에 따라 달라진다. 라스베이거스 알고리즘의 일반적인 정의에는 알고리즘에서 사용되는 임의 정보 또는 엔트로피 공간에 대해 기대값이 수행되는 기대 실행 시간이 유한하다는 제약이 포함된다. 대안적인 정의는 라스베이거스 알고리즘이 항상 종료되지만 (유효하지만) 해결책을 찾지 못했음을 나타내기 위해 솔루션 공간의 일부가 아닌 기호를 출력할 수 있다고 요구한다.^[1] 라스베이거스 알고리즘의 본질은 가능한 솔루션의 수가 제한적이고, 후보 솔루션의 정확성을 검증하는 것이 비교적 쉽지만 솔루션을 찾는 것이 복잡한 상황에 적합하다.

명제 만족도(SAT)에 대한 데이비스-푸트넘 알고리즘의 일부 변형과 같이 계산적으로 어려운 문제에 대한 체계적인 검색 방법도 비결정적 결정을 활용하므로 라스베이거스 알고리즘으로 간주될 수 있다.^[2]

역사

라스베이거스 알고리즘은 1979년 라스즐로 바바비에 의해 그래프 동형 문제의 맥락에서 몬테카를로 알고리즘의 듀얼로 소개되었다.^[3] 바바비^[4]는 동전 던지기 예시와 함께 "라스베이거스 알고리즘"이라는 용어를 도입했다. 이 알고리즘은 일련의 독립적인 동전 던지기에 의존하며, 실패(결과 없음)의 작은 확률이 있다. 그러나 몬테카를로 알고리즘과 대조적으로 라스베이거스 알고리즘은 보고된 모든 결과의 정확성을 보장할 수 있다.

예시

// 라스베이거스 알고리즘, A는 길이가 n인 배열이라고 가정한다.
// 목표: A[k] == 1이 되도록 올바른 인덱스 k를 반환한다.
n = A.length
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;

위에서 언급했듯이 라스베이거스 알고리즘은 항상 올바른 결과를 반환한다. 위 코드는 이 속성을 보여준다. 목표는 배열 A에서 값 1을 포함하는 인덱스를 찾는 것이다. 변수 k는 무작위로 생성된다. k가 생성된 후 k는 배열 A의 인덱스로 사용된다. 이 인덱스가 값 1을 포함하면 k가 반환되고, 그렇지 않으면 알고리즘은 1을 찾을 때까지 이 과정을 반복한다. 이 라스베이거스 알고리즘은 올바른 답을 찾는 것이 보장되지만, 고정된 실행 시간을 가지지 않는다. 무작위화(위 코드의 4행)로 인해 알고리즘이 종료되기 전까지 임의로 많은 시간이 경과할 수 있다.

정의

이 섹션에서는 알고리즘이 라스베이거스 유형이 되기 위한 조건을 제공한다.

알고리즘 A는 문제 클래스 X에 대한 라스베이거스 알고리즘이다, 만약^[5]

1. 주어진 문제 인스턴스 x∈X에 대해 솔루션 s를 반환할 때마다, s는 x의 유효한 솔루션임을 보장한다.
2. 주어진 각 인스턴스 x에서 A의 실행 시간은 확률 변수 RT_A,x이다.

라스베이거스 알고리즘에는 세 가지 완전성 개념이 있다.

• 완전한 라스베이거스 알고리즘은 각 풀 수 있는 문제를 실행 시간 tmax 내에서 해결할 수 있음을 보장한다. 여기서 tmax는 인스턴스 종속 상수이다.

P(RT_A,x ≤ t)가 A가 시간 t 내에 풀 수 있는 인스턴스 x에 대한 솔루션을 찾을 확률을 나타낸다고 하자. 그러면 A는 각 x에 대해 다음을 만족하는 경우에만 완전하다.

P(RT_A,x ≤ t_max) = 1인 tmax가 존재한다.

• 대략적으로 완전한 라스베이거스 알고리즘은 실행 시간이 무한대에 가까워질수록 확률이 1로 수렴하는 각 문제를 해결한다. 따라서 A는 각 인스턴스 x에 대해 lim_t→∞ P(RT_A,x ≤ t) = 1인 경우에만 대략적으로 완전하다.
• 본질적으로 불완전한 라스베이거스 알고리즘은 대략적으로 완전하지 않은 라스베이거스 알고리즘이다.

대략적인 완전성은 주로 이론적인 관심사이다. 왜냐하면 솔루션을 찾는 시간 제한은 보통 너무 커서 실제 사용에 거의 유용하지 않기 때문이다.

응용 시나리오

라스베이거스 알고리즘은 문제 설정에 따라 평가 기준이 다르다. 라스베이거스 알고리즘은 정해진 시간 복잡도가 없으므로 이러한 기준은 서로 다른 시간 제한을 가진 세 가지 범주로 나뉜다. 몇 가지 가능한 응용 시나리오는 다음과 같다.

• 유형 1: 시간 제한이 없어 알고리즘이 해결책을 찾을 때까지 실행된다.
• 유형 2: 결과를 찾는 데 시간 제한 t_max가 있다.
• 유형 3: 해결책을 찾는 데 필요한 시간에 따라 해결책의 유용성이 결정된다.

(유형 1과 유형 2는 유형 3의 특수한 경우이다.)

시간 제한이 없는 유형 1의 경우, 평균 실행 시간이 실행 시간 동작을 나타낼 수 있다. 유형 2의 경우와는 다르다.

여기서 P(RT ≤ t_max), 즉 시간 내에 해결책을 찾을 확률이 실행 시간 동작을 설명한다.

유형 3의 경우, 실행 시간 동작은 rtd(t) = P(RT ≤ t)로 정의되는 실행 시간 분포 함수 rtd: R → [0,1] 또는 그 근사치로만 나타낼 수 있다.

실행 시간 분포(RTD)는 라스베이거스 알고리즘의 실행 시간 동작을 설명하는 독특한 방법이다.

이 데이터를 통해 평균 실행 시간, 표준 편차, 중앙값, 백분위수 또는 임의의 시간 제한 t에 대한 성공 확률 P(RT ≤ t)와 같은 다른 기준을 쉽게 얻을 수 있다.

응용

비유

라스베이거스 알고리즘은 탐색 문제에서 자주 발생한다. 예를 들어, 온라인에서 정보를 찾는 사람은 원하는 정보를 얻기 위해 관련 웹사이트를 검색할 수 있다. 따라서 시간 복잡도는 "운이 좋아" 즉시 콘텐츠를 찾는 것부터 "운이 없어" 많은 시간을 소비하는 것까지 다양하다. 올바른 웹사이트를 찾으면 오류가 발생할 가능성은 없다.^[6]

확률적 퀵 정렬

INPUT:
    # A는 n개의 요소를 가진 배열이다.
def randomized_quicksort(A):
    if n == 1:
        return A  # A는 정렬되어 있다.
    else:
        i = random.randrange(1, n)  # 1~n 범위에서 무작위 숫자를 선택한다.
        X = A[i]  # 피벗 요소이다.
    """위 그림과 같이 A를 x보다 작은 요소, x, x보다 큰 요소로 분할한다.
    A[1 to i-1]과 A[i+1 to n]에 대해 퀵 정렬을 실행한다.
    정렬된 배열을 얻기 위해 응답을 결합한다."""

간단한 예로는 확률적 퀵 정렬이 있다. 여기서 피벗은 무작위로 선택되며, 요소를 피벗보다 작은 요소, 피벗과 같은 요소, 피벗보다 큰 요소의 세 부분으로 나눈다. 퀵 정렬은 항상 이 경우 정렬된 배열인 해결책을 생성한다. 불행히도 시간 복잡도는 그렇게 분명하지 않다. 실행 시간은 어떤 요소를 피벗으로 선택하는지에 따라 달라진다.

• 피벗이 가장 작은 요소 또는 가장 큰 요소일 때 최악의 경우 Θ(n²)이다.

${\displaystyle T(n)=T(0)+T(n-1)+\Theta (n)}$

${\displaystyle T(n)=\Theta (1)+T(n-1)+\Theta (n)}$

${\displaystyle T(n)=T(n-1)+\Theta (n)}$

${\displaystyle T(n)=\Theta (n^{2})}$

• 그러나 무작위화를 통해 피벗이 매번 무작위로 선택되고 정확히 중간 값일 때 퀵 정렬은 Θ(nlogn)으로 수행될 수 있다.

${\displaystyle T(n)\leq 2*T(n/2)+\Theta (n)}$

${\displaystyle T(n)=\Theta (n\log(n))}$

퀵 정렬의 실행 시간은 피벗이 얼마나 잘 선택되는지에 크게 의존한다. 피벗 값이 너무 크거나 작으면 분할이 불균형하여 효율성이 떨어진다. 그러나 피벗 값이 배열의 중간에 가까우면 분할이 상당히 균형을 이루어 더 빠른 실행 시간을 제공한다. 피벗이 무작위로 선택되므로 실행 시간은 대부분의 경우 좋고 때때로 나쁘다.

평균적인 경우, 분석이 입력 분포에 의존하는 것이 아니라 알고리즘이 내리는 무작위 선택에 의존하므로 결정하기 어렵다. 퀵 정렬의 평균은 알고리즘이 피벗을 선택할 때 내릴 수 있는 모든 가능한 무작위 선택에 대해 계산된다.

최악의 실행 시간은 Θ(n²)이지만, 평균 실행 시간은 Θ(nlogn)이다. 최악의 경우는 자주 발생하지 않는 것으로 밝혀졌다. n 값이 클수록 실행 시간은 높은 확률로 Θ(nlogn)이다.

피벗이 매번 중간 값 요소일 확률은 n개의 숫자 중 하나이므로 매우 드물다. 그러나 분할이 50%-50% 대신 10%-90%인 경우에도 재귀 트리의 깊이가 여전히 O(logn)이고 각 재귀 수준에서 O(n) 시간이 소요되므로 실행 시간은 동일하다.

8퀸 문제에 대한 확률적 그리디 알고리즘

8퀸 문제는 일반적으로 퇴각검색 알고리즘으로 해결된다. 그러나 라스베이거스 알고리즘을 적용할 수 있으며, 사실 퇴각검색보다 더 효율적이다.

체스판에 8개의 퀸을 서로 공격하지 않도록 놓는다. 퀸은 같은 행, 열, 대각선에 있는 다른 말들을 공격한다는 것을 기억하자.

k개의 행, 0 ≤ k ≤ 8이 퀸으로 성공적으로 채워졌다고 가정한다.

k = 8이면 성공적으로 중지한다. 그렇지 않으면 k + 1행을 채우는 작업을 계속한다.

기존 퀸에 의해 공격받지 않는 이 행의 모든 위치를 계산한다. 그러한 위치가 없으면 실패한다. 그렇지 않으면 하나를 무작위로 선택하고, k를 증가시킨 후 반복한다.

퀸을 놓을 수 없으면 알고리즘은 단순히 실패한다는 점에 유의한다. 그러나 이 과정은 반복될 수 있으며 매번 다른 배열을 생성할 것이다.^[7]

복잡도 종류

기댓값 다항식 실행 시간을 가진 라스베이거스 알고리즘을 가진 결정 문제의 복잡도 종류는 ZPP이다.

다음과 같이 밝혀졌다.

${\displaystyle {\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}}$

이는 라스베이거스 알고리즘이 때때로 구성되는 방식과 밀접하게 연결되어 있다. 즉, RP 클래스는 올바른 답이 "아니오"일 때 항상 올바르게 답하지만, 답이 "예"일 때 1에서 벗어난 특정 확률로 틀릴 수 있는 확률적 다항 시간 알고리즘이 존재하는 모든 결정 문제로 구성된다. 문제와 그 보수(답이 "예"와 "아니오"로 바뀌는) 모두에 대해 그러한 알고리즘이 존재할 때, 두 알고리즘을 동시에 반복적으로 실행할 수 있다. 즉, 각각의 알고리즘을 일정한 수의 단계 동안 교대로 실행하여 하나가 명확한 답을 반환할 때까지 진행한다. 이것이 기대 다항 시간으로 실행되는 라스베이거스 알고리즘을 구성하는 표준적인 방법이다. 일반적으로 라스베이거스 알고리즘의 실행 시간에는 최악의 경우 상한이 없다는 점에 유의한다.

최적의 라스베이거스 알고리즘

라스베이거스 알고리즘을 최적으로 만들기 위해서는 예상 실행 시간을 최소화해야 한다. 이는 다음을 통해 수행할 수 있다.

1. 라스베이거스 알고리즘 A(x)는 t₁ 단계만큼 반복적으로 실행된다. A(x)가 실행 중에 멈추면 A(x)는 완료된다. 그렇지 않으면 처음부터 t₂ 단계만큼 과정을 반복하는 식이다.
2. T_A(x) 분포에 대한 모든 정보가 주어졌을 때, A(x)의 모든 전략 중에서 최적인 전략을 설계한다.

최적 전략의 존재는 매력적인 이론적 관찰일 수 있다. 그러나 T_A(x) 분포에 대한 정보를 찾는 것이 쉽지 않기 때문에 실제 생활에서는 실용적이지 않다. 더욱이 대부분의 경우 x에 대한 답이 한 번만 필요하므로 분포에 대한 정보를 얻기 위해 실험을 반복적으로 실행할 필요가 없다.^[8]

몬테카를로 알고리즘과의 관계

라스베이거스 알고리즘은 사용되는 자원은 제한되지만 답변이 특정(일반적으로 작은) 확률로 틀릴 수 있는 몬테카를로 알고리즘과 대조된다. 라스베이거스 알고리즘은 정해진 시간 동안 실행하고 종료되지 않으면 무작위 답변을 생성함으로써 몬테카를로 알고리즘으로 변환할 수 있다. 마르코프 부등식을 적용하여 라스베이거스 알고리즘이 고정된 한계를 초과할 확률에 대한 상한을 설정할 수 있다.

다음은 라스베이거스 알고리즘과 몬테카를로 알고리즘을 비교한 표이다.^[9]

	실행 시간	정확성
라스베이거스 알고리즘	확률적	확정적
몬테카를로 알고리즘	확정적	확률적

정확성 테스트를 위한 결정론적인 방법이 있다면 몬테카를로 알고리즘을 라스베이거스 알고리즘으로 바꿀 수 있다. 하지만 알고리즘을 테스트할 방법이 없다면 몬테카를로 알고리즘을 라스베이거스 알고리즘으로 바꾸기 어렵다. 반면에 라스베이거스 알고리즘을 몬테카를로 알고리즘으로 바꾸는 것은 쉽다. 이는 신뢰도 매개변수로 주어진 특정 시간 동안 라스베이거스 알고리즘을 실행함으로써 가능하다. 알고리즘이 시간 내에 해를 찾으면 성공이고, 그렇지 않으면 "죄송합니다"라고 출력할 수 있다.

다음은 비교를 위한 라스베이거스 및 몬테카를로 알고리즘의 예시이다.^[10]

짝수 n 길이를 가진 배열이 있다고 가정하자. 배열의 절반은 0이고 나머지 절반은 1이다. 여기서 목표는 1을 포함하는 인덱스를 찾는 것이다.

// A는 길이가 n인 배열이다.
n = A.length

// 라스베이거스 알고리즘
repeat:
    k = RandInt(n);
    if A[k] == 1,
        return k;

// 몬테카를로 알고리즘
repeat 300 times:
    k = RandInt(n);
    if A[k] == 1,
        return k;
return "Failed";

라스베이거스 알고리즘은 배열에서 1을 찾을 때까지 끝나지 않으므로, 정확성을 놓고 도박을 하는 것이 아니라 실행 시간을 놓고 도박을 한다. 반면에 몬테카를로 알고리즘은 300번 실행되므로 코드를 실제로 실행하기 전까지는 300번의 루프 내에서 배열에서 "1"을 찾을지 알 수 없다. 해를 찾을 수도 있고 찾지 못할 수도 있다. 따라서 라스베이거스 알고리즘과 달리 몬테카를로 알고리즘은 실행 시간이 아니라 정확성을 놓고 도박을 한다.

같이 보기

• 몬테카를로 알고리즘
• 애틀랜틱 시티 알고리즘
• 무작위성