라스베이거스 알고리즘

컴퓨팅에서 라스베이거스 알고리즘은 항상 정확한 결과를 제공하는 임의화된 알고리즘이다. 즉, 항상 정확한 결과를 생산하거나 실패에 대해 알려준다. 그러나 라스베이거스 알고리즘의 런타임은 입력에 따라 다르다. 라스베이거스 알고리즘의 통상적인 정의에는 알고리즘에 사용되는 무작위 정보 공간, 즉 엔트로피에 대해 기대가 수행되는 예상 런타임이 유한하다는 제약을 포함한다. 대안 정의에서는 라스베이거스 알고리즘이 항상 종료되어야 하지만(효과적임)^[1] 해결책 찾기의 실패를 나타내기 위해 솔루션 공간의 일부가 아닌 기호를 출력할 수 있다. 라스베이거스 알고리즘의 특성상 가능한 해결책의 수가 제한되고, 솔루션을 찾는 것이 복잡하면서도 후보 솔루션의 정확성을 검증하는 것이 상대적으로 쉬운 상황에서 적합하다.

라스베이거스 알고리즘은 인공지능 분야, 컴퓨터 과학과 운영 연구 분야 등에서 두각을 나타내고 있다. AI에서 확률론적 로컬 검색(SLS) 알고리즘은 라스베이거스 유형으로^{[citation needed]} 간주된다. SLS 알고리즘은 NP-완전한 의사결정 문제와 NP-하드 결합 최적화 문제를 해결하기 위해 사용되어 왔다.^[2] 그러나, 데이비스-의 현대적 변종과 같은 몇 가지 체계적인 검색 방법.제안 만족도(SAT)를 위한 Putnam 알고리즘도 비결정론적 결정을 활용하기 때문에 라스베이거스 알고리즘으로도 간주할 수 있다.^[3]

역사

라스베이거스 알고리즘은 1979년 라슬로 바바이에 의해 그래프 이형성 문제의 맥락에서 몬테카를로 알고리즘의 이중으로 도입되었다.^[4] 바바이는^[5] 코인 플립과 관련된 예와 함께 "라스 베가스 알고리즘"이라는 용어를 도입했는데, 이 알고리즘은 일련의 독립적인 코인 플립에 의존하고 있으며, 실패 가능성은 거의 없다(결과가 없다). 그러나 몬테카를로 알고리즘과 대조적으로 라스베이거스 알고리즘은 보고된 결과의 정확성을 보장할 수 있다.

예

// 라스베이거스 알고리즘 되풀이하여 말하다:     k = 랜딘트(n)     만일 A[k] == 1,         돌아오다 k; 

위에서 언급했듯이 라스베이거스 알고리즘은 항상 정확한 결과를 반환한다. 위의 코드는 이 속성을 나타낸다. 변수 k는 임의로 생성되며, k가 생성된 후에는 배열 A를 인덱스하는 데 k가 사용된다. 이 인덱스에 값 1이 포함되면 k가 반환되고, 그렇지 않으면 알고리즘이 1을 찾을 때까지 이 프로세스를 반복한다. 이 라스베이거스 알고리즘은 정답을 찾을 수 있도록 보장되어 있지만 정해진 런타임이 없다. 임의로 (위 코드의 3행에서) 임의로 많은 시간이 경과하여 알고리즘이 종료될 수 있다.

정의

이 섹션은 알고리즘이 라스베이거스 유형임을 특징짓는 조건을 제공한다.

알고리즘^[6] A는 문제 클래스 X에 대한 라스베이거스 알고리즘이다.

1. 주어진 문제 인스턴스 x∈X에 대해 솔루션 s를 반환할 때마다 s는 x의 유효한 솔루션이 될 것을 보장한다.
2. 각 주어진 인스턴스 x에서 A의 런타임은 랜덤 변수 RT이다_A,x.

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

• 완전한 라스베이거스 알고리즘은 각 해결 가능한 문제를 런타임 tmax 내에서 해결할 수 있도록 보장할 수 있다. 여기서 tmax는 인스턴스 의존 상수다.

P(RT_A,x ≤ t)는 A가 수용성 인스턴스 x에 대한 솔루션을 t 내에서 시간 내에 찾을 확률을 나타내며, 이때 각 x에 대해 존재하는 경우 A는 정확히 완료된다.

P(RT max t) = 1과_A,x 같은_max 일부 tmax.

• 대략 완전한 라스베이거스 알고리즘은 런타임이 무한대에 가까워질 때 1로 수렴되는 확률로 각 문제를 해결한다. 따라서 각 인스턴스 x에 대해_t→∞ 림 P(RT_A,x ≤ t) = 1인 경우 A는 대략 완성된다.
• 본질적으로 불완전한 라스베이거스 알고리즘은 대략적으로 완전하지 않은 라스베이거스 알고리즘이다.

대략적인 완성도는 주로 이론적인 관심사인데, 해결책을 찾기 위한 시간 제한은 일반적으로 실용적이기에는 너무 크기 때문이다.

응용 시나리오

라스베이거스 알고리즘은 문제 설정에 따른 평가 기준이 다르다. 이 기준은 라스베이거스 알고리즘이 시간 복잡성을 설정하지 않기 때문에 시간제한이 다른 3가지 범주로 나뉜다. 가능한 애플리케이션 시나리오:

유형 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)와 같은 다른 기준을 쉽게 얻을 수 있다.

적용들

유추

라스베이거스 알고리즘은 검색 문제에서 자주 발생한다. 예를 들어, 온라인에서 어떤 정보를 찾는 사람은 원하는 정보를 위해 관련 웹사이트를 검색할 수 있다. 따라서 시간 복잡성은 "행운"을 얻고 즉시 콘텐츠를 찾는 것에서부터 "행운하지 않고" 많은 시간을 소비하는 것에 이르기까지 다양하다. 일단 제대로 된 웹사이트가 발견되면 오류의 가능성이 없다.^[7]

랜덤화된 QuickSort

입력:      # A는 n 원소의 배열이다. 반항하다 무작위화된_quicksort(A):     만일 n == 1:         돌아오다 A  # A는 정리된다.     다른:         i = 무작위의.랜드랑주(1, n)  # 1~n 범위에서 무작위 번호 취함         X = A[i]  # 피벗 요소     """"분절 A는 위의 그림에서와 같이 원소 <x, x, >x #로 분절한다.     A[1 ~ i-1] 및 A[i+1 ~ n]에서 Quicksort를 실행하십시오.     정렬된 배열을 가져오려면 응답을 결합하십시오.""" 

간단한 예로 피벗이 무작위로 선택되는 임의의 QuickSort를 들 수 있는데, 여기서 피벗을 임의로 선택하고 요소를 피벗보다 작은 요소, 피벗보다 같은 요소, 피벗보다 큰 요소 등 세 개의 파티션으로 나눈다. 랜덤화된 QuickSort는 많은 리소스를 필요로 하지만 항상 소트된 배열을 출력으로 생성한다.^[8]

QuickSort는 항상 솔루션을 생성하며, 이 경우 정렬된 어레이를 생성한다. 불행히도, 시간 복잡성은 그렇게 명백하지 않다. 실행 시간은 피벗으로 어떤 요소를 선택하느냐에 따라 달라지는 것으로 나타났다.

• 피벗이 가장 작거나 가장 큰 원소일 때 최악의 경우 ((n²)

$[\displaystyle T(n)=T(0)+T(n-1)+\세타(n)}$

$[\displayplaystyle T(n)=\테타(1)+T(n-1)+\세타(n)}$

$T(n)=T(n-1)+\세타(n)}$

$[\displayplaystyle T(n)=\테타(n^{2})}$

• 단, 피벗이 무작위로 선택되고 매번 정확히 중간값인 임의화를 통해 through(nlogn)로 QuickSort를 수행할 수 있다.

$[\displaystyle T(n)\leq 2*T(n/2)+\세타(n)}$

$[\displayplaystyle T(n)=\테타(n\log(n))}$

QuickSort의 실행 시간은 피벗을 얼마나 잘 선택하느냐에 따라 크게 달라진다. 피벗 값이 너무 크거나 작으면 파티션이 불균형하게 된다. 이 사건은 러닝타임이 나쁘다 그러나 피벗 값이 배열의 중간 근처에 있으면 분할이 합리적으로 잘 균형을 이룰 것이다. 따라서 러닝 타임이 좋을 것이다. 피벗은 랜덤으로 선택되기 때문에 대부분의 경우 런닝 시간이 양호하고 때로는 나쁠 수 있다.

평균적인 경우의 경우, 분석은 입력분포가 아니라 알고리즘이 하는 임의선택에 따라 달라지기 때문에 판단하기가 어렵다. QuickSort의 평균은 알고리즘이 피벗을 선택할 때 할 수 있는 모든 가능한 무작위 선택에 대해 계산된다.

최악의 경우 주행 시간은 θ(n²)이지만, 평균 사례 주행 시간은 θ(nlogn)이다. 최악의 경우는 자주 일어나지 않는 것으로 나타났다. n의 큰 값의 경우 런닝 시간은 높은 확률의 with(nlogn)이다.

매번 피벗이 중간값 요소일 확률은 n개 숫자 중 1개이며 매우 드물다는 점에 유의한다. 단, 재귀 트리의 깊이는 여전히 O(logn)이고 각 재귀 레벨의 O(n) 횟수는 O(logn)이기 때문에 분할이 50%~50%가 아닌 10%~90%인 경우에도 동일한 가동 시간이다.

퀸 8개 문제에 대한 무작위화된 탐욕 알고리즘

8명의 여왕 문제는 대개 역추적 알고리즘으로 해결된다. 그러나, 라스베가스의 알고리즘은 적용될 수 있다; 사실, 그것은 역추적보다 더 효율적이다.

다른 사람을 공격하지 않도록 8명의 여왕을 체스판 위에 올려놓아라. 여왕은 같은 줄, 기둥, 대각선 위에 있는 다른 조각들을 공격한다는 것을 기억하라.

k줄, 0 ≤ k 8 8이 여왕들에 의해 성공적으로 점령되었다고 가정해 보자.

k = 8이면 성공으로 중단한다. 그렇지 않으면 k + 1열 점거를 계속하십시오.

기존 여왕이 공격하지 않는 이 열의 모든 위치를 계산하십시오. 만약 없다면, 실패하라. 그렇지 않으면 임의로 하나를 선택하고 k를 증가시킨 후 반복한다.

퀸을 배치할 수 없는 경우 알고리즘이 단순히 실패한다는 점에 유의하십시오. 그러나 그 과정은 반복될 수 있고 매번 다른 배치를 만들어 낼 것이다.^[9]

복잡도 등급

예상 다항식 런타임이 있는 라스베이거스 알고리즘이 있는 의사결정 문제의 복잡도 등급은 ZPP이다.

알고 보니

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

라스베이거스 알고리즘이 만들어지는 방식과 밀접하게 연관되어 있다. 즉, 클래스 RP는 정답을 "아니오"라고 할 때 항상 정확하게 답하지만, 답이 "예"라고 할 때 경계에서 일정한 확률로 틀릴 수 있는 무작위화된 다항식 시간 알고리즘이 존재하는 모든 결정 문제로 구성된다. 이러한 알고리즘이 문제와 그 보완성("예"와 "아니오"의 답변이 교환됨) 모두에 대해 존재하는 경우, 두 알고리즘을 동시에 반복적으로 실행할 수 있다. 즉, 각 알고리즘을 일정한 수의 스텝에 대해 차례로 실행하며, 그들 중 하나가 확정적인 답변을 반환할 때까지 실행한다. 이것은 예상 다항식 시간에 실행되는 라스베이거스 알고리즘을 구성하는 표준 방법이다. 일반적으로 라스베이거스 알고리즘의 실행 시간에 최악의 경우 상한은 없다는 점에 유의하십시오.

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

라스베이거스 알고리즘을 최적의 상태로 만들려면 예상 실행 시간을 최소화해야 한다. 이 작업은 다음을 통해 수행할 수 있다.

1. 라스베이거스 알고리즘 A(x)는 일부 숫자 t₁ 스텝에 대해 반복적으로 실행된다. 실행 시간 중에 A(x)가 정지하면 A(x)가 완료되고, 그렇지 않으면 다른 t₂ 스텝에 대해 처음부터 이 과정을 반복한다.
2. T_A(x)의 분포에 대한 전체 정보를 고려할 때, A(x)의 모든 전략 중에서 최적의 전략을 설계한다.

최적의 전략의 존재는 매혹적인 이론적 관찰일지도 모른다. 그러나 T_A(x)의 유통 정보를 찾기가 쉽지 않아 실생활에서는 실용적이지 못하다. 더욱이 분포에 대한 정보를 얻기 위해 실험을 반복해서 실행할 필요가 없다. 대부분의 경우 x에 대해 한 번만 답이 필요하기 때문이다.^[10]

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

라스베이거스 알고리즘은 사용된 자원이 경계인 몬테카를로 알고리즘과 대조될 수 있지만, 특정(일반적으로 작은) 확률로 정답이 부정확할 수 있다. 라스베이거스 알고리즘은 설정된 시간 동안 실행한 뒤 종료되지 않을 때 무작위 답변을 생성해 몬테카를로 알고리즘으로 변환할 수 있다. 마르코프의 불평등을 응용하면 라스베이거스 알고리즘이 고정 한도를 넘을 확률에 대한 한계를 설정할 수 있다.

라스베가스와 몬테카를로 알고리즘을 비교한 표는 다음과 같다.^[11]

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

이것은 비교를 위한 라스베가스와 몬테카를로 알고리즘의 예다.^[12]

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

// 라스베이거스 알고리즘 되풀이하여 말하다:     k = 랜딘트(n)     만일 A[k] == 1,         돌아오다 k;          //몬테 카를로 알고리즘 되풀이하여 말하다 300 시대:     k = 랜딘트(n)     만일 A[k] == 1         돌아오다 k 돌아오다 "실패" 

라스베이거스는 배열에서 1개를 찾을 때까지 끝나지 않기 때문에 정확성으로 도박을 하지 않고 런타임으로 도박을 한다. 반면 몬테카를로는 300회 운행하는데, 이는 몬테카를로가 실제로 코드를 실행할 때까지 300회 루프 내에서 배열에서 '1'을 발견한다는 것을 알 수 없다는 것을 의미한다. 해결책을 찾을 수도 있고 아닐 수도 있다. 따라서 몬테카를로는 라스베이거스와 달리 런타임으로 도박을 하는 것이 아니라 정확성으로 도박을 하는 것이다.

참고 항목

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

참조

인용구

원천